[ 혼연 정리 ] STL 알고리즘 - 8 [ 정렬 알고리즘 ]

ㅇ 정렬 알고리즘
 - 모든 정렬 함수들은 임의 접근 반복자를 요구하므로  임의 접근이 가능한 컨테이너에서 사용가능
 - 별도의 조건자가 지정되 않을 경우 < 연산자가 요소의 대소를 비교

ㅇ sort()

  void sort (RanIt first, RanIt last [, BinPred F]);

 - 가장 기본적인 정렬 함수
 - first ~ last 구간을 조전자의 비교 결과대로 정렬

 ㅇ stable_sort()
 
   void stable_sort (RanIt first, RanIt last [, BinPred F]);

 - 같은 값의 상대적인 순서가 정렬 후에도 유지되는 안정적인 정렬을 수행
 - 안정성이 없는 sort보다 조금 더 느리다.

ㅇ partial_sort()

  void partial_sort (RanIt first, RanIt SortEnd, RanIt last [, BinPred F]);

 - 두번째 인수로 지정한 SortEnd 부분 직전까지만 정렬하고 나머지 뒷부분은 정렬되지 않은 채로 내버려 둔다.
 - 최상위 n번까지만 골라내고 싶을 때 이 함수를 사용하며 안정성은 없다.

ㅇ nth_element()

   void nth_element(RanIt first, RanIt Nth, RanIt last [, BinPred F]);

 - 두번째 인수로 지정한 n에 n번째 값을 놓고 그 왼쪽에 n보다 작은 값을, 오른쪽에 n이상의 값으로 구간을 분할한다.
 - n의 위치만 정확하며 나머지 좌우 구간의 정렬 상태는 보증되지 않는다.
 - 특정값을 기준으로 미만 그룹, 이상 그룹을 분류 할  유용

1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 #include <functional>
5
6 using namespace std;
7
8 template<typename C>
9 void dump(const char *desc, C c)

10 {
11     cout.width(12);cout << left << desc << "==> ";
12     copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," "));
13     cout << endl;
14 }
15
16 void main()
17 {
18      int ari[]={49,26,19,77,34,52,84,34,92,69};
19
20      vector<int> vi(&ari[0],&ari[10]);
21
22      dump("원본",vi);
23      sort(vi.begin(),vi.end());
24  
25      dump("sort",vi); 
26      vector<int> vi2(&ari[0],&ari[10]);
27      stable_sort(vi2.begin(),vi2.end());
28      dump("stable_sort",vi2);
29     
30      vector<int> vi3(&ari[0],&ari[10]);
31      partial_sort(vi3.begin(),vi3.begin()+5,vi3.end());
32      dump("partial_sort",vi3);
33
34      vector<int> vi4(&ari[0],&ari[10]);
35      nth_element(vi4.begin(),vi4.begin()+5,vi4.end());
36      dump("nth_element",vi4);
37 }

ㅇ binary_search

bool binary_search(FwdIt first, FwdIt last, const T& val [, BinPred F]);

 - 정렬된 구간에서 이분 검색으로 존재 여부를 조사한다.
 - 반복자 구간은 반드시 정렬되어 있어야 한다.
 - 정렬되어 있지 않으면 결과는 예측할 수 없다.
 - 단지 원하는 값이 구간내에 있는지 조사만 할뿐이지 어디 쯤에 있는지 조사하지는 않는다. ==> 중복된 값이 있을 경우 정확하게 원하는 값인지 아닌지 확신할 수 없기 때문
 - 값이 존재하면 true를 리턴, 그렇지 않으면 false를 리턴

※ 값의 위치를 검색하려면 다음 3가지 함수들을 사용해야 한다

ㅇ lower_bound()

    FwdIt lower_bound(FwdIt first, FwdIt last, const T& val [,BinPred F]);

 - 값이 있는 첫번 째 위치를 리턴, 없다면 이 값이 삽입될 수 있는 있는 위치를 조사

ㅇ upper_bound()

FwdIt upper_bound(FwdIt first, FwdIt last, const T& val [,BinPred F]);

 -  마지막 위치의 다음 위치를 리턴,  검색값보다 큰 최초의 값 위치

ㅇ  equal_range()

pair< FwdIt, FwdIt > equal_range(FwdIt first, FwdIt last, const T& val [,BinPred F]);

 - 두 함수의 결과를 pair로 묶어서 리턴

