stable_sort()와 sort() 차이 알아보기

배열이나 vector 원소를 정렬하는데 있어서 자주 사용되는 sort()

C++에는 stable_sort()라는 것도 있다.

📌 [C++] sort() 함수란?

[C++] sort() 함수란?

 

둘의 가장 큰 차이는 원소 순서를 보장 여부로 「안정성」이지 않을까 싶다.

• sort() 기존 순서를 보장하지 않는다.

• stable_sort() 기존 순서를 보장한다.

---

ex) ID를 기준으로 비교 정렬하지만 동일한 ID인 경우

      sort() 결과가 예상가 다르게 나올 수 있다.

 

예시 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct Node
{
       int ID;
       string name;
};

vector<Node> A, B;

bool compare(Node A, Node B)
{
       return A.ID < B.ID;
}

void printState(string str, vector<Node> v)
{
       cout << str;
       for (int i = 0; i < v.size(); ++i)
       {
              if (i % 10 == 0) puts("");
              cout << "(" << v[i].ID << ", " << v[i].name << ") ";
       }
       printf("\n\n");
}

int main()
{
       vector<Node> data =
       {
              {3, "-"}, {3, "-"}, {4, "-"}, {2, "-"}, {6, "-"},
              {3, "-"}, {5, "-"}, {4, "-"}, {2, "-"}, {2, "-"},
              {6, "-"}, {3, "-"}, {5, "-"}, {4, "-"}, {2, "-"},
              {6, "-"}, {3, "-"}, {5, "-"}, {4, "-"}, {2, "-"},
              {1, "A"}, {1, "B"}, {1, "C"}, {1, "D"}, {1, "E"},
              {1, "F"}, {1, "G"}, {1, "H"}, {1, "I"}, {1, "J"},
              {6, "-"}, {3, "-"}, {5, "-"}, {4, "-"}, {2, "-"},
              {6, "-"}, {3, "-"}, {5, "-"}, {4, "-"}, {2, "-"},
       };

       for (int i = 0; i < data.size(); ++i)
       {
              A.push_back(data[i]);
              B.push_back(data[i]);
       }

       sort(A.begin(), A.end(), compare);
       stable_sort(B.begin(), B.end(), compare);

       printState("sort 결과", A);
       printState("stabe_sort 결과", B);
}

 

stable_sort()는 처음 정렬되기 전에 주어진 순서가 보장됨을 확인할 수 있다.

---

정렬 알고리즘 중에서 인덱스가 변경될 수 있는 것으로는

(UnStable) Selection, Quick, Heap 정렬들이 있다.

반면에 Merge Sort는 Stable 한 특징이 있다.

 

• sort()는 내부적으로 퀵(Quick) 정렬이며

    stable_sort()는 합병 정렬(Merge Sort) 방식이다.

• "보통(?)"은 sort()가 stable_sort() 보다 빠르다고 하는데

    주어지는 데이터에 따라 속도와 안정성을 Trade-Off 하는 것 같다.

📌 PS시 어떤 정렬을 선택하는 것이 좋을까?   

📌 정렬 알고리즘 비교