[C++ STL] sort 함수

참고

https://www.youtube.com/watch?v=dq5t1woLJMw

하반기 코딩테스트 준비를 위해 sort 함수와 관련하여 공부한 내용을 정리한다.

다양한 정렬 알고리즘 및 STL에서 기본적으로 제공하는 sort 함수의 기본적인 특징은 (ex. 시간복잡도 O(NlogN)을 갖는 원리) 위의 채널에 있는 "정렬" 1, 2편 영상을 통해 확인할 수 있고,

이번 글에서는 위의 채널에 있는 두 영상을 보면서 나에게 좀 더 실전적인 측면에서 필요했던 내용을 정리하려고 한다.

1. sort 함수 사용
   sort 함수의 경우 인자로 시작지점과 종료지점을 필요로 한다. 이때, 종료지점은 엄밀히 얘기하면 배열 혹은 vetor를 벗어나는 메모리 주소를 가리킨다.
   (배열 혹은 vector의 유효주소+1 => 더이상 배열 혹은 vector를 가리키지 않는, 벗어난 주소)

   C++를 사용하는 경우, 동적선언과 같은 부분에서의 이점 때문에 많은 경우에서 배열 대신 vector 를 사용하게 된다.
   따라서 vector 자료구조에 대해 sort 함수를 사용하는 경우, 일반적으로 다음과 같이 사용할 수 있다.

   sort(a.begin(), a.end());

   혹은 a.begin() 함수는 배열의 첫 자료가 시작하는 주소이므로, 이를 활용하여 다음과 같이 선언할 수도 있다.

   //배열의 크기가 5로 가정
   sort(a.begin(), a.begin() + 5);

   만약, vector가 아니라 배열에 대해 sort 함수를 사용하는 경우에는, 배열에 대해 begin(), end() 함수를 사용할 수 없기 때문에 배열의 이름과 바로 위에 있는 성질을 활용하여 사용한다.

   int a[5] = {1, 3, 3, 2, 5};
   sort(a, a + 5);

2. tuple, pair형 자료구조에 대한 sort 함수
   tuple, pair형 자료구조와 같이 복수의 자료를 가진 자료구조에 대해, sort 함수는 각 자료에 대한 정렬 우선순위를 가지고 있다. 이는 다음과 같다.

   1) 앞에 있는 자료를 먼저 비교하여 정렬(ex. pair형의 경우 first를 먼저 비교하여 정렬)
   2) 만약 앞의 자료가 같으면 그다음 자료를 서로 비교(ex. first 자료가 동일하면 second를 비교 후 정렬)
   3) 자료를 더 갖는 경우 마찬가지 방식으로 반복&정렬
   

3. 비교 함수
   sort 함수는 함수의 기본적인 인자로 시작지점, 종료지점을 받지만, 이외에 비교 함수를 받을 수도 있다.
   이러한 특징은 사용자가 단순히 오름차순, 내림차순 외에 다양한 조건으로 배열을 정리하고자 할때 유용하게 사용될 수 있다.

   예를 들면, 크기가 7인 특정 배열에 대해 각 성분를 5로 나눈 나머지 순으로 정렬하는데, 만약 나머지가 같으면 성분의 크기가 큰 순서대로 정렬하려고 하면,
   이러한 경우, 비교 함수를 다음과 같이 구성하여 sort 함수의 인자로 입력하면 된다.

   bool cmp(int a, int b) {
   	if (a % 5 == b % 5) {
       	return a < b;
   	}
   
   	return a % 5 < b % 5;
   }
   
   int main() {
   	ios_base::sync_with_stdio(false);
   	freopen("input.txt", "rt", stdin);
   	int a[7] = { 1, 2, 3, 4, 5, 6, 7 };
   	sort(a, a + 7, cmp);
   
   	for (int i = 0; i < 7; i++) {
   		cout << a[i] << ' ';
   	}
   	cout << "\n";
   
   	return 0;
   }

   위의 코드를 실행하면 배열 a는 5, 1, 6, 2, 7, 3, 4로 정렬된다.

   특히, 3번 내용은 2번 내용과 함께 자유자재로 응용할 수 있으면 다양한 상황에서 매우 유용하게 활용될 수 있을 것으로 생각한다.

   하지만 이러한 sort 함수를 사용할 때 주의해야 할 점이 있다.
   

4. 주의사항

   1) 정렬 과정에서 두 값이 같은 경우에는 false를 반환하도록 구성해야 한다.

   즉, a와 b 중에서 대소 관계가 명확하지 않은 경우(a가 b보다 크면 크고, 작으면 작다는 판별)에는 false를 반환해야 한다.

   이전에 다른 문제를 풀다가 컴파일 에러를 해결하는 과정에서, 이와 비슷한 내용으로 구조체 내에서 연산자 오버로딩을 할때 지켜야 할 규칙을 봤는데,

   해당 규칙은 sort 함수에서 a와 b의 대소 관계를 비교할 때, a > b가 참을 반환하면 b > a는 거짓을 반환하도록 연산자 오버로딩을 정의해야 한다는 규칙이었다.

   즉, 두 성분을 바꿔서 비교한 경우와 원래대로 비교한 경우에 결과가 반드시 다르게 나와야 한다는(연산자 오버로딩 정의를 명확하게 해야한다는) 규칙이었는데,

   해당 규칙보다는 훨씬 간단한 표현인 것 같다.

   2) 비교 함수 정의시 call by reference로 정의하기

   위의 3번 예시에서 정의된 비교 함수는 call by value로 정의되어 있다. 비교 함수를 정의할 때, 위와 같이 call by value로 정의하면, 비교 함수(cmp)를 호출할 때마다 인자로 받은 데이터를 복사하게 된다. 이는 불필요한 연산을 가지면서 시간과 메모리를 소모하게 된다.

   따라서 이를 방지하기 위해, 비교 함수 내에 const와 참조자(&)를 선언하여 인자로 받는 데이터를 수정하지 않고 인자를 모두 call by reference로 사용하는 함수로 선언한다.
   이러한 주의사항을 반영하여 위의 3번 예시를 수정한 코드는 다음과 같다.

   bool cmp(const int& a, const int& b) {
   	if (a % 5 == b % 5) {
       	return a < b;
   	}
   
   	return a % 5 < b % 5;
   }
   
   int main() {
   	ios_base::sync_with_stdio(false);
   	freopen("input.txt", "rt", stdin);
   	int a[7] = { 1, 2, 3, 4, 5, 6, 7 };
   	sort(a, a + 7, cmp);
   
   	for (int i = 0; i < 7; i++) {
   		cout << a[i] << ' ';
   	}
   	cout << "\n";
   
   	return 0;
   }

   위와 같은 깨알 지식들이 유용하게 쓰일 날이 있으면 좋겠다.