불안정 정렬과 안정 정렬 (Stable Sort)

프로그래머스의 [3차] 파일명 정렬 문제에서 파이썬으로 푼 방식과 똑같이 C++로 문제를 푸는데, 계속 1, 2번을 제외한 테스트케이스가 모두 틀려 의문이 들었다. 질문하기 게시판을 읽어 보았더니, 보통 C++에서 사용하는 sort() 메소드가 불안정 정렬이라서 틀렸을 것이라고 한다. 글에서 말한대로 안정 정렬을 사용하여 푸니 바로 풀렸다.

 

알고리즘 문제를 풀며 알게 된 안정 정렬과 불안정 정렬. 이를 까먹지 않고자 다루어보려 한다.

---

1. 불안정 정렬이란?

불안정 정렬을 설명하기 전, 정렬의 개념부터 알고 가야 할듯하다.

정렬이란 데이터 요소를 특정 기준에 따라 순서대로 배치하는 과정을 말한다. 각 언어의 내장 정렬 함수는 기본적으로 숫자나 문자를 오름차순으로 정리하지만, 사용자의 정의 기준에 따른 커스텀 정렬을 할 수도 있다.

 

그렇다면 요소를 정렬시키는 것이 어떻게 불안정할 수 있다는 것인가?

불안정 정렬은 값의 원래 순서가 유지되지 않을 수도 있는 정렬 알고리즘을 의미한다. 이는 숫자나 문자와 같은 예시가 아닌, 값을 두 개 이상 가지고 있는 객체를 활용한 예시를 들면 이해가 쉬워질 것이다.

 

vector<int> numbers = {5, 3, 5, 4, 2};
sort(numbers.begin(), numbers.end(), [&](int a, int b)->bool { //오름차순 정렬
        return a < b;
    }
);

cout << "{";
for(auto& number : numbers) { //출력
    cout << number << " ";
}
cout << "}" << endl; //{2 3 4 5 5 }

위 코드를 보자. numbers 벡터에는 5가 두 개 있다. 이와 같은 원시(Primitive) 타입 같은 경우에는 정렬 후 3번째 인덱스에 오는 5가 원래 0번째 인덱스에 있었는지, 2번째 인덱스에 있었는지는 중요치가 않다.

 

vector<string> words = {"Apple", "Banana", "Train", "Book", "Dog"};
sort(words.begin(), words.end(), [&](string a, string b)->bool { //오름차순 정렬
        return a[0] < b[0];
    }
);

cout << "{";
for(auto& word : words) { //출력
    cout << word << " ";
}
cout << "}" << endl; //{Apple Book Banana Dog Train }

하지만 다음 코드와 같이 string 타입을 다루고 싶다면 어떨까?

각 단어의 첫 글자로 정렬을 하고, 첫 글자가 같으면 현재 벡터의 인덱스 순서를 유지하고 싶을 때, 불안정 정렬을 원래 순서를 유지시키지 않을 수가 있다.

 

Banana와 Book의 첫 글자는 ‘B’로 같으므로, 먼저 나온 Banana가 Book보다 앞에 있어야 하나, sort() 메소드와 같은 불안정 정렬 방식은 순서가 유지되지 않아 Book이 더 앞으로 나올 수가 있다는 것이다. 인덱스 순서를 유지하기 위해서는 pair나 struct를 만들어 인덱스 요소를 추가해 정렬 기준에 인덱스 순서를 추가 시킬 필요가 있다.

 

2. 안정 정렬이란?

반면 안정 정렬은 동일한 기준의 요소들의 원래 순서 유지를 보장해준다. 불안정 정렬의 단점에 해당하지 않는 정렬 알고리즘이라고 생각하면 되니, 이론적인 설명 없이 바로 예시를 들어가보자.

vector<string> words = {"Apple", "Banana", "Train", "Book", "Dog"};
stable_sort(words.begin(), words.end(), [&](string a, string b)->bool { //오름차순 정렬
        return a[0] < b[0];
    }
);

cout << "{";
for(auto& word : words) { //출력
    cout << word << " ";
}
cout << "}" << endl; //{Apple Banana Book Dog Train }

불안정 정렬에서 설명한 예시와 같은 코드이지만, sort() 메소드가 아닌 stable_sort() 메소드를 사용한 것에 대한 차이점이 있다.

일반적으로 Quick Sort와 Heap Sort, 그리고 Insertion Sort를 하이브리드로 사용해 정렬하는 sort()와 달리, Merge Sort를 기반으로 하는 stable_sort()는 sort()에 비해 속도는 느리지만 안정성을 보장한다. 그러므로 Banana 요소와 Book 요소는 기존 순서를 유지한 채 정렬이 될 수 있다.

 

3. sort()와 stable_sort()의 비교

불안정 정렬 메소드인 sort()와 안정 정렬 메소드인 stable_sort()의 차이를 비교해보자.

 

sort()

• 정렬 안정성: 불안정 정렬 (순서 유지 X)
• 시간 복잡도: 평균 O(N log N)
• 성능: stable_sort()보다 메모리 사용량이 더 적고, 속도가 빠름
• 사용 목적: 정렬 기준이 명확하거나, 정렬 요소가 원시 타입일 때

stable_sort()

• 정렬 안정성: 안정 정렬 (순서 유지 O)
• 시간 복잡도: 평균 O(N log N)
• 성능: sort()보다 메모리 사용량이 더 많고, 시간 복잡도는 같으나 속도가 약간 더 느림
• 사용 목적: 원래의 인덱스 순서가 중요할 때