目次：プログラミング学習
与えられた配列を昇順、降順で並べ替えます。
バブルソートの改良版
アルゴリズム
適当な間隔で整列後、間隔を少しずつ狭めて整列していく。
- 総数 n を 1.3 で割り、小数点以下を切り捨てた数を間隔 h とする。
- i=0 とする。
- i 番目と i+h 番目を比べ、i+h 番目が小さい場合入れ替える。
- i=i+1 とし、i+h>n となるまで3を繰り返す。
- hがすでに1になっている場合は入れ替えが発生しなくなるまで上の操作を繰り返す。
- h を 1.3 で割り、小数点以下を切り捨てた数を新たに間隔 h とし、操作を繰り返す。
動作例
コード(rust)
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
42
43
44
45
46
47
48
pub trait CombSort {
fn comb_sort(&mut self);
}
impl<T: Ord> CombSort for Vec<T> {
fn comb_sort(&mut self) {
// 間隔 = 要素数 ÷ 1.3
let mut h = self.len() * 10 / 13;
loop {
// 交換フラグ
let mut swaps = false;
for i in 0..(self.len() - h) {
if self[i] > self[i + h] {
// 交換
self.swap(i, i + h);
// 交換が発生した
swaps = true;
}
}
if h <= 1 {
// 間隔が 1 以下であり交換が発生しなかった場合は処理を終了する
if !swaps {
break;
}
// 交換が発生した場合は間隔は 1 のまま処理を続行する
// h = 1;
} else {
// 次の間隔 = 今の間隔 ÷ 1.3
h = h * 10 / 13;
}
}
}
}
#[cfg(test)]
mod tests {
use crate::CombSort;
#[test]
fn comb_sort() {
let mut list = [8, 4, 3, 7, 6, 5, 2, 1, 0].to_vec();
list.comb_sort();
let v: Vec<_> = (0..(list.len()) as u32).map(u32::from).collect();
assert_eq!(list, v);
}
}