[Sort] Stable / Unstable 정렬

Stable/Unstable 정렬

--> 비교 대상의 Key가 여러개 값을 가질때 혹은 같은 값을 가지는 데이터가 여러개 있을 때, 정렬후에 기존의 순서를 유지하는지에 따라 Stable과 Unstable로 나뉜다. 비교 Key가 한 개일때는 나누는 것이 굳이 의미 없지만 여러개일 경우(구조체 함수 데이터) 특정한 데이터를 기준으로 Sorting할 경우 Stable/Unstable 정렬의 종류를 고려하여 적용해야 한다.

 

예를들어 

 

Dave A

Alice B

Ken A

Eric B

Carol A

 

위와 같은 데이터를 정렬하려면 두 가지를 기준으로 정렬할 수 있다. 여기서 중복되는 데이터가 있는데 정렬 전 원래의 순서를 기억할것이냐 말것이냐에 따라 Stable과 Unstable 알고리즘을 선택해야 한다.

 

Stable Sort

• Bubble Sort
• Insertion Sort
• Merge Sort
• Counting Sort
• Bucket Sort
• Radix Sort 

Unstable Sort

• Selection Sort
• Shell Sort
• Heap Sort
• Quick Sort