[C++] sort algorithm 정리 및 예시

0. sort algorithm

• sort 알고리즘은 <algorithm> 헤더파일에 속해있습니다.

• sort(start, end)를 이용하여 [start, end) 의 범위에 있는 인자(element)를 오름차순(default)으로 정렬해주는 함수 입니다.
  start를 포함하고 end를 포함하지 않는 구간. (iterator를 생각하면됩니다.)

• quick sort(퀵 정렬)을 기반으로 함수가 구현되어있어, 평균 시간복잡도는 n log n 입니다.
  따로 quick sort를 구현할 필요 없이 C++ STL에서 제공해주는 sort 함수를 이용하면 편리하게 정렬 할 수 있습니다.

1. 원형 및 사용법

• 원형

template <typename T>
void sort(T start, T end);

template <typename T>
void sort(T start, T end, Compare comp);

을 가지고 있으며

3번째 인자를 넣지 않으면 default로 오름차순으로 정렬이 됩니다.

3번째 인자에 사용자가 정의한 함수를 기준으로 정렬을 할 수 있습니다. (이항조건자를 이용할 수도 있습니다.)

• sort(arr, arr+n);

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

• sort(v.begin(), v.end(), compare);                //사용자 정의 함수 사용

• sort(v.begin(), v.end(), greater<자료형>());    //내림차순 (Descending order)

• sort(v.begin(), v.end(), less<자료형>());        //오름차순 (default = Ascending order)

 

2. 예제

• 예제에서는 default sort 하는법, 이항조건자를 이용한 sort 내림차순, compare 함수를 만들어서 sort 사용하는법, 연산자 오버로딩을 사용해 sort하는 방법을 알아보겠습니다. 

 

- 예제 1) 배열 sort (default - 오름차순)

#include<iostream>

#include<algorithm>

using namespace std;

void Print(int *arr){

    cout << "arr[i] : " ;

    for(int i=0; i<10; i++){

        cout << arr[i] << " ";

    }

    cout << endl;

}

int main(void){

    int arr[10] = {3, 7, 2, 4, 1, 0, 9, 8, 5, 6};

    Print(arr); //정렬 전 출력

    sort(arr, arr+10); //[arr, arr+10) default(오름차순)로 정렬

    Print(arr); //정렬 후 출력

    

    return 0;

}

 

 

> 출력결과

 

 

- 예제 2) vector container sort (내림차순)

#include<iostream>

#include<algorithm>

#include<vector>

#include<ctime>

using namespace std;



void Print(vector<int> &v){

    cout << "vector : " ;

    for(int i=0; i<10; i++){

        cout << v[i] << " ";

    }

    cout << endl;

}



int main(void){

    srand((int)time(NULL)); //난수생성을 위해

    

    vector<int> v;

    int n = 10;

    

    for(int i=0; i<n; i++){ //vector에 1의자리 숫자를 임의로 삽입

        v.push_back(rand() % 10);

    }

    Print(v); //정렬 전 출력

    sort(v.begin(), v.end(), greater<int>()); //[begin, end) 내림차순으로 정렬

    Print(v); //정렬 후 출력

    

    return 0;

}

 

 

> 출력결과

- 예제 3) compare 함수를 만들어서 sort

#include<iostream>

#include<algorithm>

#include<vector>

#include<ctime>

using namespace std;





class Student{

public:

    string name;

    int age;

    Student(string name, int age):name(name),age(age){}

    

};





void Print(vector<Student> &v){

    cout << "Student : " ;

    for(int i=0; i<5; i++){

        cout << "[" << v[i].name << ", " << v[i].age << "]";

    }

    cout << endl;

}



bool compare(Student a, Student b){

    if(a.name == b.name){   //이름이 같으면, 나이가 적은순

        return a.age < b.age;

    }else{                  //이름 다르면, 이름 사전순

        return a.name < b.name;

    }

    

}

int main(void){

    vector<Student> v;

    

    v.push_back(Student("cc", 10));

    v.push_back(Student("ba", 24));

    v.push_back(Student("aa", 11));

    v.push_back(Student("cc", 8));  //cc는 이름이 같으니 나이 기준 오름차순 예시

    v.push_back(Student("bb", 21));

    

    Print(v); //정렬 전 출력

    sort(v.begin(), v.end(), compare); //[begin, end) compare 함수 기준 정렬

    Print(v); //정렬 후 출력

    

    return 0;

}

 

 

> 출력결과

 

- 예제 4) 연산자 오버로딩(operator overloading) 이용한 sort

#include<iostream>

#include<algorithm>

#include<vector>

#include<ctime>

using namespace std;





class Student{

public:

    string name;

    int age;

    Student(string name, int age):name(name),age(age){}

    

    bool operator<(Student s) const{  //연산자 오버로딩(operator overloading)

        if(this->name == s.name){

            return this->age < s.age;

        }else{

            return this->name < s.name;

        }

    }

};



void Print(vector<Student> &v){

    cout << "Student overloading : " ;

    for(int i=0; i<5; i++){

        cout << "[" << v[i].name << ", " << v[i].age << "]";

    }

    cout << endl;

}



int main(void){

    vector<Student> v;

    

    v.push_back(Student("cc", 10));

    v.push_back(Student("ba", 24));

    v.push_back(Student("aa", 11));

    v.push_back(Student("cc", 8));  //cc는 이름이 같으니 나이 기준 오름차순 예시

    v.push_back(Student("bb", 21));

    

    Print(v); //정렬 전 출력

    sort(v.begin(), v.end()); //[begin, end) 연산자 오버로딩 이용한 정렬.

    Print(v); //정렬 후 출력

    

    return 0;

}

 

 

> 출력결과

출처: https://blockdmask.tistory.com/178 [개발자 지망생]