728x90
Stable Sort (안정 정렬)
- 중복된 키를 순서대로 정렬하는 정렬 알고리즘
- 같은 값이 2개 이상 리스트에 등장할 때 기존 리스트에 있던 순서대로 중복된 키들이 정렬된 다는 것을 의미
list = [2, 8, 9, 4(1), 1, 4(2), 6, 7]는 4라는 값이 중복됨
Stable sort 알고리즘으로 정렬 시 [1, 2, 4(1), 4(2), 6, 7, 8, 9]
Unstable sort 알고리즘으로 정렬 시 [1, 2, 4(2), 4(1), 6, 7, 8, 9]
- stable sort로 정렬하는 알고리즘들의 순서는 항상 똑같기에 항상 결과가 같음을 보장할 수 있음
- 첫 문자를 기준으로 문자열을 정렬하는 경우 정렬할 때마다 순서가 다르면 혼란스러울 수 있기 때문에, 항상 안정적으로 같은 리스트가 리턴되는 것이 바람직
Stable Sorting 알고리즘 :
- Insertion Sort
- Merge Sort
- Bubble Sort
- Counting Sort
Unstable Soring 알고리즘 :
- Selection sort
- Heap Sort
- Shell Sort
- Quick Sort
Inplace algorithm
- 추가적인 메모리 공간을 많이/전혀 필요하지 않는 알고리즘
- 통상적으로, 공간은 O(logn)이고 O(n)이 될 때도 있음
list = [5, 2, 3, 4, 1]는 2와 4를 교환함으로써 정렬 가능
In-place : n 길이의 리스트가 있고, 이 리스트를 정렬할 때 추가적으로 메모리 공간을 할당하지 않아도 정렬이 이뤄짐
외 : n 길이의 리스트를 정렬할 때 n 만큼의 메모리보다 더 많은 메모리 공간 할당(공간 복잡도 높음)
Inplace 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
728x90