挿入ソートのアルゴリズム

挿入ソートのアルゴリズム

与えられた配列をソートする際、挿入ソートを用いるとする。

与えられた配列を、ソート済みの配列(長さは1)と未ソートの配列に分割する。未ソートの配列の中から一つ選び、ソート済みの配列に挿入する。挿入された値と、隣り合う要素同士を比較し、インデックスを入れ替えながら配列を並び替えていく。

アルゴリズム実装 O(n²)

TypeScript

export function insertionSort(array: number[]) {
    for (let i = 0; i < array.length; i++) {
        let j = i;

        while (j > 0 && array[j] < array[j - 1]) {
            const tmp = array[j];
            array[j] = array[j - 1];
            array[j - 1] = tmp;
            j -= 1;
        }
    }
    return array;
}

Rust

fn insertion_sort(array: &mut Vec<i32>) {
    for i in 0..array.len() {
        let mut j = i;

        while j > 0 && array[j] < array[j - 1] {
            let tmp = array[j];
            array[j] = array[j - 1];
            array[j - 1] = tmp;
            j -= 1;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn it_works() {
        let mut vec = vec![-96, 11, 0, 45, -2];
        insertion_sort(&mut vec);
        assert_eq!(vec, &[-96, -2, 0, 11, 45]);
    }
}