C++로 정렬 알고리즘 sort 사용법, 내림차순, 특정 변수 기준 정렬(연산자 오버로딩, compare 함수 활용)

알아볼 내용은, 

 

• sort 기본 함수 알아보기
• 내림차순 정렬하기
• 특정 변수 기준으로 정렬하기
  • compare 함수 구현
  • 연산자 오버로딩으로 구현
• 특정 변수 기준 내림차순 정렬하기
  • 연산자 오버로딩 + compare 함수로 구현
  • compare 함수만 구현

 

 

정렬 방식은 퀵 정렬이다. 시간복잡도는 O(NlogN)이라고 레퍼런스에도 적혀 있다.

 

www.cplusplus.com/reference/algorithm/sort/

 

sort 기본 함수 알아보기

 

sort의 인자로는 [배열의 시작주소]와 [배열의 마지막주소 + 1]이 들어간다.

#include <iostream>
#include <algorithm>

using namespace std;

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

 

 

내림차순 정렬하기

 

#include <iostream>
#include <algorithm>

using namespace std;

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

int main(void){
	int a[10] = {9, 1, 4, 5, 8, 2, 7, 3, 6, 10};
    sort(a, a+10, compare);
    for(int i =0; i<10; i++){
    	cout << a[i] << ' ';
    }
}

 

특정한 변수를 기준으로 정렬하기 (오름차순)

 

1. compare 함수를 통해 구현

#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 compare(Student a, Student b) {
    return a.score < b.score;
}

int main(void) {
    Student students[] = {
        Student("구십이", 92),
        Student("구십삽", 93),
        Student("구십구", 99),
        Student("팔십일", 81),
        Student("구십오", 95)
    };

    sort(students, students + 5, compare);
    for (int i = 0; i < 5; i++) {
        cout << students[i].name << ' ';
    }
}

 

결과

 

내림차순을 원한다면 compare함수의 return 부분을 a.score > b.score로 변경하면 된다. 아래에서 다시 설명할 예정.

 

2. 연산자 오버로딩을 통해 구현

 

연산자 오버로딩을 통해 구현하면 compare 함수 없이 구현이 가능하다.

 

#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 operator <(Student& student) {
        return this->score < student.score;
    }

};

int main(void) {
    Student students[] = {
        Student("구십이", 92),
        Student("구십삽", 93),
        Student("구십구", 99),
        Student("팔십일", 81),
        Student("구십오", 95)
    };

    sort(students, students + 5);
    for (int i = 0; i < 5; i++) {
        cout << students[i].name << ' ';
    }
}

 

결과는 위와 동일하게 오름차순 정렬이다. 오름차순 정렬은 sort 함수의 기본이 오름차순 정렬이기 때문에 따로 compare 함수 없이 연산자 오버로딩만으로 가능했지만, 내림차순 정렬은 원래 compare 함수를 구현해서 적용해야 했다. 즉 comapre함수가 필요하다.

 

 

 

특정 변수 기준 내림차순 정렬

1. compare 함수 + 연산자 오버로딩을 통한 특정변수 내림차순 정렬

#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 operator >(Student & student) {
        return this->score > student.score;
    }

};

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

int main(void) {
    Student students[] = {
        Student("구십이", 92),
        Student("구십삽", 93),
        Student("구십구", 99),
        Student("팔십일", 81),
        Student("구십오", 95)
    };

    sort(students, students + 5, compare);
    for (int i = 0; i < 5; i++) {
        cout << students[i].name << ' ';
    }
}

 

내림차순 정렬

 

2. compare 함수만 구현하기

 

사실 특정 변수 기준 정렬은 오름차순 정렬에서 연산자 오버로딩 없이 compare 함수로 구현이 가능하다. 그런데 연산자 오버로딩을 사용하면 compare이라는 새 함수를 정의하지 않아도 특정 변수 기준 정렬이 가능한 것이다. 

 

내림차순 정렬은 어차피 compare이라는 새 함수를 써야 하기 때문에, 굳이 연산자 오버로딩이랑 compare을 둘 다 구현할 것 없이 compare 함수만 구현해도 된다. 아래처럼 코드를 작성하면 된다.

 

#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 compare(Student a, Student b) {
    return a.score > b.score;
}

int main(void) {
    Student students[] = {
        Student("구십이", 92),
        Student("구십삽", 93),
        Student("구십구", 99),
        Student("팔십일", 81),
        Student("구십오", 95)
    };

    sort(students, students + 5, compare);
    for (int i = 0; i < 5; i++) {
        cout << students[i].name << ' ';
    }
}