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

실제 알고리즘 대회에서 정렬 문제가 나올 때 빠르게 풀기 위해 sort()를 사용해 간단하게 정렬을 구현한다.

 

sort()

• <algorithm> 헤더에 정의되어 있다.
• default 설정  => 오름차순으로 정렬
• 퀵 정렬을 기반으로 구현되어 있다. 
• 퀵 정렬과 달리 모든 경우에 시간 복잡도 O(N * logN)을 보장한다.
• sort(start, end, 정렬기준);

 

사용 예시

1) sort(arr, arr + n);                                     

    => 세번째 인자를 안 쓰면 default로 오름차순 정렬됨

 

2) sort(v.begin(), v.end());

    => 세번째 인자를 안 쓰면 default로 오름차순 정렬됨

 

3) sort(v.begin(), v.end(), greater<자료형>());     

    => 내림차순으로 정렬

 

4) sort(arr, arr + n, compare);                         

    => 함수를 지정해서 세번째 인자로 넣으면 정렬할 기준을 내 마음대로 지정할 수 있음

 

 

일반 배열 정렬 

#include<iostream>
#include<algorithm>

using namespace std;

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

                                                                    

정렬 기준을 사용자가 직접 함수를 정의해서 정렬

#include<iostream>
#include<algorithm>

using namespace std;

bool compare(int a, int b){
  return a > b;   // a가 b보다 클 때 우선적으로 출력하도록 함 (내림차순)
}

int main(){
  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++){
    printf("%d ",a[i]);
  }
}

 

실무에서 실제로 sort()를 사용하는 경우

- 실무에서는 알고리즘 문제에서처럼 숫자만 나열되어 있는 데이터는 거의 없고
  데이터들이 객체화 되어 있는 경우가 많기 때문에 객체를 비교해서 정렬하는 경우가 많음

#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; 
  }

  /*
  정렬 기준 : 점수가 작은 순서
  다른 학생(student)과 비교할 때 내 점수(this->score)가 더 낮다면 우선순위가 높다라는 뜻 
  => 점수가 작은 순서부터 출력하겠다는 말임
  */
  bool operator < (Student& student){
    return this->score < student.score;
  }

};

int main(){
  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 << " ";
  }
}

 

---

실제 알고리즘 문제에서 여러 개의 변수가 존재하는 상황에 "특정한 변수" 를 기준으로 정렬해야 할 때
실무에서처럼 클래스를 정의해서 푸는 방식은 빨리 풀어야 할 때는 유리하지 않다.

=> 일반적으로 빠른 코드 구현이 필요할 경우 페어(Pair) STL 라이브러리를 사용하는 것이 더 효율적이다.

 

pair STL 사용 예시

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

using namespace std;

int main(){
	vector<pair<int,string>> v;
	v.push_back(pair<int, string>(90,"김일병"));
	v.push_back(pair<int, string>(85,"김이병"));
	v.push_back(pair<int, string>(82,"김상병"));
	v.push_back(pair<int, string>(98,"김사병"));
	v.push_back(pair<int, string>(79,"김오병"));

	sort(v.begin(), v.end());
	for(int i = 0; i < v.size(); i++) {
		cout << v[i].second << " ";
	}
}

vector STL : 마치 배열과 같이 동작하는데, 배열을 보다 사용하기 쉽도록 개편한 자료구조

Pair STL    : 한 쌓의 데이터를 처리할 수 있도록 해주는 자료구조

 

 

변수가 3개일 때 "두 개" 의 변수를 기준으로 정렬해야 하는 경우

 

예를 들어 학생 이름을 기준에 맞게 정렬하는 상황이라고 가정하도록 하겠다.

학생 정보 : 이름, 성적, 생년월일

정렬 기준 : 학생의 이름을 성적 순서대로 나열 ( 단, 성적이 동일한 경우 나이가 더 어린 학생을 먼저 나열 )

 

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

using namespace std;

bool compare(pair<string, pair<int,int>> a, pair<string,pair<int,int>> b){
  if(a.second.first == b.second.first){
    return a.second.second > b.second.second;
  }else{
    return a.second.first > b.second.first;
  }
}

int main(){
  vector<pair<string, pair<int, int>>> v;

  v.push_back(pair<string,pair<int, int>>("김일병", make_pair(90, 19961001)));
  v.push_back(pair<string,pair<int, int>>("김이병", make_pair(97, 19940505)));
  v.push_back(pair<string,pair<int, int>>("김상병", make_pair(95, 19940101)));
  v.push_back(pair<string,pair<int, int>>("김사병", make_pair(90, 19910909)));
  v.push_back(pair<string,pair<int, int>>("김오병", make_pair(88, 19850303)));

  sort(v.begin(), v.end(), compare);

  for(int i = 0; i < v.size(); i++){
    cout << v[i].first << " ";
  }
}