C++ sort() 함수에 대해서 알아보자.

1. 정의 살펴보기

 

백준 단계별로 풀어보기 13장에 해당하는 정렬 단원에서는 algorithm STL에 속해있는 sort() 함수를 사용하는 문제가 등장한다.

우선 sort() 함수가 어떤 함수인지 먼저 알아보기로 했다.

 

cplusplus.com 에 제시된 sort() 함수의 사양

 

cplusplus.com 에서 제시된 sort() 함수의 사양이다. 차례로 살펴보자.

 

우선 sort 함수의 템플릿을 보면 변수를 2개 입력 받는 경우와, 3개 입력 받는 경우의 두 가지가 있다는 것을 알 수 있다.

 

 

이 녀석을 해석해보자.

 

1. [first, last) 범위에 있는 원소들을 '오름차순'으로 정렬한다.

2. 변수를 2개 입력 받는 경우는 < 연산자를 사용해 정렬하고, 변수를 3개 입력 받는 경우는 comp 변수를 사용해 정렬한다.

3. 동일한 원소의 경우 기존의 순서를 보장하지 않는다. (stable_sort 참조)

 

라고 되어있다. (stable_sort에 대해서는 다음 포스팅에서 알아보겠다.)

 

 

2. 구현해보기

(1) 오름차순 정렬 ( 백준  # 2751 )

정의에 따르면 defalut가 오름차순 정렬이기 때문에, 단순히 오름차순 정렬을 원한다면 정렬을 원하는 대상의 첫 주소와 끝 주소를 넣어준다면 깔끔하게 정렬이 된다.

sort(first, last) 와 같은 형태로 작성해주면 된다.

repl.it 에서 돌려보자.

오름차순으로 정렬하는 코드

그 결과

위와 같이 깔끔하게 나오는 것을 볼 수 있었다.

 

 

(2) 내림차순 정렬 ( 백준  # 1427 )

그렇다면 내림차순으로 정렬하려면, 내지는 다른 특이한 조건을 만족하도록 정렬하고자 한다면...

어떻게 하는 것이 좋을까?

해답은 역시 쉽게 예상할 수 있겠지만 3변수를 입력받는 템플릿을 사용하는 것에 있다.

세 번째 변수인 comp에 대한 설명

첫 주소와 끝 주소라는 직관적인 first, last 변수와는 다르게 comp 라는 변수를 어떻게 쓰면 좋을지 한 번 읽어보자.

 

범위 안의 두 원소를 비교하여, bool 형태의 값을 리턴하는 binary function이다.

리턴된 값은 "first argument로 들어온 값이 second로 들어온 값에 비해서 앞에 있어도 되는지"를 판단하는데 사용된다고 한다.

 

즉, comp에 들어가는 값은 bool 함수여야한다는 것을 알 수 있다. bool 값이 true라면 pass, false라면 swap이 일어난다.

아래 예시로 보다 구체적인 설명을 진행하겠다.

comp 함수

vector형태의 변수 V를 sort 한다고 가정해보자.

i < j인 i, j에 대해서, compare(V[i], V[j]) 를 수행하면, 아래와 같이 나올 것이다.

i) V[i] > V[j] 인 경우 : true 를 return

ii) V[i] < V[j] 인 경우 : false 를 return

i) 의 경우는 이미 올바른 순서이므로 pass, ii) 의 경우는 바꿔주고 싶으므로 swap 을 진행하는 것이다.

 

이 과정을 V의 시작부터 끝까지 진행해주도록 하려면 sort(V.begin(), V.end(), compare) 를 사용해주면 된다.

이 사실을 이용하여 내림차순으로 정렬하는 문제를 한 번 풀어보겠다.

역시 repl.it에서 돌렸다.

내림차순으로 정렬하는 코드

그 결과

 

깔끔하게 내림차순으로 정렬되는 것을 볼 수 있었다.

 

 

 

(3) 특이한 순서로 정렬 ( 백준  # 1181 )

백준 # 1131

 

위 문제를 보면, 여러가지 조건을 모두 만족시키는 정렬을 요구하고 있다.

(2) 내림차순 정렬 문제를 풀 때와 비교해서 신경써야 할 부분이 두 개 추가되었다.

하나는 compare 함수의 재설정이고, 다른 하나는 중복된 단어는 제거해야하는 것이다.

 

이 문제를 풀기 위해 내가 생각한 함수는 다음과 같다.

복잡한 조건을 만족시키는 comp 함수

 

아래는 완성된 코드이다.

복잡한 조건에 맞게 정렬하는 코드

정답이다!

 

중간에 등장하는 V.erase(unique(V.begin(), V.end()), V.end()); 는 중복된 값을 제거해주기위한 값인데, 여기서 설명하면 너무 길어지므로 향후에 다른 포스팅에서 다뤄보도록 하겠다.

 

 

 

3. 시간복잡도

cplusplus.com 에 제시된 시간복잡도

평균적으로 O(nlogn)을 따른다고 나와있다.

 

 

 

4. 마치며

이번 포스팅에서는 sort() 함수의 활용법에 대해서 알아보았다. 다만, sort() 함수 정의에 있던 3번 구문이 마음에 걸렸다.

"동일한 원소의 경우 기존의 순서를 보장하지 않는다." 라는 구문이다.

이에, 다음 포스팅에선 stable_sort()에 대해서 알아보는 시간을 가지도록 하겠다.

 

Sources

https://cplusplus.com/reference/algorithm/sort/

https://cplusplus.com/reference/algorithm/sort/

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

https://www.acmicpc.net/problem/1427

1427번: 소트인사이드

https://www.acmicpc.net/problem/1181

1181번: 단어 정렬