[c++] Sort 함수 정리

 

sort 함수는 알고리즘 문제를 풀 때 많이 사용하므로 그 사용법을 제대로 익혀두는 것이 좋다.

 

1. 특징

• <algorithm> 헤더에 포함되어 있다.
• 오름차순으로 정렬 된다. (Default)
• 숫자 뿐만 아니라 대소 비교가 가능한 모든 원소에 대해 정렬 가능하다.(int, char, string 등)
• 퀵 정렬(quick sort)을 기반으로 함수가 구현되어 있다.

2. 원형 및 예시

// default
template <class RandomAccessIterator>
  void sort (RandomAccessIterator first, RandomAccessIterator last);
  
// custom 
template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

 

예시 코드

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

using namespace std;

int main (){

    int arr[10] = {9, 1, 3, 2, 4, 5, 7, 8, 10, 6}; 
    
    /* 정렬 전*/
    for(int i=0;i<10; i++)
		cout << arr[i] << " ";

    sort(arr, arr + 10); //[begin(), end()) 오름차순(default) 정렬
    
    /*정렬 후*/
    for(int i=0;i<10; i++)
		cout << arr[i]<< " ";

	return 0;

}

결과 코드

> 9 1 3 2 4 5 7 8 10 6
> 1 2 3 4 5 6 7 8 9 10

2.1 내림차순 정렬

기본(default)는 오름차순이지만 functional 헤더의 greater를 이용해 내림차순으로 정렬하는 것도 가능하다.

 

예시코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional> //내림차순 정렬을 위해 필요 

using namespace std;

int main (){

    int arr[10] = {9, 1, 3, 2, 4, 5, 7, 8, 10, 6}; 
    
    /* 정렬 전*/
    for(int i=0;i<10; i++)
        cout << arr[i] << " ";
	
    /*정렬 후*/
    sort(arr, arr + 10, greater<int>());//[begin(), end())까지 내림차순 정렬
    
    for(int i=0;i<10; i++)
		cout << arr[i]<< " ";

    return 0;

}

결과 코드

> 9 1 3 2 4 5 7 8 10 6
> 10 9 8 7 6 5 4 3 2 1

2.2 Vector/STL Pair의 정렬

c++에서 제공되는 객체인 Vector와 STL Pair의 정렬에 대해서 알아보자.

 

Vector

Vector의 정렬은 앞선 리스트의 정렬과 매우 흡사하다.

List정렬에서는 가장 기본적인 숫자로 예시를 들었으므로 Vector에서는 문자로 예시 코드를 구성해보았다.

 

예시 코드

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

using namespace std;

int main (){

    vector<char> v;
    string s = "fcadeb";
	
    for(int i=0;i<s.length();i++)
        v.push_back(s[i]); 
	
    /* 정렬 전*/
    for(int i=0;i<s.length();i++)
        cout << s[i];
	 
    /*정렬 후*/
    sort(v.begin(), v.end());
    for(int i=0;i<v.size();i++)
		cout << v[i];
  
    return 0;

}

결과 코드

> fcadeb
> abcdef

 

STL Pair

STL Pair의 정렬은 첫번째 원소(first)를 기준으로 정렬되고,

첫 번째 원소가 같다면 두 번째 원소(second)로 정렬된다.

 

예를들면, 여러 연령대가 응시할 수 있는 시험에서 이름이 같다면 나이순으로 정렬하고자 한다.

그럴 때, 다음과 같이 코드를 짤 수 있다.

 

예시 코드 

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

using namespace std;

int main (){

    vector<pair<string,int>> v;
	
    //{이름, 나이}
    v.push_back({"sehee",24});
    v.push_back({"heejeong",28});
    v.push_back({"sumi",26});
    v.push_back({"yeahrim", 25});
    v.push_back({"sukyeong",29});
    v.push_back({"heejeong",25});
    v.push_back({"naeun",27});
    v.push_back({"heejeong",22});

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

	for(int i=0;i<v.size();i++)
		cout << v[i].first << "," << v[i].second << endl;
  
    return 0;

}

결과 코드

heejeong,22
heejeong,25
heejeong,28
naeun,27
sehee,24
sukyeong,29
sumi,26
yeahrim,25

3. 사용자 정의 객체 정렬

연산자 오버로딩을 이용해 사용자 정의 객체를 정렬할 수 있다.

 

예를들면, 등수를 매기기위해 점수에 따라 사용자가 정의한 Student객체를 정렬하고자 한다.

만약 점수가 같다면 이름순으로 정렬을 하여 출력해야한다.

 

예시 코드

#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;
		}
		
		//operator 오버로딩
		bool operator <(Student s) const{
			if(this->score == s.score)
				return this->name < s.name;
			else
				return this->score < s.score;
		} 
};

int main(){

	Student students[7] = {
		Student("효정", 95),
		Student("미미", 87), //same score 
		Student("유아", 71), 
		Student("승희", 98), 
		Student("지호", 87), //same score 
		Student("비니", 87), //same score
		Student("아린", 75),
	};
	
	sort(students , students+7);
	
	for(int i=0;i<7;i++)
		cout <<students[i].name << ":" << students[i].score <<"점"<<endl;
	
	return 0;
} 

결과 코드

> 유아:71점
> 아린:75점
> 미미:87점
> 비니:87점
> 지호:87점
> 효정:95점
> 승희:98점

결과 코드를 보면 점수에 따라 오름차순으로 정렬 되지만,

점수가 같은(미미, 비니, 지호)는 이름에 따라 오름차순으로 정렬된 것을 확인할 수 있다.

4. 사용자 정의 함수 정렬

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

//사용자 정의 함수
bool cmp(const Student &a , const Student &b){
	return a.name < b.name;
}

int main(){

	Student students[7] = {
		Student("효정", 95),
		Student("미미", 87),
		Student("유아", 71), 
		Student("승희", 98), 
		Student("지호", 87), 
		Student("비니", 87),
		Student("아린", 75),
	};
	
	sort(students , students+7 , cmp);//사용자가 정의한 함수로 sort하겠다는 것을 표현
	
	for(int i=0;i<7;i++)
		cout <<students[i].name << ":" << students[i].score <<"점"<<endl;
	
	return 0;
} 

> 미미:87점
> 비니:87점
> 승희:98점
> 아린:75점
> 유아:71점
> 지호:87점
> 효정:95점