目次：プログラミング学習
クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
アルゴリズム
- 適当な数（ピボット（英語版）という）を選択する（この場合はデータの総数の中央値が望ましい）
- ピボットより小さい数を前方、大きい数を後方に移動させる （分割）
- 二分割された各々のデータを、それぞれソートする
出典: フリー百科事典『ウィキペディア（Wikipedia）』
適当な値としては対象となる範囲の中央にある値を選択するようにしました。
ピボットのインデックス = 左のインデックス / 配列の個数 / 2
1
let pivot_idx = left + (right - left) / 2;
- 要素が１個以下の場合は何もせずに終了
- ピボットの値を選ぶ
- 左からピボット以上になる値を探し、見つかった値のインデックスを
lとする。 - 右からピボット以下になる値を探し、見つかった値のインデックスを
rとする。 lがrよりも小さい場合は値を交換して ２ に戻る。- ２に戻るときは
l+1から探索開始 - ３では
r-1から探索開始する
- ２に戻るときは
rがl以下になったら範囲を分割する。- 最初から
l-1までとr+1から最後までの２つの範囲に分割する
- 最初から
コード
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
use env_logger;
use log::{debug, error, info, warn};
use std::env;
extern crate random_vec;
use random_vec::random_vec;
fn quick_sort(list: &mut Vec<u32>, left: usize, right: usize) {
if left < right {
let pivot_idx = left + (right - left) / 2;
let pivot = list[pivot_idx];
let mut l = left;
let mut r = right;
debug!(
"l={}, r={}, pivot_idx={}, list[pivot]={} ",
l, r, pivot_idx, pivot
);
loop {
// 左：ピボットより大きい値を探す
while l <= right && list[l] < pivot {
// ピボットの値よりも小さい場合はマーカーを右に移動
l = l + 1;
}
// 右：ピボットより小さい値を探す
while left <= r && pivot < list[r] {
// ピボットの値よりも大きい場合はマーカを左に移動
r = r - 1;
}
debug!("l={}, list[l]={}", l, list[l]);
debug!("r={}, list[r]={}", r, list[r]);
if r <= l {
break;
}
let tmp = list[l];
list[l] = list[r];
list[r] = tmp;
debug!("\x1b[32mswap\x1b[m > list: {:?}", list);
l = l + 1;
r = r - 1;
}
debug!("\x1b[30m\x1b[47mnext\x1b[m\n");
if 0 < l {
quick_sort(list, left, l - 1);
}
quick_sort(list, r + 1, right);
}
}
fn main() {
// ログ
env::set_var("RUST_LOG", "info");
env_logger::init();
// 配列
let mut list = [8, 4, 3, 7, 6, 5, 2, 1].to_vec();
let left = 0;
let right = list.len() - 1;
// ソート前
info!("list: {:?}", list);
// ソート実行
quick_sort(&mut list, left, right);
// ソート後
info!("sort: {:?}", list);
info!("\x1b[{}m\x1b[47m== 終了 ==\x1b[m", 30)
}