C++ STL sort() 함수

STL sort() 함수

헤더파일에서 제공하는 STL로서 주어진 범위 내에서 원소들을 정렬한다. 이때 정렬하는 방식을 사용자가 정의할 수 있고, 동일한 원소에 대해서는 그 순서가 보장되지 않는다. std::sort는 숫자 뿐만 아니라 대소 비교가 가능한 모든 원소에 대해서 정렬을 수행할 수 있다. 즉 int뿐 아니라 char, string 역시 정렬이 가능하며 사용자가 정의한 객체 역시 연산자 오버로딩을 정의하면 정렬이 가능하다.

특징

2개 혹은 3개의 argument를 필요로 하는데, 첫 번째 두 개의 argument는 iterator로서 정렬하는 범위를 나타낸다. sort(start, end)
퀵 정렬을 기반으로 함수가 구현되어 있다. 평균 시간 복잡도 : O(NlogN)
세 번째 argument를 넣지 않으면 default로 오름차순 정렬이 수행된다.
사용자 정의 함수를 만들어 세 번째 인자로 넣어 정렬 기준을 정의할 수 있다.
기본적으로 두 개의 객체를 비교해서 첫 번째가 두 번째보다 작으면 true, 아니면 false를 반환한다.

예제

default - 오름차순 정렬

#include <iostream>
#include <algorithm>

using namespace std;

void printArray(int a[], int n) // 배열 출력 함수
{
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << endl;
}

int main(void)
{
	int arr[10] = { 9, 1, 3, 2, 5, 4, 8, 6, 10, 7 };
	sort(arr, arr + 10);
	printArray(arr, 10);
}

출력

내림차순 정렬
내림차순 정렬은 세 번째 인자로 함수를 정의하여 사용할 수도 있고, 헤더파일에 선언되어 있는 greater<자료형>() 을 전달하여 내림차순으로 정렬을 수행할 수 있다.
(less<자료형>()은 오름차순 정렬을 해주지만 default와 동일하므로 생략한다.)

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <ctime>

using namespace std;

void printArray(vector<int> &a, int n) // 배열 출력 함수
{
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << endl;
}

bool desc(int a, int b) // 내림차순 정렬을 수행할 비교 함수
{
	return a > b;
}

int main(void)
{
	srand((int)time(NULL)); // 시드 값 설정

	vector<int> vec;
	int vsize = 10;

	for (int i = 0; i < vsize; i++)
		vec.push_back(rand() % 10 + 1); // 벡터에 1 ~ 10의 난수 삽입
	// N ~ (M+N-1) 까지 난수 생성 : rand() % M + N

	printArray(vec, vsize);
	sort(vec.begin(), vec.end(), greater<int>()); // [vec.begin(), vec.end()) 내림차순 정렬
  // greater<int>() 대신 desc를 넣어도 같은 결과
	cout << endl;
	printArray(vec, vsize);
}

출력

기준을 지정하여 정렬 - compare함수

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Student
{
public:
	string name;
	int age;
	int score;
	Student(string name, int age, int score)
	{
		this->name = name;
		this->age = age;
		this->score = score;
	}
};

void printStudent(vector<Student> &vec, int n) //  출력 함수
{
	for (int i = 0; i < n; i++)
		cout << "[ 이름 : " << vec[i].name << ", 나이 : " << vec[i].age << ", 점수 : " << vec[i].score << " ]" << endl;
	cout << endl;
}

bool compare(Student a, Student b) // 내림차순 정렬을 수행할 비교 함수
{
	if (a.score == b.score) // 점수가 같으면 -> 나이가 적은 순
		return a.age < b.age;
	else // 점수가 다르면 -> 점수 높은 순(내림차순)
		return a.score > b.score;
}

int main(void)
{
	vector<Student> vec;
	int vsize = 5;

	vec.push_back(Student("kwon", 25, 100));
	vec.push_back(Student("kim", 24, 88));
	vec.push_back(Student("shin", 29, 97));
	vec.push_back(Student("jung", 27, 75));
	vec.push_back(Student("park", 22, 88)); // 점수가 같으면 나이가 적은 순

	printStudent(vec, vsize);
	sort(vec.begin(), vec.end(), compare);
	cout << endl;
	printStudent(vec, vsize);
}

출력

연산자 오버로딩을 통한 정렬(operator overloading)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Student
{
public:
	string name;
	int age;
	int score;
	Student(string name, int age, int score)
	{
		this->name = name;
		this->age = age;
		this->score = score;
	}

	// 연산자 오버로딩 '<' (클래스 내부)
	bool operator <(Student& student)
	{
		return this->age < student.age; // 나이 오름차순으로 정렬
	}
};

void printStudent(vector<Student>& vec, int n) //  출력 함수
{
	for (int i = 0; i < n; i++)
		cout << "[ 이름 : " << vec[i].name << ", 나이 : " << vec[i].age << ", 점수 : " << vec[i].score << " ]" << endl;
	cout << endl;
}

int main(void)
{
	vector<Student> vec;
	int vsize = 5;

	vec.push_back(Student("kwon", 25, 100));
	vec.push_back(Student("kim", 24, 88));
	vec.push_back(Student("shin", 29, 97));
	vec.push_back(Student("jung", 27, 75));
	vec.push_back(Student("park", 22, 88));

	printStudent(vec, vsize);
	sort(vec.begin(), vec.end());
	cout << endl;
	printStudent(vec, vsize);
}

출력

참조
https://www.acmicpc.net/blog/view/22
https://hongku.tistory.com/153
https://blockdmask.tistory.com/178

C/C++

STL sort() 함수

특징

예제

FEATURED TAGS

FRIENDS