[알고리즘] 안정적인 정렬 Stable Sorting

출처

ChatGPT

---

안정적인 정렬이란 정렬 전에 동일한 값을 가진 요소들의 상대적인 순서가 정렬 후에도 유지되는 정렬 알고리즘을 말한다. 즉, 값이 같은 두 요소가 있을 때, 정렬 전에서의 순서가 정렬 후에도 동일하다면 그 정렬 알고리즘은 안정적이다.

예시

병합 정렬(Merge Sort), 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort)은 안정적인 정렬 알고리즘이다.

비안정적인 정렬

퀵 정렬(Quick Sort), 힙 정렬(Heap Sort) 등은 비안정적인 정렬 알고리즘으로, 정렬된 후 동일한 값의 요소들 간의 순서가 변할 수 있다. -> 정렬하면서 값이 같은 요소들의 순서가 바뀌는 경우가 있대 

 

안정적인 정렬의 특징

데이터의 순서 유지

동일한 값이 여러 개가 있을 때, 그 값들 간의 상대적인 순서가 변하지 않는다.

정렬이 중요한 경우

안정적인 정렬은 동일한 값의 순서가 중요한 경우, 예를 들어, 데이터의 특정 기준으로 1차 정렬 후, 2차 정렬을 수행할 때 유용하다.

 

예시 : 병합 정렬 Merge Sort

병합 정렬은 안정적인 정렬 알고리즘으로, 정렬된 두 하위 배열을 병합할 때, 같은 값이 있을 경우 앞에 있는 요소를 먼저 병합해 상대적인 순서를 유지한다.

public class MergeSort {
    public static void mergeSort(int[] arr, int[] temp, int leftStart, int rightEnd) {
        if (leftStart >= rightEnd) {
            return;
        }

        int middle = (leftStart + rightEnd) / 2;
        mergeSort(arr, temp, leftStart, middle);
        mergeSort(arr, temp, middle + 1, rightEnd);
        mergeHalves(arr, temp, leftStart, rightEnd);
    }

    private static void mergeHalves(int[] arr, int[] temp, int leftStart, int rightEnd) {
        int leftEnd = (rightEnd + leftStart) / 2;
        int rightStart = leftEnd + 1;
        int size = rightEnd - leftStart + 1;

        int left = leftStart;
        int right = rightStart;
        int index = leftStart;

        while (left <= leftEnd && right <= rightEnd) {
            if (arr[left] <= arr[right]) {
                temp[index] = arr[left];
                left++;
            } else {
                temp[index] = arr[right];
                right++;
            }
            index++;
        }

        System.arraycopy(arr, left, temp, index, leftEnd - left + 1);
        System.arraycopy(arr, right, temp, index, rightEnd - right + 1);
        System.arraycopy(temp, leftStart, arr, leftStart, size);
    }
}