쉐이커 소트
| 클래스 | 소트 |
|---|---|
| 데이터 구조 | 배열 |
| 최악 계산 시간 | О(n□) |
쉐이커 소트(영: shaker sort)는, 소트의 알고리즘의 하나.버블 소트를, 효율이 좋아지도록(듯이) 개량한 것.
버블 소트로는 스캔을 한방향 밖에 실시하지 않는데 대해, 쉐이커 소트로는 교대로 후타카타향에 실시한다. 버블 소트와 같이 안정인 내부 소트로, 최악의 경우의 시간 계산량은 O(n2)이다.
알고리즘
버블 소트로 1회 스캔을 실시하면, 마지막 요소 1개가 스캔 범위중 최대인 것을 알아 다음 번의 스캔 범위를 1좁힐 수 있다. 게다가 이 스캔의 최후로 연속해 m개의 요소의 교환을 하지 않으면 그 m개에 대해서는 소트가 끝난 상태인 것을 알므로, 다음 번의 스캔 범위를 m 좁힐 수 있다. 이 궁리로, 후반이 대부분 정렬 끝난 데이터에 대해서 버블 소트를 고속으로 실시할 수 있게 된다.
쉐이커 소트는 이것에 가세해 스캔 방향을 매회 반전하는 것으로써, 스캔 범위를 후방 뿐만 아니라 전방으로부터도 좁히도록(듯이) 한 것이다.삽입 소트와 같이, 대부분 정렬 끝난 데이터에 대해서는 고속으로 실시할 수 있다.
실장예
C++언어에 의한 실장예를 나타낸다.
#include <algorithm> // std::swap template<typename T> void shaker_sort(T data[], int num_elements) { int top_index = 0; int bot_index = num_elements - 1; while (true) { int last_swap_index; /*순서 방향의 스캔*/ last_swap_index = top_index; for (int i = top_index; i < bot_index; i++) { if (data[i] > data[i+1]) { std::swap(data[i], data[i+1]); last_swap_index = i; } } bot_index = last_swap_index; /*후방의 스캔 범위를 좁힌다*/ if (top_index == bot_index) break; /*역방향의 스캔*/ last_swap_index = bot_index; for (int i = bot_index; i > top_index; i--) { if (data[i] < data[i-1]) { std::swap(data[i], data[i-1]); last_swap_index = i; } } top_index = last_swap_index; /*전방의 스캔 범위를 좁힌다*/ if (top_index == bot_index) break; } } 동작예
t는 스캔 범위의 선두, b는 말미를 나타낸다.
초기 데이터: 8 4 3 7 6 5 2 1
1회째의 스캔 종료후: (交換回数:7)
4 3 7 6 5 2 1 8 t b
2번째의 스캔 종료후: (交換回数:6)
1 4 3 7 6 5 2 8 t b
3번째의 스캔 종료후: (交換回数:4)
1 3 4 6 5 2 7 8 t b
4번째의 스캔 종료후: (交換回数:1)
1 2 3 4 6 5 7 8 t b
5번째의 스캔 종료후: (交換回数:1)
1 2 3 4 5 6 7 8 t b
6번째의 스캔 종료후: (交換回数:0)
1 2 3 4 5 6 7 8
합계 교환 회수:7+6+4+1+1+0=19 (버블 소트의 경우 22)
This article is taken from the Japanese Wikipedia 쉐이커 소트
This article is distributed by cc-by-sa or GFDL license in accordance with the provisions of Wikipedia.
In addition, Tranpedia is simply not responsible for any show is only by translating the writings of foreign licenses that are compatible with CC-BY-SA license information.
0 개의 댓글:
댓글 쓰기