[C/C++] sort - 안정정렬/불안정정렬

🔷 안정정렬

: 동일한 값에 대하여 기존의 순서가 유지되는 정렬

🔷 불안정정렬

: 동일한 값에 대하여 기존의 순서가 뒤바뀔 수 있는 정렬

ex)

기존의 숫자 배열이 다음과 같이 구성되어 있다고 하자.
7 red
5 orange
2 purple
5 green

이 배열을 숫자에 대해 오름차순으로 정렬한다고 생각했을 때,

📌 안정정렬

안정정렬을 하게 되면 앞에 있던 5 orange와 뒤에 있던 5 green의 순서는 바뀌지 않는다.
2 purple
5 orange
5 green
7 red

---

📌 불안정정렬

그러나! 불안정정렬의 경우,
앞에 있던 5 orange와 뒤에 있던 5 green의 순서는 바뀔 수도 있고, 바뀌지 않을 수도 있다.

➔ 즉, 두 가지 경우 모두 될 수 있음

---

C++에서의 sort / stable_sort

C++에서, algorithm 헤더를 통해 sort 함수를 사용할 수 있다.

🔻 sort : 퀵정렬로 구현되어 있음 -> 시간복잡도 : O(nlogn)
🔻 stable_sort : 병합정렬로 이루어져 안정정렬임