In-place ? Stable?

In-Place 알고리즘?

쉽게 말하면 추가적인 메모리 공간이 거의 안드는 정렬.

대표적인 In-Place 알고리즘,

• insertion Sort
• Selection Sort
• Bubble Sort
• Sheel Sort
• Heap Sort
• Quick Sort

Not In-Place 알고리즘,

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

Stable 알고리즘?

중복된 키 값이 있을 때 이를 순서대로 정렬하는 알고리즘.

예를 들어,

[7, 6, 5, 4, 7, 3, 2, 1]

위의 배열에는 7이 중복되어 있는데 이를 쉽게 설명하기 위해 아래와 같이 바꾸겠다.

[7(1), 6, 5, 4, 7(2), 3, 2, 1]

이를 정렬했을 때, 중복된 키 값의 순서가 처음와 같다면 stable, 아니면 not stable이라고 한다.

[1, 2, 3, 4, 5, 6, 7(1), 7(2)]

대표적인 Stable Sorting 알고리즘,

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

대표적인 Unstable Soring 알고리즘,

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