list 컨테이너에 있는 것을 범용 알고리즘을 사용하여 정렬 할 때 어떤 방법이 있는지 설명하고 각 정렬 방식을 사용했을 때 어떤 것이 성능적으로 우수한지 결과를 보여주고 있습니다.

또 아래에는 글에서 소개한 정렬 방식의 구현을 코드로 보여주고 있습니다.

 

 

출처 : http://www.s34.co.jp/cpptechdoc/article/sort/index.html

 

sort는 list를 정렬 할 수 없다.

 

 

표준 C++가 제공하는 <algorithm>에는 편리한 알고리즘이 많이 준비되어 있습니다.

그 중에서도 sort(sort, stable_sort)는 사용 빈도가 높은 알고리즘입니다.

유감스럽지만 sort, stable_sort가 인수로서 받는 이테레이터는 RandomAccessIterator가 아니면 안됩니다. 따라서 list<T>의 요소를 정렬 하고 싶을 때,

list<int> il;
sort(il.begin(), il.end());

라고 하는 코드는 compile error를 일으킵니다. list<T>의 이테레이터는 BidirectionalIterator로 랜덤 접근을 할 수 없기 때문입니다.

list<T>에는 메소드 sort()가 준비되어 있습니다만 코드 중에서 이용하는 컨테이너를 여러가지로 바꾸는 경우

#ifdef USE_LIST
typedef list<int> container;
#else
typedef vector<int> container;
#endif
...
container c;
...
#ifdef USE_LIST
c.sort();
#else
sort(c.begin(), c.end());
#endif

와 같이 #ifdef...#else...#endif로 새로 바꾸지 않으면 안 되게 됩니다.

여기서 Bidirectionaliterator(혹은 ForwardIterator)를 받아들이는 정렬 알고리즘을 준비하면 이러한 변환을 행하지 않고 끝납니다.


selection_sort: 단순 선택 정렬

단순 선택 정렬 알고리즘은 매우 단순합니다.

  1. x[0] .. x[N-1] 중에서 최소의 요소 x[i] 를 찾아내서 그것과 x[0]을 교환한다
  2. x[1] .. x[N-1] 중에서 최소의 요소 x[i] 를 찾아내서 그것과 x[1]를 교환한다
  3. x[2] .. x[N-1] 중에서 최소의 요소 x[i] 를 찾아내 그것과 x[2]를 교환한다

...이것을 N회 반복하면 정렬 완료입니다.

요소의 비교 회수는 N2에 비례하고 교환 회수는 N에 비례합니다.


buble_sort: 버블 정렬

가장 유명하고 가장 성능이 나쁜 정렬입니다.

  1. x[0] )과 x[1] 을 비교하여 x[0] > x[1] 이라면 이 두 개를 교환한다
  2. x[1] 과 x[2] 를 비교하여 x[1] > x[2] 이라면 이 두 개를 교환한다
  3. x[2] 와 x[3]를 비교하여 x[2] > x[3] 이라면 이 두 개를 교환한다

...이것을 N회 반복하면 X[N-1]에는 최대 요소가 저장 됩니다.

그리고 이 일련의 처리 중에서 한 번이라도 교환이 행해지면 최대 요소를 제외한(요소수는 하나 적다) 열에 대해 재차 반복합니다.

요소의 비교 회수/교환 회수 모두 N2에 비례합니다.


comb_sort: 콤 정렬

버블 정렬은 "매우 가까운 두 개의 요소간에 비교/교환을 행한다"는 것이 성능이 좋지 않은 원인입니다. 더 떨어진 요소 사이에 비교/교환을 행하면 더 빨라질 것입니다. 즉, 버블 정렬 알고리즘을 약간 어레인지한:

  1. x[0]와 x[0+gap] 을 비교하여 x[0] > x[0+gap] 이라면 이 두 개를 교환한다
  2. x[1] 과 x[2+gap] 를 비교하여 x[1] > x[2+gap] 이라면 이 두 개를 교환한다
  3. x[2] 와 x[3+gap] 를 비교하여 x[2] > x[3+gap] 이라면 이 두 개를 교환한다

