정렬 알고리즘 평가기준
- 시간 복잡도(최선, 평균, 최악), 공간복잡도
- 안정성
안정성에 대한 부가 설명
안정성은 반복되는 요소를 입력할 때 동일한 순서로 저장되는지 여부이다. 순서가 보장되면 안정 보장되지 않으면 불안정이라고 한다.
안정성이 중요한 이유는 예를 들어 반 학생을 이름순으로 우선정렬할때 안정 정렬 알고리즘이 아니라면 같은 이름의 학생은 항상 같은 순서가 아닌 다른 입력값(다른 학생들의 이름)에 따라 달라지게 된다.
정렬 알고리즘 종류
- 선택 정렬(Selection Sort)
- 삽입 정렬(Insertion Sort)
- 버블 정렬(Bubble Sort)
- 병합 정렬(Merge Sort)
- 퀵 정렬(Quick Sort)(분할정복)
- 힙 정렬(Heap Sort)
- 기수 정렬(Radix Sort)
여기서 특히 Quick Sort와 Merge Sort정도는 코딩테스트를 위해 언제나 직접 구현 가능한 것이 좋다.
상당히 많은 종류의 정렬이 있으나 자주 쓰는 정렬 몇 가지를 정리해보겠다.
위에 있는 정렬 알고리즘은 모두 비교 정렬 알고리즘이며 비교없이 정렬하는 알고리즘들도 있다. 여기서는 기수 정렬만 소개하겠다.
평가기준이나 입력 데이터에 따라 적절한 정렬방법이 있기에 반드시 어느 정렬이 좋다라고 말하긴 어렵다.
선택 정렬(Selection Sort)
선택된 값과 나머지 데이터들을 비교하여 알맞는 자리를 찾는 알고리즘(안정성 보장 x)
O(n^2) 최선 = 평균 = 최악
삽입 정렬(Insertion Sort)
데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아 이를 다시 적당한 곳에 삽입
O(n^2) 최악 = 평균, 최선: 모두 정렬되어 있는 경우 O(n)
버블 정렬(Bubble Sort)
거품이 수면으로 올라오는 듯하여 붙인 이름으로, 인접한 두 수를 비교해서 정렬 안정성은 보장된다.
O(n^2) 최선=최악=최선
병합 정렬(Merge Sort)
둘 이상의 부분 집합으로 가르고, 각 부분집하을 정렬한 다음 부분집합들을 다시 정렬된 형태로 합치는 방식 안정성 보장
분할 정복법을 사용한다.
O(n log n) 최선=평균=최악
단 다른 정렬 대비 O(n) 수준 메모리 추가 필요
퀵 정렬(Quick Sort)(분할정복)
데이터 집합내에 임의의 기준값을 정하고 해당 피벗을 기준으로 두개의 부분집합으로 나눠 한쪽엔 기준보다 작은 값 한쪽엔 기준보다 큰 값만 넣기 안정성 보장 x
O(n log n)평균=최선, O(n^2) 최악
힙 정렬(Heap Sort)
트리 기반으로 최대 힙 트리 or 최소 힙 트리를 구성해 정렬하는 방법 안정성 보장 x
O(n log n) 최선=평균=최악
기수 정렬(Radix Sort)
낮은 자리수부터 비교해가며 정렬, 비교연산이 없어 빠르지만 또 다른 메모리 공간을 필요로 함
O(dn) d:자리수
파이썬 sort()의 경우
파이썬 sort()의 경우 tim sort를 사용한다. 이는 최선의 경우 O(n) 평균 = 최악 O(n log n)라는 시간복잡도에서 유리한 정렬을 사용한다.
