sort () 함수

1. sort() 함수는 C++ STL에서 제공하는 함수로써 이 함수의 시간 복잡도는 nlogn입니다.

이 함수는 intro sort라는 정렬 방식을 바탕으로 구현되어 있다.

이 방식은 quick sort를 기반으로 heap sort와 insertion sort를 섞은 방식으로 최악의 경우 n^2의 시간 복잡도를 가지는 quick sort와는 달리, 최악의 경우에도 nlogn을 보장하는 정렬 알고리즘입니다.

 

2. 사용법은 <algorithm>헤더를 include한 뒤 sort(begin,end) 이렇게 사용하면 오름차순으로 정렬됩니다. 정렬 방식이 sort(begin,end)이지만 범위가 begin <= arr <end 이기에 종료 index가 아닌 배열의 크기를 넣어주셔야 합니다.

 

3. 배열 오름차순 정렬하기 

#include<algorithm>

int arr[10]={1,2,....9,10};
sort(arr,arr+10);

첫번째 인자 : 배열의 포인터 (begin)

두번째 인자: 배열의 포인터+배열의 크기(end) // end는 포함 안하기 때문에 종료 인덱스가 아닌 크기만큼 더해줘야함

 

4. 벡터 오름차순 정렬하기

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

int main(){
vector <int> x1;
x1.push_back(1);
x1.push_back(3);

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

5. 내림차순으로 정렬하기 

- 내림차순으로 비교하는 함수를 구현하고 , sort() 함수의 마지막 인자값으로 넣어주면 된다.

#include <algorithm>
using namespace std; 

bool desc(int a, int b){
	return a>b;
}

int main(){
	...
    sort(arr,arr+10,desc);
}