Stable Sort &Inplace

 

Stable Sort (안정적인 정렬)

정의:

• Stable Sort는 동일한 값에 대한 상대적인 순서가 정렬 후에도 유지되는 정렬 알고리즘입니다.

예시:

• 예를 들어, 다음과 같은 리스트가 있습니다: [(2, 'a'), (1, 'b'), (2, 'c'), (1, 'd')]
• 안정적인 정렬 알고리즘을 사용하여 첫 번째 요소를 기준으로 오름차순 정렬하면 결과는 [(1, 'b'), (1, 'd'), (2, 'a'), (2, 'c')]가 됩니다.
• 여기서 중요한 점은 두 개의 (1, 'b')와 (1, 'd')는 원래 순서대로 유지되고, 두 개의 (2, 'a')와 (2, 'c')도 원래 순서대로 유지된다는 것입니다.

안정적인 정렬 알고리즘 예시:

• Bubble Sort
• Merge Sort
• Insertion Sort
• Timsort (Python의 내장 sort()와 sorted()에서 사용됨)

불안정한 정렬 알고리즘 예시:

• Quick Sort
• Heap Sort
• Selection Sort

Inplace 정렬

정의:

• Inplace 정렬 알고리즘은 추가적인 메모리를 많이 사용하지 않고, 입력 데이터의 일부만을 이용하여 데이터를 정렬하는 알고리즘입니다. 즉, 입력 배열 외에 추가적인 O(1) 또는 O(log n) 공간만 사용합니다.

예시:

• 배열 [3, 1, 4, 1, 5]를 정렬할 때, Inplace 알고리즘은 이 배열 자체를 변경하여 정렬합니다.

Inplace 정렬 알고리즘 예시:

• Quick Sort (일반적으로 Inplace)
• Heap Sort
• Insertion Sort
• Bubble Sort

비-Inplace 정렬 알고리즘 예시:

• Merge Sort (일반적으로 추가적인 배열 공간 사용)
• Counting Sort (추가적인 배열 사용)

두 개념을 종합한 정렬 알고리즘 분석:

Insertion Sort:

• Stable: 예, 같은 값의 원소들이 입력 순서를 유지합니다.
• Inplace: 예, 추가적인 메모리를 거의 사용하지 않습니다.

Merge Sort:

• Stable: 예, 같은 값의 원소들이 입력 순서를 유지합니다.
• Inplace: 아니요, 추가적인 메모리 배열을 사용합니다.

Quick Sort:

• Stable: 아니요, 같은 값의 원소들이 입력 순서를 유지하지 않을 수 있습니다.
• Inplace: 예, 추가적인 메모리를 거의 사용하지 않습니다.

Heap Sort:

• Stable: 아니요, 같은 값의 원소들이 입력 순서를 유지하지 않습니다.
• Inplace: 예, 추가적인 메모리를 거의 사용하지 않습니다.

이렇게 정렬 알고리즘을 선택할 때는 정렬의 안정성(stable)과 메모리 사용 여부(inplace)를 고려하여 적합한 알고리즘을 선택해야 합니다.