list에 해당되는 글 1건

list에서 사용할 수 있는 세(+1)개의 sort

프로그래밍, GameDev
, ,

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


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

TRACKBACK :0 COMMENT :0
by 흥배 2009. 4. 14. 01:05
| 1 |