[c++]정렬 알고리즘 - sort 함수 사용하기_완전 정복

일반적인 코딩 테스트용 sort 함수 사용 방법에 대해 알아보겠습니다.

c언어와 달리 c++에서는 STL(Standard Template Library) sort 함수를 제공해주고 있습니다. 

더이상 힘들게 버블, 선택, 삽입, 퀵, 합병 등등의 함수를 직접 만들지 않고 편하게 쓰도록 합시다.

 

#include <bits/stdc++.h>

using namespace std;

int main(){

	int arr[5] = {5,4,3,2,1};
  sort(arr, arr+5);
	for(int i = 0; i<5;i++){
    cout<<arr[i]<<'\t';
  }
}

이때 sort 함수의 사용법은 정렬하고자 하는 첫번째 원소에서, 마지막 원소의 메모리 주소값을 입력하는 것입니다.

기본적으로 sort함수는 오름차순으로 정렬을 합니다. 

sort 함수의 장점은 우리가 커스텀으로 정렬의 기준을 정할 수 있다는 것입니다. 

 

#include <bits/stdc++.h>

using namespace std;

bool compare(int a, int b){
  return a > b;
}

int main(){

	int arr[5] = {5,4,3,2,1};
  sort(arr, arr+5, compare);
	for(int i = 0; i<5;i++){
    cout<<arr[i]<<'\t';
  }
}

bool 은 참/거짓을 반환하는 자료형입니다. compare 함수를 살펴보면 a가 b보다 클때 참, 즉 우선적으로 정렬을 실행한다는 의미입니다. 

여기서 compare는 내림차순 정렬을 의미합니다.

 

sort는 class, list, 구조체, vector  등등 다양하게 사용 할 수 있습니다.

 

코테에서는 아마 클래스를 사용할 확률이 적겠지만, 아무튼 중요한 개념이니 배워가시면 좋을 듯 합니다.

객체(클래스)에 담겨진 여러 변수들 중 특정 변수를 기준으로 정렬을 할 수 있습니다.

 

#include <bits/stdc++.h>

using namespace std;

class Info {
public:
  string name;
  int data;
  Info(string name, int data){
    this->name = name;
    this->data = data;
  }
  bool operator <(Info &info){
    return this->data < info.data;
  }

};

int main(){
  Info arr[] = {
    Info("a", 90),
    Info("b", 89),
    Info("c", 88),
    Info("d", 45)
  };
  sort(arr, arr+4);
  for(int i =0;i<4;i++){
    cout << arr[i].name <<' '<<arr[i].data<<'\n';
  }
}

여기서 Info 클래스 내에서 비교연산자 <를 오버라이딩 했습니다. 

코드를 살펴보신다면 쉽게 이해하실 수 있습니다.

 

하지만 실전 코딩 대회에서는 어떻게 해야할까요?

vector와 pair를 사용을 합니다.

#include <bits/stdc++.h>

using namespace std;

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

int main(){
  vector<pair<string,int>> v;
  v.push_back(pair<string,int>("a",90));
  v.push_back(pair<string,int>("d",10));
  v.push_back(pair<string,int>("c",70));
  v.push_back(pair<string,int>("b",80));
  
  sort(v.begin(),v.end(),compare);
  
  for(int i = 0;i<v.size();i++){
    cout<<v[i].first<<' '<<v[i].second<<'\n';
  }
  
}

숫자 기준으로 오름차순으로 정렬했습니다. 기본적으로 compare 함수를 정의하지 않는다면 pair에서 first값들을 비교하게 되어있습니다. 그래서 위의 소스코드에서는 일부로 second으로 비교했습니다.

# 참고로 v.begin 과 v.end함수의 반환값은 주소 메모리입니다.

 

다음은 조금 더 심화된 정렬을 해보겠습니다. 

만약 2개 이상의 변수를 기준으로 정렬을 해야한다면 어떻게 할까요?

흔히 점수가 같으면 이름을 사전순으로, 아니면 점수가 같으면 빠른 생일 순으로 등등 다양한 문제가 있습니다.

이때 이중pair 즉, pair 안에 pair를 사용하면 편리합니다.

#include <bits/stdc++.h>

using namespace std;

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

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

  v.push_back(pair<string, pair<int, int>>("a", pair<int,int>(90,1)));
  v.push_back(pair< string, pair<int, int>>("d", pair<int,int>(80,4)));
  v.push_back(pair< string, pair<int, int>>("c", pair<int,int>(70,3)));
  v.push_back(pair< string, pair<int, int>>("f", pair<int,int>(60,6)));
  v.push_back(pair< string, pair<int, int>>("e", pair<int,int>(60,5)));
  v.push_back(pair< string, pair<int, int>>("b", pair<int,int>(60,2)));
  v.push_back(pair< string, pair<int, int>>("aa", pair<int,int>(30,2)));
  sort(v.begin(),v.end(),compare);
  
  for(int i = 0;i<v.size();i++){
    cout<<v[i].first<<' '<<v[i].second.first<<' '<<v[i].second.second<<'\n';
  }
  
}

이처럼 이중 pair를 사용하면 3개까지 데이터를 한번에 관리를 할 수 있습니다. 

마지막 순자 기준으로 오름차순 정렬을 하되, 같은 수 가 나오면 앞의 숫자를 기준으로 오름차순으로 정렬입니다.

말로 설명하면 복잡할 수 있으니, 직접 코드를 보시고 이해하시면 좋을 듯 합니다.

 

하지만 4개 이상은 코드량이 더욱 늘어나고, 가시적으로 효율성이 떨어집니다. 

오히려 4개 이상은 클래스를 선언하셔서 코드를 구현하면 좀더 편할거 같습니다.

 

그럼 열공하시길