[C++] Sort

부가설명없이 코딩테스트에 활용하기 위한 정리

STL의 Sort() 함수

• < algorithm> 헤더파일에 포함된 함수

• 퀵정렬기반으로 구성되어있음

• nlogn의 시간복잡도

• 원형

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

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

세번째 인자 생략 시 오름차순으로 정렬된다.

사용자 지정 비교함수

자료형에 따라 다른 함수를 쓰는것이 아니라, 비교함수를 직접 인자로 넣어 세밀한 조정을 할 수 있다.

• sort(T start, T end) : default 오름차순
• sort(T start, T end, greater<T>()) : 내림차순
• sort(T start, T end, compare) : 사용자 지정 비교함수

예시

반환형은 bool형을 사용한다. 퀵정렬의 원리이므로,
두 인자를 집어넣고,
true를 반환할 시 전달한 인자의 순서가 바뀌지 않고,
false를 반환할 시 그 인자의 순서를 바꾼다.

typedef struct BJ1931
{
     int start;
     int end;
}time;

//true 반환되면 ab순서가 안바뀜
bool compare(time a, time b)
{
     if(a.end == b.end)
          return a.start < b.start; //그냥 부등호 방향대로 작은게 앞으로 오겠다는 뜻
     else
          return a.end < b.end;
}


sort(arr,arr+n,compare);

백준1931 회의실 배정 中

위와 같이 사용되므로 구조체 뿐만아니라, pair, map 등 모든 자료형에 대하여 그에 맞게 적절히 compare 함수를 작성하여 적용시키면 된다.

start, end

저장된 위치, 즉 주소값에 대하여 정렬을 해주는 원리이므로 정렬하고 싶은 자료형의 범위를 주소값으로 전달해주어야한다.

이는 배열의 부분에 한해서 정렬을 할수도 있다는 의미가 된다

• 배열
  sort(배열명+0 , 배열명+n)
• vector
  sort(v.begin(), v.end());