# Shaker sort

Class | Sort |
---|---|

Data structure | Sequence |

The worst calculation time | О(n²) |

The **shaker sort** (British: shaker sort) is algorithmic one of the sorts. I improved bubble sorting to become efficient.

It is bidirectional and performs it by the shaker sort in turn whereas I perform a scan by the bubble sorting only in one direction. The time computational complexity when it is the worst by the internal sort that is stable as well as bubble sorting is O(n^{2}).

## Algorithmic

I know that one last element is the maximum in the scan range and can narrow a next scan range 1 when I scan it by bubble sorting once. Furthermore, m can narrow a next scan range because I know what have been sorted about the m unit if the exchange of the element of the m unit is not performed in succession in the last of this scan. By this invention, most of the latter half comes to be able to perform bubble sorting for the data that it has been stood in line fast.

It was not from the rear, and the shaker sort narrowed a scan range from the front by reversing a scan direction in addition to this every time. Like an insertion sort, I can almost perform it for the data that it has been stood in line fast.

### Implementation

I show the implementation by the C++ language.

` #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; Scan */ of the /* order direction 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; */ which narrows a scan range of the /* rear if (top_index = = bot_index) break; Scan */ of the /* opposite direction 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; */ which narrows a scan range /* ahead if (top_index = = bot_index) break; } } `

### Movement example

In t, top, b of the scan range express the end.

Initial data: 8 4 3 7 6 5 2 1

After the first scan: (the exchange number of times: 7)

4 3 7 6 5 2 1 8 t b

After the second scan: (the exchange number of times: 6)

1 4 3 7 6 5 2 8 t b

After the third scan: (the exchange number of times: 4)

1 3 4 6 5 2 7 8 t b

After the fourth scan: (the exchange number of times: 1)

1 2 3 4 6 5 7 8 t b

After the fifth scan: (the exchange number of times: 1)

1 2 3 4 5 6 7 8 t b

After the sixth scan: (the exchange number of times: 0)

1 2 3 4 5 6 7 8

The total exchange number of times: 7+6+4+1+1+0 = 19 (in the case of bubble sorting 22)

This article is taken from the Japanese Wikipedia **Shaker sort**

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 개의 댓글:

## 댓글 쓰기