Tutorial : STL Sort 1 ( 기본 사용법 ) timer 2s memory 1024MB

여태까지 우리는 선택정렬, 삽입정렬, 버블정렬 등 이중 for문을 써서 O(N²) 의 시간 복잡도로 배열을 정렬했다.

따라서, 정렬하려는 수의 개수가 10만 개 이상으로 매우 많다면 시간 초과가 발생한다.

이 문제에서 학습해볼 것은 O(N log N) 의 시간 복잡도로 배열을 정렬하는, 간단한 함수다.

바로 sort 함수다.

A = [3, 5, 2, 6, 4, 1]

A.sort()   # 리스트 A를 정렬된 상태로 바꾸는 코드

B = sorted(A)  # 리스트 A를 수정하지 않고, 리스트 A의 각 원소를 정렬된 상태로 B에 저장하는 코드

sort 함수는 #include <algorithm> 헤더를 추가하면 사용할 수 있다.

사용 방법은 매우 매우 간단하다.

배열 A 의 s 번 칸 부터 e 번 칸까지 정렬하고 싶다면, 아래처럼 써주면 된다. ( s ≤ e )

std::sort ( A + s , A + e + 1 ) ;

오른쪽 항에서 A + e + 1 이 됨에 주의하자.

단, 매번 앞에 std:: 을 붙이기 귀찮다는 단점이 있다.

이를 방지하기 위해서는 코드 초반에 using namespace std; 를 적어주면 된다.

이를 적어주면, 앞으로 std:: 은 생략해도 된다.

즉, sort 함수를 사용하기 위한 준비 과정은 아래와 같다.

#include <algorithm>        ←   sort() 함수를 쓰기 위한 헤더
using namespace std;       ←   이 코드를 추가하면 std::sort() 에서 std:: 를 생략하고 sort() 만 써도 된다.

이제 추가 예시를 들면 아래와 같다.

sort ( A + 3 , A + 7 );     ←  A[3] ~ A[6] 을 정렬하는 코드다.

sort ( A + 0 , A + 5 );     ←  A[0] ~ A[4] 을 정렬하는 코드다.

sort ( A , A + 5 );      ←  위와 마찬가지로, A[0] ~ A[4] 을 정렬하는 코드다. A + 0 은 A 로 써도 된다.

더 쉽게 이해하려면 아래 그림을 보자. 배열 A 가 아래처럼 주어져 있을 때,

sort ( A + 1 , A + 5 );

위 명령을 수행한다면,

A[1] ~ A[4] 만 정렬한다는 뜻이 되고, 최종 결과는 아래와 같다.

한 줄의 코드만으로 원하는 부분을 빠르게 정렬할 수 있다 !

필수 STL 함수 중 하나이니, 문법을 잘 외워두도록 하자.