...이 일련의 처리를 gap을 점차 작게 하면서 반복합니다.

정렬에 대해 조사하고 있던 참에 "콤 소트(comb_sort)"라고 하는 알고리즘을 찾아냈습니다. 이것은 상기 알고리즘에 대하여 gap / 1.3 을 새로운 gap으로 반복합니다( 1.3 이라고 하는 값은 경험적으로 구할 수 있던 값인 것 같다).


세 개의 정렬을 비교

상기 세 개의 정렬(selection_sort, bubble_sort, comb_sort)에 대해서 비교/교환 회수를 실측해 보았습니다.

정렬 대상은 list<char> 로 aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
이것을 승순, 즉: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
로 순서를 바꾸는데 행한 비교/교환 회수를 실측했습니다.

알고리즘 비교 회수 교환 회수
단순 선택 정렬 1378 51
버블 정렬 1377 975
콤 정렬 564 99

이 결과로부터도 버블 정렬의 늦음은 분명합니다.
그에 대한 콤 정렬은 단순 선택 정렬/버블 정렬과 비교하면 비교 회수가 격감하고 있습니다.


역자

아래 내용 중 'stable_sort: 안정적인 정렬(only VC++)' 부분은Visual Studio 2008에서 확인 결과 맞지 않습니다. 이 글이 2004년 이전에 써여진 글이기 때문에 지금과는 틀린 것 같습니다. 그러니 이 부분은 그냥 넘어가셔도 됩니다. 또한 comb_sort에 관한 내용은 위키피디아에 있습니다.


stable_sort: 안정적인 정렬(only VC++)

알고리즘 stable_sort 는 표준 C++ 규격에서는 인수에 건네 주는 이테레이터는RandomAccessIterator이다고 쓰여져 있습니다. 하지만 적어도 Visual C++의 STL 구현에서는 헤더<algorithm>의 단 2행을 고쳐 쓰는 것만으로 list<T>에 적용할 수 있는 것을 알 수 있었습니다.

헤더 <algorithm>의 570 행 근처:

template inline
void _Insertion_sort_1(_BI _F, _BI _L, _Ty *) {if (_F != _L) for (_BI _M = _F; ++_M != _L; ) {_Ty _V = *_M; if (!(_V < *_F)) _Unguarded_insert(_M, _V); else {copy_backward(_F, _M, _M + 1); *_F = _V; }}}

및 620 행 근처:

template inline
        void _Insertion_sort_1(_RI _F, _RI _L, _Pr _P, _Ty *)
        {if (_F != _L)
                for (_RI _M = _F; ++_M != _L; )
                        {_Ty _V = *_M;
                        if (!_P(_V, *_F))
                                _Unguarded_insert(_M, _V, _P);
                        else
                                {copy_backward(_F, _M, _M + 1);
                                *_F = _V; }}}

