정렬

일반적으로 정렬(Sorting)은 컨테이너의 요소들을 논리적인 순서로 재배열하는 개념입니다.

정렬은 함수를 통해 데이터에 적용되는 가장 기본적이고 필수적인 기술 중 하나입니다. 즉, 정렬을 사용하면 일련의 요소들을 우리가 원하는 특정한 방식의 논리적 순서에 따라 배치할 수 있습니다.

정렬 알고리즘은 데이터를 조작하는 데 도움을 줄 뿐만 아니라, 많은 수학적 및 코딩 문제를 해결하는 데에도 도움을 줍니다.

*이러한 메서드들을 사용하려면 C++ 파일 상단에 #include <algorithm>을 사용하여 algorithm 헤더 파일을 포함해야 합니다.

데이터 정렬에 사용되는 STL 알고리즘 라이브러리의 내장 함수들에 대해 배우게 될 것입니다. 
우리가 공부할 세 가지 함수는 다음과 같습니다:

• sort()
• is_sorted()
• partial_sort()

sort 메서드

STL의 sort() 메서드는 주어진 범위의 내용을 정렬합니다. 이 메서드는 시작 반복자(iterator)와 끝 반복자가 필요하며, 해당 범위 내의 요소들을 오름차순으로 정렬합니다.

두 가지 버전으로 사용할 수 있습니다:

• sort(starting_iterator, ending_iterator) - 반복자로 정의된 범위를 오름차순으로 정렬합니다.
• sort(starting_iterator, ending_iterator, comparing_function) - 반복자로 정의된 범위를 정렬하되, 세 번째 매개변수로 주어진 함수를 기반으로 정렬합니다.

vector<int> numbers = {3, 5, 1, 2, 4};

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

for(auto i = numbers.begin(); i != numbers.end(); i++)
	cout << *i << " ";

Output:
1 2 3 4 5

위의 코드에서 볼 수 있듯이, sort() 메서드가 벡터를 오름차순으로 정렬했습니다.

bool compare(int a, int b)
{
	return a > b; // return 1 if a is greater than b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4};
	
	sort(numbers.begin(), numbers.end(), compare);
	
	for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
5 4 3 2 1

여기서 sort 메서드의 두 번째 버전을 어떻게 사용했는지 확인할 수 있습니다. a가 b보다 크면 true를 반환하도록 compare() 함수를 생성했습니다. 이를 통해 벡터를 내림차순으로 정렬할 수 있습니다.

is_sorted 메서드

is_sorted() 메서드는 주어진 범위가 정렬되어 있는지 여부에 따라 true 또는 false를 반환하는 STL 함수입니다. 

is_sorted() 메서드 역시 sort() 메서드와 마찬가지로 두 가지 버전이 있습니다:

• is_sorted(starting_iterator, ending_iterator) - 두 반복자로 정의된 범위가 오름차순으로 정렬되어 있는지 확인하여, 맞으면 true를, 그렇지 않으면 false를 반환합니다.
• is_sorted(starting_iterator, ending_iterator, comparing_function) - 두 반복자로 정의된 범위가 정렬되어 있는지 확인하되, 비교 함수를 기반으로 확인합니다.

vector<int> numbers = {3, 5, 1, 2, 4};

cout << is_sorted(numbers.begin(), numbers.end()) << endl;

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

cout << is_sorted(numbers.begin(), numbers.end());

Output:
0
1

bool compare(int a, int b)
{
	return a > b; // return 1 if a is greater than b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4};
	
	cout << is_sorted(numbers.begin(), numbers.end(), compare) << endl;
	
	sort(numbers.begin(), numbers.end(), compare);
	
	cout << is_sorted(numbers.begin(), numbers.end(), compare);

Output:
0
1

partial_sort 메서드

partial_sort() 메서드는 주어진 범위 내 요소들의 앞부분만 정렬하고 나머지 요소들은 처음 상태 그대로 둡니다. 
이 또한 두 가지 버전이 있습니다:

• partial_sort(start, middle, end) - start부터 end까지의 범위를 정렬하되, 시작 반복자부터 중간 반복자까지의 요소는 오름차순으로 정렬되고 중간 반복자부터 끝 반복자까지의 요소는 처음 상태 그대로 남겨둡니다.
• partial_sort(start, middle, end, compare) - start부터 end까지의 범위를 정렬하되, start부터 middle까지의 요소는 비교 함수를 기반으로 정렬되고 middle부터 end까지의 요소는 처음 상태 그대로 남겨둡니다.

vector<int> numbers = {3, 5, 1, 2, 4, 10, 7};

partial_sort(numbers.begin(), numbers.begin() + 4, numbers.end());

for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
1 2 3 4 5 10 7

bool compare(int a, int b)
{
	return a > b; // return 1 if a is greater than b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4, 10, 7};
	
	partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end(), compare);
	
	for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
10 7 5 1 2 3 4

보시다시피 partial_sort() 메서드는 조금 다르게 작동하지만, 너무 신경 쓰지 마세요. 부분 정렬을 사용할 일은 드뭅니다. 

지금은 정렬이 무엇인지 기억하고, sort()와 is_sorted() 메서드를 정확히 기억하며 사용하는 연습을 하세요.