검색결과 리스트
list에 해당되는 글 1건
- 2009.04.14 list에서 사용할 수 있는 세(+1)개의 sort
list 컨테이너에 있는 것을 범용 알고리즘을 사용하여 정렬 할 때 어떤 방법이 있는지 설명하고 각 정렬 방식을 사용했을 때 어떤 것이 성능적으로 우수한지 결과를 보여주고 있습니다.
또 아래에는 글에서 소개한 정렬 방식의 구현을 코드로 보여주고 있습니다.
출처 : http://www.s34.co.jp/cpptechdoc/article/sort/index.html
표준 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)를 받아들이는 정렬 알고리즘을 준비하면 이러한 변환을 행하지 않고 끝납니다.
단순 선택 정렬 알고리즘은 매우 단순합니다.
...이것을 N회 반복하면 정렬 완료입니다.
요소의 비교 회수는 N2에 비례하고 교환 회수는 N에 비례합니다.
가장 유명하고 가장 성능이 나쁜 정렬입니다.
...이것을 N회 반복하면 X[N-1]에는 최대 요소가 저장 됩니다.
그리고 이 일련의 처리 중에서 한 번이라도 교환이 행해지면 최대 요소를 제외한(요소수는 하나 적다) 열에 대해 재차 반복합니다.
요소의 비교 회수/교환 회수 모두 N2에 비례합니다.
버블 정렬은 "매우 가까운 두 개의 요소간에 비교/교환을 행한다"는 것이 성능이 좋지 않은 원인입니다. 더 떨어진 요소 사이에 비교/교환을 행하면 더 빨라질 것입니다. 즉, 버블 정렬 알고리즘을 약간 어레인지한:
...이 일련의 처리를 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 는 표준 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>
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) { }
int gap = static_cast<int>(std::distance(first, last)); if( gap <1 ){ return;} |
sample code (상기 코드의 직후에 기술) |
#include <iostream> #include <functional> #include <list>
|
result |
source :aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ |
이 글은 스프링노트에서 작성되었습니다.
댓글