[C에서 C++로 넘어가기] - 5. 정렬하기 : sort

 

C++에서는 쉬운 정렬을 위해 sort함수가 지원됩니다.

C언어에서도 stdlib.h 헤더파일을 선언하여 qsort()를 사용할 수 있지만, C++의 sort() 함수는 이와는 조금 다릅니다.

---

sort

 

C++에서 sort()함수는 <algorithm> 헤더파일을 추가한 다음 사용할 수 있습니다.

이 sort 정렬 함수는 최악의 경우에도 O(nlogn)의 시간 복잡도를 가지는 intro sort 정렬 알고리즘을 이용합니다.

intro sort 알고리즘은 quick 정렬 알고리즘을 기반으로, heap sort와 insertion sort를 혼합해 만든 알고리즘이라고 합니다. quick 정렬의 경우는 최악의 경우 O(n^2) 시간복잡도를 가지므로, 더 빠르게 사용할 수 있다는 장점이 있네요.

 

sort 함수의 사용방법을 알아보겠습니다.

sort(start, end);
sort(start, end, compare);		// 사용자 정의 함수 compare 사용
sort(start, end, greater<자료형>());	// 내림차순
sort(start, end, less<자료형>());	// 오름차순 (default)

sort(arr, arr + n);			// 배열 arr에서 arr[0]~arr[n-1]까지를 내림차순 정렬

 

sort(start, end) 함수는 start부터 end 이전 까지의 인자를 오름차순으로 정렬해 줍니다.

내림차순으로 정렬하기 위해선 세 번째 인자에 greater<자료형>()을 추가해 주면 됩니다.

 

내림차순으로 정렬하는 예제는 아래 게시글을 참고해 주세요.

https://sirius7.tistory.com/84

 

세 번째 인자를 자세히 설명하면,

세번째 인자에는 원하는 정렬의 기준을 정의하여 그 기준으로 정렬을 하게 됩니다.

아래 예시를 확인해 주세요

#include <iostream>
#include <algorithm>
using namespace std;

bool compare(int x, int y) {
	return x > y;
}

int main() {
	int arr1[5] = { 5,3,2,1,4 };
	int arr2[5] = { 5,3,2,1,4 };

	sort(arr1, arr1 + 5, compare);
	sort(arr2, arr2 + 5, greater<int>());

	for (int i = 0; i < 5; i++) {
		cout << arr1[i] << " ";
	}
	cout << "\n";
	for (int i = 0; i < 5; i++) {
		cout << arr2[i] << " ";
	}

	return 0;
}

소스코드 실행결과

 

arr1은 compare()라는 함수를 기준으로 정렬했습니다. 실행 결과를 확인하면 greater<자료형>()을 이용해서 내림차순으로 정렬한 것과 같은 결과가 나온 것을 확인 가능합니다.

 

compare함수를 자세히 살펴보면, x > y가 참이면 1, 거짓이면 0을 반환하는 함수이므로,

x가 y보다 크도록 sort를 실시해라! 라는 뜻이 되어 내림차순으로 정렬되게 됩니다.

즉, 왼쪽 값(=x)이 오른쪽 값(=y)보다 큰 정렬을 하라는 것입니다.

 

자세한 예시를 확인하기 위해서는 아래 게시글을 참고해 주세요.

https://sirius7.tistory.com/86