에 있는 {copy_backward(_F, _M, _M + 1);

{_RI _N = _M; copy_backward(_F, _M, ++_N);

로 고쳐 써 주세요.이것만으로 stable_sort 에 BidirectionalIterator 를 건네 줄 수 있게 됩니다.


source code
#include <algorithm>

template <class ForwardIterator,class Predicate>
void selection_sort(ForwardIterator first, ForwardIterator last, Predicate pr)
{
while ( first != last ) { ForwardIterator mid = std::min_element(first, last, pr);
if( first != mid ){ std::iter_swap(first, mid);
}
++first;
}
}

template <class ForwardIterator>
void selection_sort(ForwardIterator first, ForwardIterator last) {
while( first != last ) { ForwardIterator mid = std::min_element(first, last);
if( first != mid ){ std::iter_swap(first, mid);
}
++first;
}
}

template <class BidirectionalIterator,class Predicate>
void bubble_sort(BidirectionalIterator first, BidirectionalIterator last, Predicate pr) {
bool swapped;
do { BidirectionalIterator curr = first; BidirectionalIterator next = curr;
++next; swapped=false;
while( next!= last ) {
if( pr(*next,*curr)) { std::iter_swap(curr, next); swapped = true;
}
++curr;
++next;
}
--last;
} while( swapped );
}

template <class BidirectionalIterator>
void bubble_sort(BidirectionalIterator first, BidirectionalIterator last) {
bool swapped;
do { BidirectionalIterator curr = first; BidirectionalIterator next = curr;
++next; swapped =false;
while( next != last ) {
if(*next <*curr ){ std::iter_swap(curr, next); swapped = true;
}
++curr;
++next;
}
--last;
} while( swapped );
}

template <class BidirectionalIterator, class Predicate>
void comb_sort(BidirectionalIterator first, BidirectionalIterator last, Predicate pr) {
int gap =static_cast<int>(std::distance(first, last));
if( gap < 1 ){
return;
}
     BidirectionalIterator first2 = last;
     bool swapped = false;
     do{
       int newgap = (gap*10+3)/13;
       if( newgap < 1) newgap =1;
       std::advance(first2, newgap - gap);
       gap = newgap;
       swapped = false;
       for( BidirectionalIterator target1 = first, target2 = first2;
               target2 != last;  ++target1, ++target2) {
if( pr(*target2, *target1) ) { std::iter_swap(target1, target2); swapped = true;
          }
}
} while((gap >1)|| swapped );
}

template <class BidirectionalIterator>
void comb_sort(BidirectionalIterator first, BidirectionalIterator last){
       int gap = static_cast<int>(std::distance(first, last));
       if( gap <1 ){  return;}
BidirectionalIterator first2
= last;
bool swapped=false;
do {
int newgap =(gap*10+3)/13;
if( newgap < 1) newgap =1; std::advance(first2, newgap-gap); gap = newgap; swapped =false;
for( BidirectionalIterator target1 = first, target2 = first2; target2 != last;
++target1,++target2){
if(*target2 <*target1 ) { std::iter_swap(target1, target2); swapped =true;
}
}
} while( (gap >1)|| swapped );
}
sample code (상기 코드의 직후에 기술)

#include <iostream>
#include <functional>
#include <list>
using namespace std;
int main() { list<char> il, tl; for ( int i = 0; i < 26; ++i ) { tl.push_back('a'+i); tl.push_back('A'+i); }
il = tl; cout << "source :"; copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl;
il = tl; cout << "selection (ascending) :"; selection_sort(il.begin(), il.end()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl;
il = tl; cout << "selection (descending):"; selection_sort(il.begin(), il.end(), greater<char>()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl;
il = tl; cout << "bubble (acsending) :"; bubble_sort(il.begin(), il.end()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl;
il = tl; cout << "bubble (descending) :"; bubble_sort(il.begin(), il.end(), greater<char>()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl;
il = tl; cout << "comb (ascending) :"; comb_sort(il.begin(), il.end()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl;
il = tl; cout << "comb (descending) :"; comb_sort(il.begin(), il.end(), greater<char>()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl; #ifdef PATCHED_MS_STL il = tl; cout << "stable (ascending) :"; stable_sort(il.begin(), il.end()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl;
il = tl; cout << "stable (descending) :"; stable_sort(il.begin(), il.end(), greater<char>()); copy(il.begin(), il.end(), ostream_iterator<char>(cout)); cout << endl; #endif return 0; }

result
source                :aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
selection (ascending) :ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
selection (descending):zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA
bubble (acsending) :ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
bubble (descending) :zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA
comb (ascending) :ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
comb (descending) :zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA
stable (ascending) :ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
stable (descending) :zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA


이 글은 스프링노트에서 작성되었습니다.

신고
by 흥배 2009.04.14 01:05
| 1 |

티스토리 툴바