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

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

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

바로 sort 함수다.

파이썬 (Python)에서는 아래와 같이 정렬이 가능하다.

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

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

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

리스트이름.sort() 는 해당 리스트의 원소들을 정렬시키는 명령어로 반환되는 값이 없는 함수다.
sorted(리스트이름)는 해당 리스트를 수정하지 않고, 정렬된 값들로 이루어진 리스트를 반환하는 함수다. 이 경우 반환된 값을 변수에 저장하거나 바로 사용하지 않으면 아무일도 일어나지 않는 것처럼 보인다.

상황에 따라 두 방법 중 하나의 방법을 사용하여 정렬을 할 수 있다.

일부 부분만 정렬하고 싶다면 해당 부분만 슬라이싱하여 뽑아내는 형식으로 재구성이 가능하다.
입력 형식과 출력 형식을 보고 문제를 한 번 풀어보자.

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 함수 중 하나이니, 문법을 잘 외워두도록 하자.

#8551 upload 437 done 160 how_to_reg 149

Tutorial : STL Sort 1 ( Basic Usage ) timer 2s memory 1024MB

#8551

Tutorial : STL Sort 1 ( Basic Usage ) 2s 1024MB