Rustでバブルソートを書く

バブルソートの理解とRustの勉強のため、Rustでバブルソートを書きました

書いた後、ChatGPTに訊ねたら、似たようなコードを教えてくれたのでおおむね正しそうです

ソースコード

fn main() {
    let original_array = vec![ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ];

    let sorted_array = bubble_sort(original_array.clone());

    println!("original array: {:?}", original_array);
    println!("sorted array: {:?}", sorted_array);
}

fn bubble_sort(mut arr: Vec<u8>) -> Vec<u8> {
    let debug_print_flag = true; // 途中結果表示用
    let len = arr.len();

    if debug_print_flag { println!("{:?}", arr); }
    if debug_print_flag { println!("--------"); }

    // lenが配列の個数nなので、O(n^2)であることがわかる
    for i in 0..len-1 { // n個のデータをひとつずつ位置を確定する
        for j in 0..(len-1-i) { // 位置が確定した大きな数字をソート対象から除く
            if arr[j] > arr[j+1] {
                arr.swap(j, j+1);
                if debug_print_flag { println!("{:?}", arr); }
            }
        }
        if debug_print_flag { println!("--------"); }
        if debug_print_flag { println!("{:?}", arr); }
    }
    if debug_print_flag { println!("--------"); }
    arr
}

考え方

以下のような比較をしていっている

i:0
[ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ]
  ^^^^^ j:0
      ^^^^ j:1   
         ^^^^ j:2
                   ...     
                           ^^^^ j:8
i:1
[ 9, 8, 7, 6, 5, 4, 3, 2, 1 ] [ 10 ]
  ^^^^ j:0
     ^^^^ j:1   
        ^^^^ j:2
                   ...     
                       ^^^^ j:7
.
i:8
[ 2, 1 ] [ 3, 4, 5, 6, 7, 8, 9, 10 ]
  ^^^^ j:0

改良点

-                let tmp = arr[j];
-                arr[j] = arr[j+1];
-                arr[j+1] = tmp;
+                arr.swap(j, j+1);

基本データ型のスライスにはswapメソッドがあるため、こう書いた方がわかりやすい

出力結果

バブルソートという名前の通り、値が泡のように浮き上がっていきます

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
--------
[9, 10, 8, 7, 6, 5, 4, 3, 2, 1]
[9, 8, 10, 7, 6, 5, 4, 3, 2, 1]
[9, 8, 7, 10, 6, 5, 4, 3, 2, 1]
[9, 8, 7, 6, 10, 5, 4, 3, 2, 1]
[9, 8, 7, 6, 5, 10, 4, 3, 2, 1]
[9, 8, 7, 6, 5, 4, 10, 3, 2, 1]
[9, 8, 7, 6, 5, 4, 3, 10, 2, 1]
[9, 8, 7, 6, 5, 4, 3, 2, 10, 1]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 10]
--------
[9, 8, 7, 6, 5, 4, 3, 2, 1, 10]
[8, 9, 7, 6, 5, 4, 3, 2, 1, 10]
[8, 7, 9, 6, 5, 4, 3, 2, 1, 10]
[8, 7, 6, 9, 5, 4, 3, 2, 1, 10]
[8, 7, 6, 5, 9, 4, 3, 2, 1, 10]
[8, 7, 6, 5, 4, 9, 3, 2, 1, 10]
[8, 7, 6, 5, 4, 3, 9, 2, 1, 10]
[8, 7, 6, 5, 4, 3, 2, 9, 1, 10]
[8, 7, 6, 5, 4, 3, 2, 1, 9, 10]
--------
[8, 7, 6, 5, 4, 3, 2, 1, 9, 10]
[7, 8, 6, 5, 4, 3, 2, 1, 9, 10]
[7, 6, 8, 5, 4, 3, 2, 1, 9, 10]
[7, 6, 5, 8, 4, 3, 2, 1, 9, 10]
[7, 6, 5, 4, 8, 3, 2, 1, 9, 10]
[7, 6, 5, 4, 3, 8, 2, 1, 9, 10]
[7, 6, 5, 4, 3, 2, 8, 1, 9, 10]
[7, 6, 5, 4, 3, 2, 1, 8, 9, 10]
--------
[7, 6, 5, 4, 3, 2, 1, 8, 9, 10]
[6, 7, 5, 4, 3, 2, 1, 8, 9, 10]
[6, 5, 7, 4, 3, 2, 1, 8, 9, 10]
[6, 5, 4, 7, 3, 2, 1, 8, 9, 10]
[6, 5, 4, 3, 7, 2, 1, 8, 9, 10]
[6, 5, 4, 3, 2, 7, 1, 8, 9, 10]
[6, 5, 4, 3, 2, 1, 7, 8, 9, 10]
--------
[6, 5, 4, 3, 2, 1, 7, 8, 9, 10]
[5, 6, 4, 3, 2, 1, 7, 8, 9, 10]
[5, 4, 6, 3, 2, 1, 7, 8, 9, 10]
[5, 4, 3, 6, 2, 1, 7, 8, 9, 10]
[5, 4, 3, 2, 6, 1, 7, 8, 9, 10]
[5, 4, 3, 2, 1, 6, 7, 8, 9, 10]
--------
[5, 4, 3, 2, 1, 6, 7, 8, 9, 10]
[4, 5, 3, 2, 1, 6, 7, 8, 9, 10]
[4, 3, 5, 2, 1, 6, 7, 8, 9, 10]
[4, 3, 2, 5, 1, 6, 7, 8, 9, 10]
[4, 3, 2, 1, 5, 6, 7, 8, 9, 10]
--------
[4, 3, 2, 1, 5, 6, 7, 8, 9, 10]
[3, 4, 2, 1, 5, 6, 7, 8, 9, 10]
[3, 2, 4, 1, 5, 6, 7, 8, 9, 10]
[3, 2, 1, 4, 5, 6, 7, 8, 9, 10]
--------
[3, 2, 1, 4, 5, 6, 7, 8, 9, 10]
[2, 3, 1, 4, 5, 6, 7, 8, 9, 10]
[2, 1, 3, 4, 5, 6, 7, 8, 9, 10]
--------
[2, 1, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
--------
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
--------
original array: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

まあ、ソートメソッドが実装されているため、普通はarr.sort()で終わります

こちらのソートは

This sort is stable (i.e., does not reorder equal elements) and O(n * log(n)) worst-case.

オーダーは最悪でO(n*log(n))だそうです
unstableなソートのメソッドも存在するとか書いてありました