안정 정렬(stable sort)과 불안정 정렬(unstable sort)의 차이는 주로 같은 값을 가지는 요소의 상대적인 순서에 있습니다.

1. 안정 정렬 (Stable Sort)

안정 정렬은 같은 값을 가진 요소들이 정렬 후에도 원래의 상대적인 순서를 유지하는 정렬 방법을 말합니다. 즉, 두 개의 값이 같다면, 정렬 전후에 그들의 상대적인 위치가 변경되지 않습니다.

예시: 정렬하려는 데이터가 [5A, 3, 5B, 2]일 때,

• 정렬 후 [2, 3, 5A, 5B]와 같이, 5A와 5B의 상대적인 순서가 그대로 유지됩니다.

안정 정렬의 예:

• 버블 정렬 (Bubble Sort)
• 병합 정렬 (Merge Sort)
• 삽입 정렬 (Insertion Sort)

2. 불안정 정렬 (Unstable Sort)

불안정 정렬은 같은 값을 가진 요소들의 상대적인 순서를 보장하지 않는 정렬 방법입니다. 즉, 값이 같은 두 요소가 정렬 후에 순서가 바뀔 수 있습니다.

예시: 정렬하려는 데이터가 [5A, 3, 5B, 2]일 때,

• 정렬 후 [2, 3, 5B, 5A]와 같이, 5A와 5B의 상대적인 순서가 바뀔 수 있습니다.

불안정 정렬의 예:

• 퀵 정렬 (Quick Sort)
• 선택 정렬 (Selection Sort)
• 힙 정렬 (Heap Sort)

요약

• 안정 정렬: 같은 값을 가진 요소들의 상대적 순서가 변하지 않음.
• 불안정 정렬: 같은 값을 가진 요소들의 상대적 순서가 변할 수 있음.