[C++] sort (정렬)

개인 공부 후 자료를 남겨놓기 위한 목적이므로,
생략되거나 오류가 있을 수 있음을 알립니다.

이번 포스팅에서는 정렬에 대한 근본적인 알고리즘보다,

C++에서 정렬을 하는 메소드를 어떻게 사용하고, 해당 메소드에 대한 옵션을 어떻게 설정해야 하는지 적어보려 한다.

sort()

우선 sort 메소드를 사용하기 위해서는 코드의 헤더 부분에 algorithm 라이브러리를 추가해주어야 한다.

해당 헤더를 추가했다면, 이제 main과 같은 함수에서 정렬과 관련된 메소드들을 사용할 수 있게 된다.

C++에서는 내부적으로 해당 값이 32개 이하일 때는 삽입정렬을 사용하고,

32개 초과일 경우에는 힙정렬과 퀵소트를 사용한다고 한다. (대략 O(nlogn) 정도의 시간복잡도가 걸린다고 함.)

다음과 같은 int 자료형인 vect 데이터 가 있다고 하자,

정렬의 경우에는 다음과 같은 방식으로 정렬을 시작하고자 하는 주소와 끝 주소를 입력하여 해당 영역을 정렬을 하게 된다.

기본적인 방법은 주소를 입력하여 해당 영역을 정렬을 하는 것이지만,

가독성을 높인 방법이 있는데, 해당 방법은 다음과 같다.

+ string의 경우에는 가독성을 높인 방법을 사용하기 힘들 수도 있다.

그 때는 일반적인 주소값을 이용한 방법을 사용하면 되고,

vector의 경우에는 처음과 끝의 주소값을 가리치는 메소드인 begin()과 end()를 사용하면 된다.

정렬을 구분지으면 보통 3가지 방법으로 나누어볼 수 있다.

해당 방법들에 대하여 나누어 알아보도록 하자.

우리가 위에서 알아보았던 방법이 오름차순으로 배열을 정렬하는 방법이다.

sort 메소드 3가지 인자를 가지는데,

1, 2번째 인자의 경우 정렬하고자 하는 배열의 처음과 끝 영역의 주소값

마지막 인자의 경우에는 정렬 조건을 의미한다. 3번째 인자가 아무 값도 가지지 않았을 경우

less<int>, 즉 오름차순을 기본값으로 가지게 된다.

만약 배열이 int가 아닌 char라면 들어가는 값을 바꾸어 주면 된다.

(string의 경우에는 char로 설정)

내림차순의 경우에는 3번째 인자를 greator<int> 로 설정해주면 된다.

다중 조건 정렬의 경우에는 3번째 인자를 직접 만들어 사용한다.

예를 들어 설명하자면,

만약 배열을 2가지 조건으로 정렬하고자 한다.

이 두가지 조건으로 compare 함수를 만들고 3번째 인자로 넣어주면 된다.

구조체의 경우에는 내부에 가지고 있는 값들이 여러개이기 때문에 일반적인 sort와 같은 사용이 불가능하다.

따라서 compare를 다음과 같은 형식으로 만들어 주면 구조체를 정렬할 때, 특정 인자를 기준으로 정렬이 가능하다.