Python - stable 정렬

정렬에는 두 가지의 유형으로 나눌 수 있는데 하나는 Stable이고, 다른 하나는 In-place가 있다.

Stable Sorting

 어떤 배열을 정렬했을때, 같은 값들은 그 값들 내에서 배열의 순서에 맞게 정렬되는 것, 즉 어떤 a는 2번째에 있고 b는 5번째에 있다고 치자. a와 b에 들어있는 값이 같으면, a, b로 정렬되는 것을 말한다. b, a로 정렬되면 Unstable Sorting이라고 한다.

Sep	Example
Stable Sorting	Insertion Sort Merge Sort Bubble Sort Counting Sort
Unstable Sorting	Selection Sort Heap Sort Shell Sort Quick Sort

 

In-place Algorithm

원소들의 개수에 비해서 충분히 무시할 만한 저장 공간만을 조금 더 사용하는 정렬 알고리즘이다. 즉, 정렬하는데 필요한 추가적인 메모리 공간 비용이 매우 극소적으로 드는 것을 말한다.

Sep	Example
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

 

정리하면 다음과 같다.

Sep	In-place Sorting	Not in-place Sorting
Stable Sorting	Insertion Sort ( O(n^2) ) Bubble Sort ( O(n^2) )	Merge Sort ( O(nlogn) ) Counting Sort ( O(n + k) )
Unstable Sorting	Selection Sort ( O(n^2) ) Heap Sort ( O(nlogn) ) Shell Sort ( O(sqrt(n)) ) Quick Sort ( O(nlogn) )

파이썬은 기본적으로 퀵소트를 따르고 있다.