C++ sort & stable_sort

sort는 불안정정렬이고 stable_sort는 안정정렬입니다.

이 두가지의 차이점을 먼저 말씀드리겠습니다.

배열이 다음과 같이 나와있을 수 있습니다.

배열 예시

이게 정렬 전 배열입니다.

같은 숫자는 자신의 앞과 뒤의 순서를 알아볼 수 있도록 색깔을 빨강(선) - 주황(후)로 하겠습니다.

일반적인 stable_sort(안정정렬)은 다음과 같이 정렬이 완성됩니다.

stable_sort 결과

순서가 바뀌지 않고 정렬이 완성이 됩니다.

 

하지만 정렬이 되지 않은 배열을 sort로 정렬하면 다음과 같이 됩니다.

sort 결과

위의 결과와 같이 먼저 왔다고 해서 배열의 앞순서로 온다는 보장이 없습니다.

그렇기에 불안정정렬이라고 합니다.

물론 78의 순서도 서로 달라질 수 있고 25의 앞, 뒤 순서가 올바르게 될 수도 있습니다.

 

이러한 요소를 잘 고려해서 코딩을 만들면 좋을 것 같습니다.

sort에서 사용되는 퀵정렬과 stable_sort의 머지소트의 비교는

제 블로그인 아래의 글에 간단히 나와있습니다.

https://daisy0461.tistory.com/32?category=841468 

퀵소트 VS 머지소트