Summary
目次：プログラミング学習
与えられた配列を昇順、降順で並べ替えます。
アルゴリズム
まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。次に、2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する（配列の場合、前の要素を後ろに一つずつずらす）。この操作で、2番目までのデータが整列済みとなる（ただし、さらにデータが挿入される可能性があるので確定ではない）。このあと、3番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。
挿入ソート - Wikipedia
例
配列番号 0 から開始します。まずは 0 番目の要素を整列済みとします。 次に 1 番目の要素を整列済みの配列と比較をし、挿入先を探します。挿入先が決まったら、挿入先を空けるために要素を移動します。
移動する要素が２つありました。５を移動してから３を移動させました。これが逆だった場合は５が消えてしまいます。
移動先と元が同じでした。
コード(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
fn insertion_sort(list: &mut [i32]) {
// 要素番号 0 は整列済みとして 1 から開始
for i in 1..list.len() {
// 挿入先を探す
let mut k = i;
for j in (0..i).rev() {
if list[i] < list[j] {
// 挿入先
k = j;
} else if list[k] < list[i] {
// これ以上左に挿入先となる場所は無いのでループを抜ける
break;
}
}
// 移動と挿入
if k != i {
// 移動先を空けるための移動
let tmp = list[i];
for j in (k..i).rev() {
list[j + 1] = list[j];
}
// 挿入
list[k] = tmp;
}
}
}
fn main() {
let mut list = [5, 3, 1, 2, 6, 4];
println!("ソート前: {:?}", list);
insertion_sort(&mut list);
println!("ソート後: {:?}", list);
}
1
2
3
$ cargo run
ソート前: [5, 3, 1, 2, 6, 4]
ソート後: [1, 2, 3, 4, 5, 6]
コード(Swift)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public func insertionSort(_ array: inout [Int]) {
// 1個目の要素を整列済みとし、２個目の要素（要素番号1）から開始
for i in 1..<array.count {
var k = i;
// 要素 i より左にある要素と比較、挿入先を探す
for j in (0..<i).reversed() {
if array[i] < array[j] {
k = j;
} else if array[k] < array[i] {
break;
}
}
if k != i {
// 配列から要素iを削除
// 削除した要素をkに挿入
array.insert(array.remove(at: i), at: k)
}
}
}
[変更履歴]
- 2020/09/03: Swift コードを追加しました