目次：プログラミング学習
シェーカーソート (英: shaker sort) は、ソートのアルゴリズムの一つ。バブルソートを、効率がよくなるように改良したもの。別名は、双方向バブルソート、改良交換法。 バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行う。バブルソートと同じく安定な内部ソートで、最悪の場合の時間計算量はO(n2)である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
アルゴリズム
バブルソートで1回スキャンを行うと、最後の要素1個がスキャン範囲中最大であることが分かり次回のスキャン範囲を1狭めることができる。さらに、このスキャンの最後で連続してm個の要素の交換が行われていなければ、そのm個についてはソート済みであることが分かるので、次回のスキャン範囲をm狭めることができる。この工夫で、後半が殆ど整列済みのデータに対してバブルソートが高速に行えるようになる。 シェーカーソートはこれに加え、スキャン方向を毎回反転することにより、スキャン範囲を後方からだけではなく前方からも狭めるようにしたものである。挿入ソートのように、殆ど整列済みのデータに対しては高速に行うことができる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
コード
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
pub fn sort(list: &mut Vec<u32>) {
bubble_sort(list);
}
fn bubble_sort(vec: &mut Vec<u32>) {
let mut left = 0;
let mut right = vec.len() - 1;
let mut last_swap_index = 0;
loop {
for i in left..right {
if vec[i + 1] < vec[i] {
swap(vec, i, i + 1);
last_swap_index = i;
}
}
right = last_swap_index;
if left == right {
break;
}
for i in ((left + 1)..=right).rev() {
if vec[i - 1] > vec[i] {
swap(vec, i, i - 1);
last_swap_index = i;
}
}
left = last_swap_index;
if left == right {
break;
}
}
}
fn swap(vec: &mut Vec<u32>, i: usize, j: usize) {
let tmp = vec[i];
vec[i] = vec[j];
vec[j] = tmp;
}