[Algorithm] 불안정정렬 sort, 안정정렬 stable_sort

안정 정렬와 불안정 정렬

우선 안정정렬와불안정정렬이 무엇인지 알아봅시다.

안정정렬은 동일한 값에 대해 기존의 순서가 유지되는 정렬을 말하며 불안정정렬은 반대로 동일한 값에 대해 기존의 순서가 뒤바뀔 수 있는 정렬입니다.

아래 그림을 보며 이해를 해봅시다.

기존의 숫자배열은 스페이스 7, 하트 5, 하트 2, 스페이스 5로 구성되어 있습니다.

 

이를 숫자에 대하여 오름차순으로 정렬한다고 생각해봅시다.

이 때 안정정렬을 하게 되면 앞에 존재하던 하트 5와 뒤에 존재하던 스페이스 5의 순서는 바뀌지않음이 보장됩니다.

 

반대로 불안정정렬을 보도록 하겠습니다.

이 경우에는 하트 5와 스페이스 5의 순서가 바뀌었지만 불안정이라고 해서 항상 바뀌는 것은 아닙니다. 바뀔 수 도 있고 바뀌지 않을 수 도 있습니다.

C++의 sort 와 stable sort

C++ 를 비롯한 여러 언어에서는 sort 함수를 지원해줍니다.

C++ 같은 경우에서는 algorithm 해더를 include함으로서 sort함수를 사용할 수 있습니다.

이 때의 sort는 내부적으로 퀵정렬로 구현이 되어있습니다. 이는 시간복잡도 O(nlogn) 으로 빠르지만 불안정 정렬입니다.

따라서 안정정렬을 위한 함수도 지원해주는데 이는 stable_sort 입니다. 이는 내부적으로 병합정렬로 이루어져 있기 때문에 안정정렬입니다.

 

문제

https://programmers.co.kr/learn/courses/30/lessons/17686?language=cpp

프로그래머스

다음 문제는 안정정렬이 필요한 문제입니다.

문제의 지문 중 다음과 같은 구절을 확인할 수 있습니다.

두 파일의 HEAD 부분과, NUMBER의 숫자도 같을 경우, 원래 입력에 주어진 순서를 유지한다.

따라서 해당 문제는 정렬 시, sort가 아닌 stable_sort를 사용하여 문제를 해결해야 합니다.

 

해당 문제의 답은 아래 링크로 첨부합니다.

https://github.com/arkss/Algorithm/blob/master/programmers/%ED%8C%8C%EC%9D%BC%EB%AA%85%EC%A0%95%EB%A0%AC.cpp

arkss/Algorithm