アルゴリズムを始めよう(整列アルゴリズム)

言語とフレームワークの勉強の他に実際にプログラミングの発想をだすための下地
が必要だと感じ、アルゴリズムを勉強する。教科書はこれ

アルゴリズムを、はじめよう

整列アルゴリズムの種類

定番のアルゴリズムは4つある。選択ソート、バブルソート、挿入ソート、クイックソート。

選択ソート

単純選択法ともいう。順列に並べる場合、１つずつ値を取り出していき最小のものを配列の先頭の要素とする。

Rubyで書いてみた

a = [12, 5, 11, 6, 10,]
i = 0
while i < 4
    indexMin = i　# =>暫定的に配列の先頭が小さいとする
    k = i + 1　# =>暫定配列と比べるために添字に＋1をする
        while k < 5 # =>　要素数の数だけ繰り返す
            if a[k] < a[indexMin]
            indexMin = k
            k = k + 1
            else
            k = k + 1
            end
        end
    w = a[i]
    a[i] = a[indexMin]
    a[indexMin] = w
    i = i + 1
end
p a

書いてみたが、これsortメソッドでできる。sortすごい。全体の要素を検証する添字iと、配列の中身を検証していくための添字kを回していくのが難しい。

バブルソート

単純交換法　右端から順に比較していく。右端とその左隣を比較して値が少ない方を左にずらしていく。難しいところはずらしていく添字、比較する２つの要素の右側を表す変数と、すでに確定した数字である要素の添字を定める発想。このすでに確定した要素の添字を置かないと無駄な動作が増えるため、必ず定めておくことが必要。
この発想に思い至るには、処理を何回繰り返すかを意識して置かなければいけない。何回繰り返すかを考えると添字の数の発想にたどり着く。

Rubyで書いてみた

array = [5, 3, 4, 1, 2]
k = 0 # =>　確定した添字を表す変数
while k < 4 # => kは配列のどこの要素を確定するかということを管理している
i = 4
    while i > k
        if array[i - 1] > array[i]
            w = array[i - 1]
            array[i - 1] = array[i]
            array[i] = w
            i -= 1
        else
            i -= 1
        end
      end
       k += 1 #=> array[0]が確定、次はarray[1]を確定させる番だという記し
end
p array