C++ STL sort

Sort

C++ STL 개념의 마지막인 sort에 대해서 알아보겠습니다.

슬슬 개념공부가 지겨워서 빨리 문제를 풀고 싶은데 다행입니다.

 

1) Sort의 정의

C++의 sort() 함수는 기본적으로 오름차순의 정렬을 수행합니다.

정렬 방식은 quick sort를 기반으로 heap sort, insertion sort를 섞은 방식으로 nlogn의 시간복잡도를 가집니다.

 

2) Sort의 사용

sort() 함수를 사용하기 위해서는 <algorithm>을 include 해주어야 합니다.

vector를 정렬한다고 가정하였을 때

sort(v.begin(), v.end()); 로 정렬을 진행하여 줄 수 있습니다.

만약 크기가 10인 배열 arr을 정렬한다면

sort(arr, arr+10); 으로 정렬을 해 줄 수 있습니다.

 

3) Sort의 변형

sort(v.begin(), v.end(), compare) 을 이용하여서 정렬 기준을 변형할 수 있습니다 (compare()가 아닌 compare임을 주의)

compare 는 boolean 타입의 함수여야 합니다.

 

예시를 통해서 어떻게 사용하는지 알아보겠습니다.

 

내림차순으로 정렬하는 예시)

 

#include <iostream>
//sort()함수를 사용하기 위해
#include <algorithm>

using namespace std; 

//새로운 기준을 위해서 return형이 boolean type인 함수를 만들어준다
bool compare(int a, int b){ 
  return a > b; 
} 

int main(void){ 

  //정렬 대상 배열
  int arr[10] = {7, 1, 5, 9, 8, 3, 2, 4, 6, 10}; 
  
  sort(arr, arr+10, compare); 
  for(int i=0; i<10; i++){ 
    cout << arr[i] << ' '; 
  } 
  
  return 0; 
}

 

위에서 사용한 compare 함수를 보면 a>b이기 때문에 a가 더 클 때 true를 반환하게 되어있습니다.

따라서 큰 것이 앞으로가는 내림차순으로 정렬이 됩니다.

 

기준에 따른 class sort 예시)

 

compare를 사용하는 다양한 예시를 찾아보다가 잘 정리된 blog를 발견하였습니다.

https://blockdmask.tistory.com/178

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

 

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


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

 

output은

Student : [aa, 11] [ba, 24] [bb, 21] [cc, 8] [cc, 10]

 

으로 이름이 같으면 숫자를 기준으로 오름차순으로 정렬하고, 이름이 다르면 사전순으로 정렬한 것을 볼 수 있습니다.

 

이상으로 sort에 대한 포스팅을 마치겠습니다.