1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 #include <functional>
5
6 using namespace std;
7
8 template<typename C>
9 void dump(const char *desc, C c) 10 {
11     cout.width(12);cout << left << desc << "==> ";
12     copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," "));
13     cout << endl;
14 }
15
16 void main()
17 {
18     int ari[]={49,26,19,77,34,52,84,34,92,69};
19     vector<int> vi(&ari[0],&ari[10]);
20     vector<int>::iterator it;
21
22     dump("원본",vi);
23     sort(vi.begin(),vi.end());
24     it=lower_bound(vi.begin(),vi.end(),50);
25     if (*it == 50)
26     {
27         cout << "찾는값이존재합니다." << endl;
28     } else
29     {
30         vi.insert(it,50);
31         dump("삽입후",vi);
32     }
33 }

- 34의 앞쪽에 삽입을 하고 싶다면 lower_bound로 위치를 검색하고, 34의 뒤쪽에 삽입을 하고 싶다면 upper_bound로 검색



ㅇ merge

  OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt result [, BinPred F]);

 - 두 반족자 구간의 요소를 병합한다.
 - 두 구간은 정렬되어 있어야 하며 합쳐진 결과도 정렬된다.
 - first1 ~ lsat1 구간과 first2 ~ last2 구간을 병합하여 result에 작성한다.
 - result는 두 구간을 모두 받을 수 있을 만한 충분한 공간이 확보되어 있던가 아니면 삽입 반복자여야 한다.
  - 안정성이 있고 동등한 값의 원래 순서가 유지된다.

ㅇ  inplace_merge

  void inplace_merge(BiIt first, BiIt middle, BiIt last [, BinPred F]);

 - 두 반족자 구간의 요소를 병합한다.
 - 두 구간은 정렬되어 있어야 하며 합쳐진 결과도 정렬된다.
 - 한 컨테이너의 정렬된 두 연속 구간을 합쳐 원래 구간에 써 넣는다.
 - first ~ middle 구간과 middle ~ last 구간을 병합하여 다시 first ~ last 구간을 작성한다.
 - 안정성이 있고 동등한 값의 원래 순서가 유지된다.

1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 #include <functional>
5
6 using namespace std;
7
8 template<typename C>
9 void dump(const char *desc, C c) 10 {
11     cout.width(12);cout << left << desc << "==> ";
12     copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," "));
13     cout << endl;
14 }
15
16 void main()
17 {
18      int i;
19      vector<int> vi1,vi2,vi3;
20      for (i=1;i<5;i++) vi1.push_back(i);
21      for (i=3;i<9;i++) vi2.push_back(i);
22      merge(vi1.begin(),vi1.end(),vi2.begin(),vi2.end(),back_inserter(vi3));
23      dump("merge",vi3);
24
25      vector<int> vi4;
26      for (i=1;i<5;i++) vi4.push_back(i);
27      for (i=3;i<9;i++) vi4.push_back(i);
28      inplace_merge(vi4.begin(),vi4.begin()+4,vi4.end());
29      dump("inplace_merge",vi4);
30
31 }

ㅇ min, max

const T& min(const T& x, const T& y [, BinPred F]);
const T& max(const T& x, const T& y [, BinPred F]);

 - min, max는 두 값 중 큰값과 작은 값을 조사
 - 인수로 비교 대상이 되는 두값을 전달 받는다.
 - 마지막 인수로 조건자를 지정할 수 있다.
 - 크다, 작다라는 비교연산은 지극히 단순한 개념이지만 사용자 정의 타입에서는 이런 간단한 비교조차도 다른 의미를 가질 수 있으므로 조건자가 비교하도록 할 수 있다.

ㅇ min_element, max_element

FwdIt min_element(FwdIt first, FwdIt last[, BinPred F]);
FwdIt max_element(FwdIt first, FwdIt last[, BinPred F]);

 - 반복자 구간에서 가장 큰 요소, 가장 작은 요소를 찾아 반복자를 리턴한다.

1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5 using namespace std;
6
7 void main()
8 {
9      int i=3,j=5;
10      printf("둘중작은값은%d이고큰값은%d이다.\n",min(i,j),max(i,j)); 11
12      int ari[]={49,26,19,77,34,52,84,34,92,69};
13      vector<int> vi(&ari[0],&ari[10]);
14      printf("벡터에서가장작은값은%d이고가장큰값은%d이다.\n",
15           *min_element(vi.begin(),vi.end()),*max_element(vi.begin(),vi.end()));
16 }

ps : 출처 및 자세한 내용은  www.WinAPI.co.kr 참고