Quicksort
분할 정복. 비교 정렬(다른 원소와의 비교만으로 정렬을 수행)
process
- 배열 가운데 하나의 원소(pivot) 고른다
- 피벗 앞에는 피벗보다 값이 작은 원소, 뒤에는 값이 더 큰 원소가 오도록 배열을 둘로 나눈다. 이 분할 작업을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
- 분할된 두 개의 배열에 대해 재귀적으로 1,2를 반복한다.
시간 복잡도
- best/average : O(nlog₂n)
재귀 호출 깊이 * 각 재귀 호출 단계에서의 비교 연산 - worst : O(n^2)
정렬하고자 하는 배열이 오름차순 혹은 내림차순 정렬되어 있을 때는 재귀 호출 깊이가 n이 된다
공간 복잡도
O(logn) (in-place + 재귀 호출을 위함)
속성
- 위 1,2번 과정에서 최소한 하나의 원소는 최종 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
- 한 번 결정된 피벗들이 추후 연산에서 제외되기 때문에 시간 복잡도가 O(nlog₂n)인 다른 정렬 알고리즘과 비교하면 가장 빠르다.
- 배열 안에서 교환이 이루어져 다른 메모리 공간을 필요로 하지 않는다.
- 불안정 정렬(중복된 값이 입력 순서대로 정렬되지 않을 수 있음)
- 정렬된 배열에 대해서는 불균형 분할 과정 때문에 오히려 수행 시간이 더 많이 걸린다.
- 원 배열이 오름차순이나 내림차순 정렬되어 있을 때를 대비해 피벗을 랜덤 선택, 세 값의 중위(three of median) 정렬 등의 방식으로 개선할 수 있다.
Mergesort
병합 정렬. 분할 정복
process
- 배열을 비슷한 크기의 두 배열로 나눈다. 이 작업을 더 이상 분할이 불가능할 때까지 재귀적으로 반복한다.
- 두 영역을 정렬하면서 병합한다. (합치면서 정렬)
시간 복잡도
O(nlog₂n)
공간 복잡도
O(n)
속성
- 안정 정렬
- 일반적인 경우는 퀵소트보다 느리지만 언제나 시간복잡도가 O(nlog₂n)로 유지된다. (최선, 최악, 평균이 동일)
- 별도의 임시 배열 공간이 필요하다. (in-place가 아니다)
- 연결 리스트로 레코드 구성시 유리하다.
Heapsort
힙 자료구조를 기반으로 한 정렬 방식
process
- 최대 힙을 구성
- 루트에 있는 최대값을 extract함
- 힙의 사이즈가 1보다 크면 1,2를 반복
시간 복잡도
O(nlog₂n)
공간 복잡도
O(1)
속성
- 불안정 정렬
- in-place 정렬
- 최대값, 최소값을 구할 때 한 번의 힙 구성을 통해 구할 수 있음
- 퀵이나 머지소트가 더 많이 쓰이는 편
Bubble Sort
서로 인접한 두 원소의 대소를 비교하여 자리를 교환하며 정렬
process
- (오름차순 정렬 경우) 서로 인접한 원소를 비교하여 더 큰 원소를 뒤로 이동시킨다.
- 맨 뒤에 있는 원소를 제외하고 1번의 과정을 반복한다.
시간 복잡도
best: O(n) (이미 정렬된 경우)
average, worst: O(n^2)
공간 복잡도
O(1)
속성
- 안정 정렬
- in-place 정렬
Selection Sort
배열의 특정 위치에 어떤 원소를 넣을지 선택하는 알고리즘
process
- 주어진 배열 중 최소값을 찾는다
- 최소값을 맨 앞의 값과 교체한다
- 맨 앞을 제외한 나머지 배열에 대해 1,2 과정을 반복한다
시간 복잡도
O(n^2)
공간 복잡도
O(1)
속성
- in-place 정렬
- 불안정 정렬
- 실제 원소의 교환 횟수가 bubble sort보다는 적다 (버블 정렬보다는 우수하다)
Insertion Sort
두번째 원소부터 시작하여 앞쪽의 원소들과 비교하여 삽입할 위치를 정하고, 지정된 자리에 자료를 삽입하여 정렬한다. (ex 손 안에 카드 정렬)
process
- 두번째 위치 값이 key가 된다.
- key와 key 앞에 있는 원소를 비교하여 key가 더 작으면 앞에 있는 원소보다 앞에, 더 크면 뒤에 삽입한다.
- 1번으로 돌아가 다음 위치 값을 key로 지정하고 반복한다
시간 복잡도
best: O(n) (이미 정렬된 경우)
average, worst: O(n^2)
공간 복잡도
O(1)
속성
- 안정 정렬
- 선택 정렬, 버블 정렬보다 빠르다
- 대부분의 원소가 이미 정렬되어 있는 경우, 자료의 수가 적은 경우 매우 효율적이다. 모든 요소에 대해 앞에서부터 차례대로 '이미 정렬된 배열'과 비교하여 삽입될 위치를 찾기 때문이다
- in-place 정렬
Bucket Sort
분포 정렬
process
- 데이터의 범위를 n개로 나누고 n개의 빈 버킷을 만든다
- 정렬할 배열의 원소를 버킷에 나누어 넣는다
- 내용물이 있는 버킷을 각각 정렬한다
- 버킷을 순서대로 방문하여 모든 원소를 원래 배열에 다시 넣는다
시간 복잡도
best, average: O(n)
worst: O(n^2) (하나의 버킷에 원소가 몰리게 될 때)
공간 복잡도
O(n)
속성
- 비교 정렬의 경우 시간 복잡도가 최소 O(nlogn)이다. 데이터 분포 특성에 따라 시간 복잡도를 개선시키기 위해 분포 정렬을 이용한다.
- 버킷 내부 정렬은 주로 삽입 정렬이 이용된다. 내부 정렬이 어떤 알고리즘을 쓰느냐에 따라 비교 정렬에 속하기도 한다.
- 데이터가 특정 범위 내에 확률적으로 균등하게 분포한다고 가정할 수 있을 때 적용할 수 있다
Counting Sort
요소 값을 서로 비교하지 않는 정렬 알고리즘
process
- 원소 값의 개수를 저장하는 카운팅 배열을 만든다
- 카운팅 배열의 각 원소 값에 직전 요소 값을 더한다
- 입력 배열과 같은 크기의 출력 배열을 만든다
- 출력 배열을 카운팅 배열에 따라 채운다
시간 복잡도
O(n+k): 입력 배열에서 개수 세는 시간 복잡도 O(n) + 출력 배열 만드는 시간 복잡도 O(n) + 카운팅 배열 업데이트 시간 복잡도 O(k)
공간 복잡도
O(k)
속성
- k(배열요소 range)가 충분히 작을 경우 빠르지만, k값이 커지면 k가 복잡성을 지배하게 된다. (ex A = [0, 10000]) 정렬하려는 숫자가 특정한 좁은 범위 내에 있을 때 사용하면 효율적이다. k << n이면 시간복잡도 O(n)으로 볼 수 있다
- 안정 정렬
Radix Sort
요소 값을 서로 비교하지 않는 정렬 알고리즘
process
- 가장 낮은 자리부터 정렬한다
- 각 자리수마다 정렬하는데 counting sort를 사용한다
- 각 자리수를 정렬하는 알고리즘은 반드시 stable sort여야 한다
시간 복잡도
O(n) : O(d(자리수)*(n+k)). k << n이고 d가 n보다 작고 상수이면 O(n)으로 볼 수 있다
공간 복잡도
O(n+k)
속성
- 안정 정렬
Shell Sort
삽입 정렬이 어느 정도 정렬된 배열에 대해서는 빠르게 정렬한다는 사실에 기반하여 삽입 정렬을 개선한 알고리즘
process
- 연속적이지 않은 여러 개의 부분 리스트를 만든다
- 각 부분 리스트를 삽입 정렬로 정렬한다
- 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만들어 위 과정을 반복한다
시간 복잡도
- best: O(nlog₂n)
- worst: O(n^2)
공간 복잡도
O(1)
속성
- 교환되는 요소들이 삽입 정렬보다 최종 위치에 더 가까이 있을 확률이 높다
- 부분 리스트가 어느 정도 정렬이 된 상태에서 부분 리스트 개수가 1개가 되면(최종 단계) 삽입 정렬이 빠르게 수행된다
- 불안정 정렬
Cubesort
Tree Sort
Reference
https://gyoogle.dev/blog/algorithm/Quick%20Sort.html
http://syllabus.cs.manchester.ac.uk/ugt/2019/COMP26120/SortingTool/radix_sort_info.html
