C++ sort 함수 제대로 사용하기(배열, 벡터)

* C++ sort함수란? 

: C++STL에서 제공하는 sort 알고리즘

 

- 헤더파일: <algorithm>

- 구문: sort(start, end); //start부터 end개를 오름차순(default)로 정렬한다.

- 내부는 Quick sort(퀵 정렬)로 구현되어 있다. 따라서 평균 시간 복잡도는 O(NlogN)을 가진다.

 

1) 함수 원형

template <typename T>
void sort(T start, T end);

template <typename T>
void sort(T start, T end, Compare comp);

: 3번째 인자 값(Compare comp)을 넣으면 오름차순, 내림차순 등으로 정렬할 수 있다. compare 함수는 true 인 경우를 기준으로 정렬한다. 

 

2) 배열(array) 사용할 때 예시

sort(arr, arr+n); //배열 전체를 오름차순으로 정렬할 때
sort(arr+i, arr+n); //arr[i]~arr[n]까지 오름차순으로 정렬할 때

배열의 내림차순 정렬은 아래처럼 비교함수를 구현해서 sort()함수의 3번째 인자로 넣어주면 된다.

#include <algorithm>
using namespace std; 

bool desc(int a, int b){ //비교함수 구현해서 sort()함수 인자로 넣어주기
  return a > b; 
} 

int main(void){ 
  int arr[10] = {5, 1, 3, 6, 2, 10, 4, 7, 8, 9}; 
  sort(arr, arr+10, desc); // 내림차순 정렬: 10 9 8 7 6 5 4 3 2 1
  
  return 0; 
}

arr 배열 범위 내의 값들에 대해 desc함수를 실행해서 true가 반환될 때 정렬을 실시하겠다는 말이다.

즉, a가 b보다 클 경우(true) sort를 실시해서 내림차순 정렬이 되게끔 해준다.

 

 

3) 벡터(vector) 사용할 때 예시

sort(v.begin(), v.end()); // 벡터 전체를 오름차순으로 정렬할 때
sort(v.begin() + i, v.end()); // v[i]~끝까지 오름차순으로 정렬할 때
sort(v.begin(), v.end(), greater<int>()); // 벡터 전체를 내림차순으로 정렬할 때

 

cf) 정렬관련 문제들

11650번: 좌표 정렬하기

10825번: 국영수