26. STL 정렬 관련 알고리즘

* sort

- 컨테이너에 있는 데이터들을 내림/오름차순으로 정렬할 때 가장 자주 사용. 기본 형이라면 greate나 less 비교 조건자를 사용(STL의 string 정렬에도 사용 가능하나 알파벳 순서로 정렬)

- 기본형이 아닌 경우에 비교 조건자를 만들어서 사용하여야한다.

# sort-1 기본형

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
 
using namespace std;
 
void print(vector<int> vec) {
  for(vector<int>::iterator IterPos = vec.begin(); IterPos!=vec.end(); ++IterPos) {
    cout << *IterPos << ", ";
  }
  cout << endl << endl;
}
 
int main() {
  vector<int> vec1(10);
  vector<int> vec2(10);
  vector<int> vec3(10);
  
  vector<int>::iterator Iter1;
  generate(vec1.begin(), vec1.end(), rand);
  generate(vec2.begin(), vec2.end(), rand);
  generate(vec3.begin(), vec3.end(), rand);
  
  cout << "정렬 이전" << endl;
  print(vec1);
  print(vec2);
  print(vec3);
  cout <<"정렬 이후" << endl;
  sort(vec1.begin(), vec1.end());
  print(vec1);
  
  sort(vec2.begin(), vec2.end(), greater<int>());
  print(vec2);
  
  sort(vec3.begin()+5, vec3.end(), greater<int>());
  print(vec3);
  return 0;
}

# 결과

정렬 이전
1804289383, 846930886, 1681692777, 1714636915, 1957747793, 424238335, 719885386, 1649760492, 596516649, 1189641421, 

1025202362, 1350490027, 783368690, 1102520059, 2044897763, 1967513926, 1365180540, 1540383426, 304089172, 1303455736, 

35005211, 521595368, 294702567, 1726956429, 336465782, 861021530, 278722862, 233665123, 2145174067, 468703135, 

정렬 이후
424238335, 596516649, 719885386, 846930886, 1189641421, 1649760492, 1681692777, 1714636915, 1804289383, 1957747793, 

2044897763, 1967513926, 1540383426, 1365180540, 1350490027, 1303455736, 1102520059, 1025202362, 783368690, 304089172, 

35005211, 521595368, 294702567, 1726956429, 336465782, 2145174067, 861021530, 468703135, 278722862, 233665123,

# sort-2 사용자 정의 형

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
 
using namespace std;
 
struct USER {
  int UID;
  int Level;
  int Money;
};
 
struct USER_MONEY_COMP {
  bool operator()(const USER& user1, const USER& user2){
    return user1.Money > user2.Money;
  }
};
 
void print(vector<USER> Users) {
  for(vector<USER>::iterator Iter1 =  Users.begin(); Iter1 != Users.end(); ++Iter1 ) {
    cout << Iter1->UID << " : " << Iter1->Money << ", ";
  }
  cout << endl << endl;
}
 
int main() {
  USER User1; User1.UID = 1; User1.Money = 2000;
  USER User2; User2.UID = 2; User2.Money = 2050;
  USER User3; User3.UID = 3; User3.Money = 2200;
  USER User4; User4.UID = 4; User4.Money = 1000;
  USER User5; User5.UID = 5; User5.Money = 2030;
  
  vector<USER> Users;
  Users.push_back(User1);
  Users.push_back(User2);
  Users.push_back(User3);
  Users.push_back(User4);
  Users.push_back(User5);
  
  cout << "돈을 기준으로 정렬하기 전 " << endl;
  print(Users);
  
  sort(Users.begin(), Users.end(), USER_MONEY_COMP());
  print(Users);
  return 0;
}

# 결과

돈을 기준으로 정렬하기 전 
1 : 2000, 2 : 2050, 3 : 2200, 4 : 1000, 5 : 2030, 

3 : 2200, 2 : 2050, 5 : 2030, 1 : 2000, 4 : 1000, 

* binary_search

- 이미 정렬된 상태에서 특정 데이터가 지정한 구간에 있는지를 조사하는 알고리즘.

- binary_search(시작 반복자, 끝 반복자, 찾을 데이터, 비교 조건자);

- 비교조건자는 없어도 되고 존재해도 된다.(sort처럼)

- release모드에서는 정렬 없이 사용 가능하지만 일반적으로 불가능. 꼭 정렬하자.

# 정렬 없이 사용 예시

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
 
using namespace std;
 
int main() {
  vector<int> vec1;
  vec1.push_back(10);
  vec1.push_back(20);
  vec1.push_back(15);
  vec1.push_back(7);
  vec1.push_back(100);
  vec1.push_back(40);
  vec1.push_back(11);
  vec1.push_back(60);
  vec1.push_back(140);
  bool bFind = binary_search(vec1.begin(), vec1.begin()+5, 15);
  
  if(false == bFind) cout << "15가 없습니다." << endl;
  else cout << "15를 찾았습니다." << endl;
  return 0;
}

# 결과

15가 없습니다.

# 정렬 후 사용

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
 
using namespace std;
 
int main() {
  vector<int> vec1;
  vec1.push_back(10);
  vec1.push_back(20);
  vec1.push_back(15);
  vec1.push_back(7);
  vec1.push_back(100);
  vec1.push_back(40);
  vec1.push_back(11);
  vec1.push_back(60);
  vec1.push_back(140);
  sort(vec1.begin(), vec1.end());
  bool bFind = binary_search(vec1.begin(), vec1.begin()+5, 15);
  
  if(false == bFind) cout << "15가 없습니다." << endl;
  else cout << "15를 찾았습니다." << endl;
  return 0;
}

# 결과

15를 찾았습니다.

- 비교조건자의 경우엔 sort 때의 코드를 활용해보면 알 수 있다.

* merge

- 두개의 정렬된 구간을 합칠 때 사용하는 것. 두 구간과 겹치지 않은 곳에 합친 결과를 넣어야한다.

- 합치기 전에 이미 정렬이 되어있어야하며, 합친 결과를 넣는 것은 합치는 것들과 겹치면 안되며, 합친 결과를 넣을 수 있는 공간이 필요하다.

- merge(시작 반복자1, 끝 반복자1, 시작 반복자2, 끝 반복자2, 대입할 곳 시작 반복자);

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
 
using namespace std;
 
void print(vector<int> vec) {
  for(vector<int>::iterator IterPos = vec.begin(); IterPos != vec.end(); ++IterPos) {
    cout << *IterPos << ", ";
  }
  cout << endl << endl;
}
 
int main() {
  vector<int> vec1, vec2, vec3(12);
  srand(time(NULL));
  for(int i = 0 ; i < 6; ++i) vec1.push_back(rand()%100);
  for(int i = 0 ; i < 6; ++i) vec2.push_back(rand()%100);
  
  print(vec1);
  print(vec2);
  
  merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec3.begin());
  
  print(vec3);
  
  return 0;
}

# 결과

41, 97, 35, 65, 78, 58, 

1, 21, 75, 71, 47, 94, 

1, 21, 41, 75, 71, 47, 94, 97, 35, 65, 78, 58, 

* 참고 : Thinking About C++ STL Programming