Sort 정렬 알고리즘 C++

C++ STL에 존재하는 sort 알고리즘에 대해서 간단히 정리 해보겠습니다.

먼저 C++ STL에 존재하는 sort 알고리즘의 내부 동작에 대해서 말씀드리면... 바로 Quick Sort로 동작하는 것을 알 수 있습니다.

Quick Sort는 Merge Sort와 주로 비교되며 Pivot을 정하고 Pivot을 기준으로 정렬하는 특징을 가지고 있습니다. (빅오는 평균 NlogN 입니다.)

상대적으로 알고리즘 작성이 쉬운 선택, 삽입 정렬 등에 비해 좋은 성능을 가지고 있고 Quick Sort보다 더 효율적인 특수 정렬 알고리즘을 묻는 문제가 아닌 이상 대부분의 정렬 문제를 해결할 수 있습니다.

sort 알고리즘의 설명은 C++을 사용하시는 분들은 주로 배열보다 vector를 많이 사용하기 때문에 vector를 기준으로 진행하겠습니다.

sort 알고리즘을 사용하기 위해 가장 먼저 해주셔야 하는 부분은

#include <algorithm> 헤더파일의 추가 입니다!!!

다음으로 사용 부분은 sort 함수에 오버로딩이 되어있기 때문에 나누어 정리했습니다.

1. sort(begin,end)

먼저 가장 기본적인 sort 문입니다. 사용 방법은 정말 간단합니다.

sort 함수에서 2 개의 매개변수를 가지는 경우 입니다.

sort(vector의 시작 위치,vector의 마지막 위치)

로 정의 됩니다.

위 소스 코드를 보시면 먼저 data라는 vector를 만든 후 5,9,2 순으로 값을 insert 했습니다. 때문에 처음에 벡터 내에 데이터는 5, 9, 2 순으로 입력되지만,

sort알고리즘을 통해서 2,5,9 순으로 정렬 되는 것을 확인할 수 있습니다.

sort의 매개변수로는

data 벡터의 처음 위치를 나타내는 data.begin()

data 벡터의 마지막 위치를 나타내는 data.end()

를 입력했습니다.

이로 인해 data 벡터의 처음 부터 끝까지 값들 즉 5부터 2까지의 모든 숫자가 정렬 대상이 되고 정렬 결과 2,5,9의 출력결과를 확인 가능합니다.

2. sort(begin,end,bool 함수)

이번에는 sort의 매개변수가 3개인 경우입니다.

먼저 첫 번째 매개변수와 두 번 째 매개변수는 sort의 매개변수가 두 개인 경우와 같습니다.

세 번째 매개변수의 경우 bool 자료형을 리턴하는 함수가 주로 사용 됩니다.

여기서 함수는 정렬 기준을 나타내는 함수 입니다.

매개 변수가 두 개인 sort의 경우 항상 범위 내의 데이터를 오름차순으로 정렬하게 됩니다.

하지만 정렬 문제를 해결하기 위해서는 다양한 정렬이 요구되는 순간이 있습니다.

예를들어 내림차순으로 정렬이 필요한 순간이 있고 pair<int,int>, unordered_map<int,int>와 같이 정수 하나가 아닌 두 개 이상의 데이터가 포함된 배열, 해시, 클래스 객체 등의 정렬을 진행해야 하는 경우도 존재합니다. 마지막으로 두 개 이상의 변수를 가지고 있는 객체를 정렬할 때 기준이 되는 변수를 설정하고 만약 해당 변수의 값이 같다면 객체 내에 존재하는 다른 변수를 통해 정렬하는 것 까지 정렬 기준을 개발자 입맞에 맞게 수정할 수 있습니다.

그럼 매개변수가 3개인 sort 함수의 사용을 간단하게 예를들어 정리하겠습니다.

예는 간단 합니다. 

first와 second라는 두 개의 변수를 가지고 있는 클래스의 객체를 저장하는 vector를 정렬하는 예시 입니다.

(이 때, first를 기준으로 내림차순으로 정렬하고 만약 first의 값이 같다면 second를 기준으로 오름차순으로 정렬합니다.)

cmp 함수는 두 개의 매개변수를 가지며 이 때 매개변수의 데이터타입은 sort가 적용되는 데이터의 데이터 타입과 같습니다.

함수의 정의는 간단합니다.

return 부분에 내림차순을 원하면 좌측항(t1)>우측항(t2)인 경우 true를 반환해주면 되고

반대로 오름차순으로 정렬을 원하는 경우 좌측항(t1)<우측항(t2)의 경우 true를 반환해주도록 작성하면 됩니다.

위의 cmp함수는 first를 기준으로 내림차순 정렬 만약 first가 같다면 second를 기준으로 오름차순으로 정렬을 진행합니다.

sort알고리즘을 진행한 결과 first 내림차순 기준으로 test2가 가장 앞에 오게되고 first가 같은 test1, test3은 second 오름차순 기준을 바탕으로 test3, test1 순으로 정렬 됩니다.

이상으로 C++ STL sort에 대한 정리를 마치겠습니다.

다양한 알고리즘 문제를 해결하는데 C++ 에서 제공하는 sort함수는 매우 유용하기 때문에 알아두시면 정말 좋습니다~!

감사합니다~~!!!