[C++] STL sort 튜토리얼

STL sort 튜토리얼

•  2015년 10월 13일
 
•  hakgb11
 
•  댓글 (1개)
•  STL, 소트, sort, sort()

1. 정의

알고리즘 헤더파일에서 제공하는 STL로써 범위내에서 주어진 범위내에서 원소들을 정렬합니다. 이때 정렬하는 방식(오름차순, 내림차순 등등등)은 사용자가 정의할 수 있으며, 동일한 원소에 대해서는 그 순서가 보장되지 않습니다. 이때 std::sort는 숫자 뿐만 아니라 대소 비교가 가능한 모든 원소에 대해서 정렬을 할 수 있습니다. 즉 int 뿐만 아니라 char, string 역시 정렬이 가능하고, 사용자가 정의한 객체 역시 연산자 오버로딩('<')을 정의해주면 정렬이 가능합니다. 또한 동일한 원소에 대해서 그 원소들의 상대적 순서를 보장해 주는 라이브러리도 존재합니다.

자세한 내용은 여기를 참고해 주세요.

2. 특징

2개의, 혹은 3개의 argument를 필요로 하는데, 첫번째 두개의 argument는 iterator로써 정렬하는 범위를 나타냅니다. 이때 iterator는 random access와, 수정이 가능해야 합니다. 기본적으로 Strick week Ordering, 즉 두개의 객체를 비교해서 첫번째가 두번째보다 작으면 true 그렇지 않다면 false를 리턴합니다. 대부분 quick sort를 사용한다고 알려져 있지만 대부분의 컴파일러에서 다양한 방식의 정렬을 복합적으로 사용합니다. GCC의 경우 introsort와 원소의 개수가 적을 경우 insertion sort를 사용한다고 알려져 있습니다.

자세한 내용은 여기를 참고해 보세요.

3. 사용법

기본 사용법

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

배열 정렬

기본적으로 std::sort를 이용하면 오름차순 정렬이 수행됩니다.

소스예제

#include <iostream>
#include <algorithm>

using namespace std;

int main(){

    int arr[5];
    arr[0] = 0;
    arr[1] = 4;
    arr[2] = 3;
    arr[3] = 1;
    arr[4] = 5;
    sort(arr, arr + 5);

    for (int i = 0; i < 5; i++)
        cout << arr[i] << endl;

    return 0;
}

결과

0
1
3
4
5

정렬 오름차순(greater)

내림차순 정렬을 수행하기 위해서 fuctional 헤더에서 제공하는 less를 사용하는 방법입니다.

소스예제

#include <iostream>
#include <functional>
#include <algorithm>

using namespace std;

int main(){
    int arr[5];
    arr[0] = 0;
    arr[1] = 4;
    arr[2] = 3;
    arr[3] = 1;
    arr[4] = 5;

    sort(arr, arr + 5, greater<int>());

    for (int i = 0; i < 5; i++)
        cout << arr[i] << endl;

    return 0;
}

결과

5
4
3
1
0

vector의 정렬

숫자 뿐만 아니라 대소비교가 가능한 모든 변수형은 정렬이 가능합니다.

소스예제

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

using namespace std;

int main(){
    vector<char> v;
    v.push_back('c');
    v.push_back('b');
    v.push_back('e');
    v.push_back('a');
    v.push_back('g');

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

    for (int i = 0; i < 5; i++)
        cout << v[i] << endl;

    return 0;
}

결과

a
b
c
e
g

사용자 정의 객체 정렬 (global < operator)

연산자 오버로딩을 통해서 사용자 정의 객체를 정렬해 봅시다.

소스예제

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

using namespace std;

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

bool operator <(const Person &a, const Person &b){
    return a.age < b.age;
}

int main(){
    vector<Person> v;
    v.push_back(Person("MinJi", 22));
    v.push_back(Person("Kangho", 28));
    v.push_back(Person("Minho", 26));
    v.push_back(Person("Strange Yun", 25));
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++)
        cout << v[i].age  << ", " <<  v[i].name << endl;

}

결과

22, MinJi
25, Strange Yun
26, Minho
28, Kangho

객체 정렬 (클래스내 연산자 오버로딩)

소스예제

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

using namespace std;

class Person{
public:
    string name;
    int age;
    Person(string name, int age){
        this->name = name;
        this->age = age;
    }
    bool operator <(const Person &a) const {
        return this->age < a.age;
    }

};

int main(){
    vector<Person> v;
    v.push_back(Person("MinJi", 22));
    v.push_back(Person("Kangho", 28));
    v.push_back(Person("Minho", 26));
    v.push_back(Person("Strange Yun", 25));
    v.push_back(Person("JunEun", 40));
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++)
        cout << v[i].age  << ", " <<  v[i].name << endl;

}

결과

22, MinJi
25, Strange Yun
26, Minho
28, Kangho
40, JunEun

객체 정렬 (사용자 정의 함수)

이름을 기준으로 내림차순 정렬하는 사용자 정의 함수를 작성해봅니다.

예제소스

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

using namespace std;

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

bool cmp(const Person &a, const Person &b){
    return a.name > b.name;
}

int main(){
    vector<Person> v;
    v.push_back(Person("Ace", 22));
    v.push_back(Person("Luffy", 28));
    v.push_back(Person("Zoro", 26));
    v.push_back(Person("Robin", 25));
    v.push_back(Person("Brook", 40));
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < v.size(); i++)
        cout << v[i].age  << ", " <<  v[i].name << endl;
}

결과

26, Zoro
25, Robin
28, Luffy
40, Brook
22, Ace

STL Pair의 정렬

많이 쓰이는 STL의 pair을 sort함수로 정렬할 경우 기본적으로 pair의 첫번째 원소를 기준으로 정렬이 되고 첫번째 원소가 같을 경우 두번째 원소를 사용해서 비교하게 됩니다.

예제소스

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

using namespace std;

int main(){
    vector<pair<int, string> > v;
    v.push_back(pair<int, string>(20, "A_Jiwoo"));
    v.push_back(pair<int, string>(21, "B_Songju"));
    v.push_back(pair<int, string>(21, "C_Induk"));
    v.push_back(pair<int, string>(21, "D_SeungHyun"));
    v.push_back(pair<int, string>(20, "E_Soyen"));

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

}

결과

20, A_Jiwoo
20, E_Soyen
21, B_Songju
21, C_Induk
21, D_SeungHyun

4.Reference

CodeProject Cplusplus Wiki_introsort

출처 - https://www.acmicpc.net/blog/view/22