Stable Sort
- 중복된 키를 순서대로 정렬하는 정렬 알고리즘
-
같은 값이 2개 이상 리스트에 등장할 경우 중복 키들은 기존 리스트에 있던 순서대로 정렬된다
예를 들어, 이런 배열이 있다
1
arr = [9(1번째), 3, 6, 9(2번째), 24, 13]
정렬을 했을 때 이런 순서로 나오게 되는 것이 stable sort다
1
arr = [3, 6, 9(1번째), 9(2번째), 13, 24]
만약 아래와 같은 순서로 뒤섞인다면 unstable sort다
1
arr = [3, 6, 9(2번째), 9(1번째), 13, 24]
stable sort를 알아야 하는 이유
- stable sort로 정렬하는 알고리즘의 순서는 항상 똑같기 때문에 항상 결과가 같다는 것을 보장할 수 있다
- 숫자를 정렬할 때는 stability가 중요하지 않을 수도 있지만 첫 문자를 기준으로 문자열을 정렬하는 경우, 항상 안정적으로 같은 리스트가 리턴되는 것이 바람직할 것이다.
Stable Sorting
- Insertion Sort
- Merge Sort
- Bubble Sort
- Counting Sort
Unstable Sorting
- Heap Sort
- Selection Sort
- Shell Sort
- Quick Sort
Inplace algorithm
- 추가적인 메모리 공간을 많이 필요로 하지 않거나 또는 거의 필요하지 않는 알고리즘
- 보통 공간은 O(logn)이고, O(n)이 될 때도 있다
inplace sorting을 알아야 하는 이유
- n 길이의 리스트가 있고, 리스트를 정렬할 때 추가적으로 메모리공간을 할당하지 않아도 정렬이 이루어진다면 in-place알고리즘이라고 불릴 수 있다.
- inplace하지 않은 알고리즘은 n길이의 리스트를 정렬할 때 n만큼의 메모리보다 더 많은 메모리 공간을 할당한다. 공간복잡도가 높다.
in-place sorting
- Insertion Sort
- Selection Sort
- Bubble Sort
- Shell Sort
- Heap Sort
- Quick Sort
Not in-place sorting
- Merge Sort
- Counting Sort
- Radix Sort
- Bucket Sort
