728x90
Stable Sort (안정 정렬)
동일한 정렬기준을 가진 것은 정렬하기 전의 순서와 정렬한 후의 순서가 동일하다
EX (아래의 숫자들을 오름차순으로 정렬할시[이때 1;과 1은 같은 숫자이다])
- 5 2 1; 3 6 1
여기서 동일한 정렬기준을 가진 1; 과 1 이 존재한다. 이런경우 정렬 전/후의 순서가 동일하여 아래와 같은 결과가 나온다.
- 1; 1 2 3 5 6
종류
- timSort (타임정렬)
- Bubble Sort (버블 정렬)
- insertion Sort (삽입 정렬)
- merge Sort (합병 정렬)
Unstable Sort(불안정 정렬)
동일한 정렬기준을 가진 것의 정렬 전/후 순서가 다를 수 있다.
EX (아래의 숫자들을 오름차순으로 정렬할시[이때 1;과 1은 같은 숫자이다])
- 5 2 1; 3 6 1
여기서 동일한 정렬기준 1; 과 1 이 존재한다. 이런경우에 정렬 전의 순서가 유지된다는 보장 할수 없다. 그렇기 때문에 아래의 2가지 결과가 모두 나올 수 있다.
- 1; 1 2 3 5 6
- 1 1; 2 3 5 6
종류
- Selectioin Sort (선택 정렬)
- Quick Sort (퀵 정렬)
- Heap Sort (힙 정렬)
Big O
- Worst Case: O(nlog₂n)
- Best Case: O(nlog₂n)
