[알고리즘] Stable & In-place

Stable 알고리즘

• 정렬할 자료들 중 동일한 두 자료의 상대적인 위치가 **정렬 후에도 유지**되는 알고리즘
• 정렬을 했을 때 중복된 값들의 순서가 변하지 않으면 **안정(Stable) 정렬**, 변하면 **불안정(Unstable) 정렬**

Stable 알고리즘

• Insertion Sort
• Merge Sort
• Bubble Sort
• Counting Sort

Unstable 알고리즘:

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

In-place 알고리즘

• **입력을 저장하는 메모리 공간** 이외에 추가로 사용하는 메모리공간이 O(1)인 알고리즘
• 추가적인 메모리가 거의 들지 않는 알고리즘

In-place 알고리즘

• Insertion Sort
• Selection Sort
• Bubble Sort
• Shell Sort
• Heap Sort
• Quick Sort (경우에 따라 다르지만, 보편적으로 In-place)

Not in-place 알고리즘

• Merge Sort
• Counting Sort
• Radix Sort
• Bucket Sort