이번 글에서는 여러 가지 정렬 알고리즘을 비교, 분석해 보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.

비교표

알고리즘별 특징을 한 눈에 보기 쉽게 정리한 표는 다음과 같습니다. 아래 표에서 complexity는 average case를 기준으로 한 계산복잡성입니다.

• 버블정렬(Bubble sort) : 주어진 배열의 마지막 위치에 있는 요소를, 정렬되지 않은 직전 요소부터 첫 요소에 이르기까지 비교해 정렬 순서가 맞지 않은 모든 case에 대해 요소 위치를 바꿔줌. 이를 요소 수만큼 반복. 가장 간단하지만 비효율적인 알고리즘.
• 선택정렬(Selection Sort) : 요소 위치 변경 횟수를 줄여 버블정렬을 일부 개선한 알고리즘. 정렬 순서가 맞지 않으면 무조건 자리를 바꿔줬던 버블정렬과 달리, 1회 iteration마다 최소값(혹은 최대값)을 찾고 단 한번만 해당 요소 위치를 바꿔줌.
• 삽입정렬(insertion sort) : 모든 요소에 대해 앞에서부터 차례대로 이미 정렬된 배열(sorted list)과 비교하여 sorted list 내 자신의 위치를 찾아 삽입함으로써 정렬을 완성, 입력데이터가 이미 정렬된 상태라면 $O(n)$의 빠른 속도를 보이지만 그렇지 않은 경우 다른 기법을 적용하는 것이 나음.
• 쉘정렬(shell sort) : 정렬되지 않은 배열의 경우 비효율적인 삽입정렬을 개선한 기법. 주어진 배열의 일정 간격(gap)만큼의 요소들에 대해 삽입정렬을 반복 수행.
• 합병정렬(merge sort) : 리스트를 잘게 쪼갠 뒤 둘씩 크기를 비교해 정렬하고 분리된 리스트를 재귀적으로 합쳐서 정렬을 완성, 분할된 리스트를 저장해둘 공간이 필요해 메모리 소모량이 큰 편
• 힙정렬(heap sort) : 모든 노드가 힙 속성(각 노드의 값이 자신의 자식노드 값보다 큰 이진트리)을 만족하도록 재귀적으로 트리 구조를 만들어 정렬을 완성
• 퀵정렬(quick sort) : 피봇값을 기준으로 피봇 앞에는 피봇보다 작은 값, 뒤에는 큰 값이 오도록 하여 리스트를 분할하고, 분할된 두 개 리스트 각각에 재귀적으로 이 과정을 반복해 정렬을 완성. 합병정렬과 달리 주어진 배열을 임의로 나누지 않기 때문에 대개는 효율적이지만, 피봇값이 잘못 선택되면 $O(n^2)$이 될 수도 있음.
• 카운팅정렬(counting sort) : 입력값의 빈도를 세어서 이를 결과리스트의 인덱스로 활용, 입력리스트의 요소값을 해당하는 결과리스트 인덱스 위치에 채워 넣는 방식으로 정렬을 완성, 입력리스트의 최대값($k$)이 커지면 복잡도가 크게 높아짐
• 래딕스정렬(radix sort) : 입력값의 자릿수($d$) 각각에 대해 카운팅정렬을 적용해 카운팅정렬의 단점 보완, 예컨대 10진법으로 표현된 입력값에 래딕스정렬을 적용하면 $k$값이 9로 작아짐
• 버킷정렬(bucket sort) : 데이터 개수만큼의 버킷을 두어 데이터를 나누고 버킷별로 정렬한 후 합쳐 정렬을 완성, 데이터 분포가 균등할 경우 계산복잡성을 낮출 수 있으나 그 반대의 경우 효과를 기대하기 어려울 수 있음

In-Place

입력리스트 내부에서 정렬이 이뤄지는 경우를 가리킵니다. 반대는 정렬 도중에 별도 저장공간을 필요로 하는 경우입니다. 합병정렬의 경우 입력리스트를 분할해 이를 정렬하고 다시 합치는 과정에서 분할된 리스트를 별도로 저장해 두어야 합니다. 카운팅정렬과 래딕스정렬은 입력값의 빈도를 세어서 저장해 두는 변수, 결과리스트를 저장해 둘 변수가 필요합니다. 버킷정렬은 버킷이라는 변수를 만들 공간이 있어야 합니다.

Stable

Stable이란 같은 값의 위치가 정렬 과정에서 뒤바뀌지 않는 것을 뜻합니다. 아래 그림과 같습니다(위키피디아).

힙정렬은 이진트리를 배열 형태로 표현해 정렬을 수행하는 과정에서 입력값의 위치가 바뀔 수 있습니다. 퀵정렬 또한 피봇을 기준으로 각 요소값들이 좌우로 이동할 수 있어 위치가 바뀔 수 있습니다.

comparison

값을 비교하는 정렬 알고리즘을 comparison sort라고 합니다. comparison sort 계산복잡성의 하한은 $O(n\log{n})$입니다. 카운팅정렬의 경우 값을 비교하지 않고도 정렬을 수행할 수 있어 comparson sort가 아닙니다. 래딕스정렬은 카운팅정렬을 기본으로 사용합니다. 버킷정렬의 경우 각 버킷에 대해 어떤 정렬 알고리즘을 쓰느냐에 따라 comparison 유무가 달라질 수 있습니다.