sort algorithm

https://blockdmask.tistory.com/178

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

 

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

 

sort algorithm 사용은 다음과 같다.

sort(start, end); // [start, end) 범위에 있는 요소를 오름차순으로 정렬 

quickSort를 기반으로 함수가 구현되어 있다. (O(N*logN)

 

다른 sort를 구현하지 않고 C++ STL의 sort 함수를 사용함으로써 구현이 편리하다.

 

sort(arr, arr+n);
sort(v.begin(), v.end());
sort(v.begin(), v.end(), compare); // 사용자 정의 함수 사용
sort(v.begin(), v.end(), greater<자료형>()); // 내림차순 정렬(큰거부터)
sort(v.begin(), v.end(), less<자료형>()); // 오름차순 정렬 (작은거부터)

 

1. 오름차순 sort

//오름차순
#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);
  Print(arr);

  return 0;
}

 

2. 내림차순 sort

//내림차순
#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, greater<int>());
  Print(arr);

  return 0;
}

 

3. 사용자 정의 함수 sort

//사용자 정의 함수 sort
#include <iostream>
#include <algorithm>
#include <vector>
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("곽재우", 10));
  v.push_back(Student("김연우", 20));
  v.push_back(Student("김의종", 15));
  v.push_back(Student("곽수민", 13));
  v.push_back(Student("곽재우", 15));

  Print(v);
  sort(v.begin(), v.end(), compare);
  Print(v);
  
}

 

4. 연산자 오버로딩 sort

//연산자 오버로딩 sort
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class Student{
  public:
    string name;
    int age;
    Student(string name, int age)
    : name(name), age(age)
    {

    }
  bool operator<(Student s) const { //연산자 오버로딩
    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;
}

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("곽재우", 10));
  v.push_back(Student("김연우", 20));
  v.push_back(Student("김의종", 15));
  v.push_back(Student("곽수민", 13));
  v.push_back(Student("곽재우", 15));

  Print(v);
  sort(v.begin(), v.end(), compare);
  Print(v);
  
}