コンピューターサイエンスに関して学習してみた(ソートアルゴリズム編)

udemyのコンピューターサイエンスの講義を受講しましたので，前回に引き継ぎ講義でやった内容の１部をJuliaで記述したいと思います．
前回：コンピューターサイエンスに関して学習してみた(アルゴリズム編)

今回取り扱うのは以下のソートのアルゴリズムになります．
・選択ソート
・バブルソート
・クイックソート

本当はマージソートに関しても講義で扱われているのですが，今回は未対応です．
各ソートの詳細なアルゴリズムには他のサイトにお任せいたします．
(本当は勉強のためにもまとめるのが良いのかもしれませんが)

# 間違いがありましたら優しくご指摘お願いいたします．

選択ソート

選択ソートは，配列の中から常に最小の値を抜き出していくイメージなります．
個人的には１番直感的です．

# 選択ソート
function selectionSort(d)
    println("-- 入力 --")
    println(d)
    println("-- デバック --")
    for i = 1:length(d)
        println(d)
        for j = i + 1:length(d)
            # 最小の値を検索
            if d[i] > d[j]
                # デバック用①
                println("変更前：" * string(d[i]), string(d[j]))
                tmp = d[i]                
                d[i] = d[j]
                d[j] = tmp
                # デバック用②
                println("変更後：" * string(d[i]), string(d[j]))
            end
        end
    end
    println("-- 結果 --")
    println(d)
end

selectionSort([4,7,3,2,5,1,6])

バブルソート

バブルソートは，隣接する要素同士を大小比較して並び替えをするイメージなります．
１回目のループで最大(または最小)の要素が決まり，２回目のループで最大 – 1(または最小 -1)の要素が決まり，といった感じで順番に並ばれていきます．

# バブルソート
function bubbleSort(d)
    println("-- 入力 --")
    println(d)
    println("-- デバック --")
    for i = 1:length(d)
        println(d)
        for j = 1:length(d) - i
            # 最小の値を検索
            if d[j] > d[j + 1]
                # デバック用①
                println("変更前：" * string(d[j]), string(d[j + 1]))
                tmp = d[j + 1]                
                d[j + 1] = d[j]
                d[j] = tmp
                # デバック用②
                println("変更後：" * string(d[j]), string(d[j + 1]))
            end
        end
    end
    println("-- 結果 --")
    println(d)
end

bubbleSort([4,7,3,2,5,1,6])

クイックソート

クイックソートは，配列の中から基準の値を元にそれよりも大きい値と小さい値のグループに分けるます．それらを各グループごとに同じことを繰り返していくイメージになります
もっとも高速な手法の１つのようですが，プログラム自体は再帰的に記述しなくてはいけないので，やや複雑でした．

# クイックソート
function quickSort(d)
    if length(d) <= 1
        return d
    end
    base = d[1]
    small = []
    big = []
    println("-- 入力 --")
    println(d)
    println("-- デバック --")
    for i = 2:length(d)
        if d[i] <= base
            push!(small, d[i])
        elseif d[i] > base
            push!(big, d[i])     
        end       
    end
    println("small：", small)
    println("big：", big)
    t = append!(quickSort(small), [base], quickSort(big))
    println("結果：", t)
    return t
end

quickSort([4,7,3,2,5,1,6])

最後に

こういうプログラムを書くことはあまりなかったので結構大変でした．
(紙とペンを持ってプログラムを書いたのは久々でした)
次は探索のアルゴリズムに関して書きたいと思います．

Julia言語で奏でる詩