sort (select/bubble/quick/merge/radix)

 Python에서 sort(), sorted() 함수로 사용 가능

 

 

 

 

@선택 정렬(selection sort)

-앞에서부터 최소값과 최대값의 인덱스 저장해가며 정렬

-O(N)

->교환이 많이 이루어져야 하는 자료 상태에서 효율적

 역순 정렬에 가장 적합(내림차순 정렬되어 있는 자료를 오름차순으로 정렬)

-이미 정렬된 상태에서 소수의 자료가 추가됨으로 재정렬하게 될 때는 최악

 

 

 

 

@버블 정렬(bubble sort)

-거품처럼 앞 원소 뒤 원소 비교해가며 정렬

-O(N)

 

 

 

 

@퀵 정렬(quick sort)

-원소 하나 고르고 그것보다 작은 건 그 원소 기준 왼쪽으로, 그것보다 큰 건 오른쪽으로

-최악의 경우 O(N)이 되기 때문에 최악을 피하려고 함

-보통 O(NlogN)이라고 생각하면 됨(빠른 편)

-내부메모리만 사용. 메모리 용량을 많이 쓰지 않음

-가장 많이 쓰이나, 안정성 떨어짐

 

 

 

 

@병합 정렬(merge sort)

-2 pointer 개념을 사용해 나누고 합치며 정렬

-졍렬이 되든 안되든 항상 O(NlogN)의 일정한 속도

-안정적이지만 메모리 용량을 많이 씀

 

 

 

 

@Radix sort

-메모리 용량이 넘쳐날 때, 수의 범위를 알고있을 때 사용

-최소값과 최대값 배열 만들어 주기

->원소 하나씩 카운팅

-반복문 수행하며 정렬