6. C++ STL sort() 함수 다루기

sort 함수는 C++ STL에서 제공하는 함수로써 정렬에 이용되며 <algorithm> 헤더를 include 하여 사용 할 수 있다.

 

sort() 함수는 기본적을 오름차순 정렬을 수행한다.

 

시간 복잡도는 nlogn 이다.

 

배열의 (시작점 주소, 마지막 주소 + 1)을 적으면 된다.

[begin, end) 범위로 정렬한다.

 

- 첫 번째 인자: iterator(or 포인터)에서 정렬을 시작 할 부분

- 두 번째 인자: iterator(or 포인터)에서 정렬을 마칠 부분

- 세 번째 인자: 정렬을 어떤 식으로 할 것인지 알려주는 함수 (compare)

 

세번째  인자를 compare 함수라고 많이들 하는데,

이 부분에는 bool형 함수나 혹은 수식(수식도 0 또는 1이 나오므로)을 넣어 줄 수 있다.

 

 

 

▼sort() 함수의 기본 사용법

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
	int a[10] = {9, 3, 5, 4, 1, 10, 8, 6, 7, 2};
	sort(a, a + 10);
	for(int i = 0; i < 10; i++) {
		cout << a[i] << ' ';
	}
}

▼compare 함수

#include <iostream>
#include <algorithm>

using namespace std;

bool compare(int a, int b) {
	return a < b;  
	//a가 b보다 작을 때 우선적으로 정렬을 하겠다.
	//a < b 일 때 true 값 전달. (오름차순)
	//a > b (내림차순) 
	//즉, sort함수는 기본적으로 오름차순을 내부적으로 포함. 
}

int main(void) {
	int a[10] = {9, 3, 5, 4, 1, 10, 8, 6, 7, 2};
	sort(a, a + 10, compare);
	for(int i = 0; i < 10; i++) {
		cout << a[i] << ' ';
	}
}

함수의 이름은 당연히  compare가 아닌 어떤 것이라도 상관 없다.
주의해야 할 점은 인자로 compare()가 아닌 compare를 넣어줘야 한다는 것.

 

 

▼ 데이터를 묶어서 정렬하는 방법

#include <iostream>
#include <algorithm>

using namespace std;

class Student {
public:
	string name;
	int score;
	Student(string name, int score) {  //생성자 
		this->name = name;
		this->score = score;  
	}  //생성자는 특정한 객체를 초기화 하기 위해 사용
	
	//정렬 기준은 '점수가 작은 순서'
	bool operator <(Student &student) {
		return 	this->score < student.score;
	}
		
};

int main(void) {
	Student students[] = {
		Student("나동빈", 90),
		Student("이상욱", 93),
		Student("박한울", 97),
		Student("강종구", 87),
		Student("이태일", 92) 
	};
	
	sort(students, students + 5);
	
	for(int i = 0; i < 5; i++) {
		cout << students[i].name << ' ';
	}
}

 

 

[동빈나 유튜브 - 알고리즘 강의 정리]