Rubyで整列アルゴリズムを書いてみた。（単純交換法、選択法、挿入法＋クイックソート）

##はじめに
本記事ではこちらの本でアルゴリズムの勉強をしているので学んだことをRubyで書いて見ました。初心者なので簡単な記述法しか取れませんがよかったら読んで頂けたらと思います。間違い等あればコメントいただけると幸いです。
[アルゴリズムをはじめよう](https://www.amazon.co.jp/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%82%92%E3%80%81%E3%81%AF%E3%81%98%E3%82%81%E3%82%88%E3%81%86-%E4%BC%8A%E8%97%A4-%E9%9D%99%E9%A6%99-ebook/dp/B01CZDTINE/ref=sr_1_1?__mk_ja_JP=%E3%82%AB%E3%82%BF%E3%82%AB%E3%83%8A&crid=1IFTF2EOG9SW2&dchild=1&keywords=%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%82%92%E3%81%AF%E3%81%98%E3%82%81%E3%82%88%E3%81%86&qid=1588756149&sprefix=%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%2Caps%2C320&sr=8-1)

**【本記事で記述するアルゴリズム】**
・単純選択法
・単純交換法
・単純挿入法
・クイックソート

##単純交換法
一番小さなデータを選択して、先頭から順に並べるアルゴリズムで、主に下記の手順でできています。

①探索範囲の最小値を探す処理
②探索範囲の最小値を先頭要素と交換する処理

```ruby
def selection_ascending(array)
    i = 0
    #配列の末尾まで繰り返し処理
    while i < array.count-1
        k = i+1
        indexmin = i
        #①探索範囲の最小値を探す処理
        while k < array.count
            if array[k] < array[indexmin]
                indexmin = k
            end
            k += 1
        end
        #②探索範囲の最小値を先頭要素と交換する処理
        w = array[i]
        array[i] = array[indexmin]
        array[indexmin] = w
        i += 1
    end
    array
end
```

```:実行結果
array = Array.new(10)
array.each_index do |i|
    array[i] = rand(1000)
end
[835, 95, 359, 273, 102, 387, 932, 79, 434, 248]

election_ascending(array)
[79, 95, 102, 248, 273, 359, 387, 434, 835, 932]
```

##単純交換法（バブルソート）
隣り合ったデータを交換する処理を繰り返して、全体を整列させるアルゴリズム。
①配列の末尾の要素から順に、隣り合ったデータを並べ替える。
②先頭まで並び終えたら末尾に戻り再度並び替えを行う。

```ruby
def buble_ascending(array)
    
    k = 0

    while k < array.count
        i = array.count-1
        while k < i
            #①右端の要素から順に、隣り合ったデータを昇順に並べ替える
            if array[i] < array[i-1]
                w = array[i]
                array[i] = array[i-1]
                array[i-1] = w
            end
            i -= 1
        end
         #左端の要素から一つずつ順番にデータが昇順に整列する。
         k += 1
    end
    array
end
```
```:実行結果
#配列はランダムに作成しています。
array = [914, 433, 369, 664, 640, 352, 680, 970, 830, 108]
buble_ascending(array)
[108, 352, 369, 433, 640, 664, 680, 830, 914, 970]
```

##単純挿入法
単純挿入法では整列済みと未整列の2つの種類にデータを分けて考え、配列の0番目のデータを整列済みとして処理を開始します。挿入用データを格納する変数xとxを格納して空き要素となった配列を表す変数kを用意して処理を行います。

```ruby
def insertion_ascending(array)
    i = 1

    while i < array.count
        x = array[i]
        k = i

        while k > 0 && array[k-1] > x
            array[k] = array[k-1]
            k -= 1
        end

        array[k] = x
        i += 1
    end
    array
end
```
```:実行結果
array = [993, 424, 879, 719, 225, 987, 284, 239, 567, 844]
insertion_ascending(array)
[225, 239, 284, 424, 567, 719, 844, 879, 987, 993]
```

##クイックソート
データの基準となるものを選んで（今回は配列の先頭）データを大小二つのグループに分割しながら全体を整列させてるアルゴリズムです。メゾットの中で同じメゾットを呼び出すことによって大小に分ける処理を繰り返して配列を並び替えます。

```ruby
def quick_ascending(array,left,right)
    i = left+1
    k = right

    while i < k
        while i < right && array[i] < array[left]
            i += 1 
        end

        while left < k && array[k] >= array[left]
            k -= 1
        end

        if i < k
            w = array[i]
            array[i] = array[k]
            array[k] = w
        end
    end

    if array[left] > array[k]
        w = array[left]
        array[left] = array[k]
        array[k] = w
    end
    
    if  left < k-1
        quick_ascending(array,left,k-1)
    end

    if  k+1 < right
        quick_ascending(array,k+1,right)
    end

    array
end
```

```:実行結果
array = [207, 948, 857, 313, 475, 508, 609, 474, 664, 205]

quick_ascending(target,0,target.count-1)
[205, 207, 313, 474, 475, 508, 609, 664, 857, 948]
```

以上です。本当に基本的な書き方しかできてませんがここまでお読み頂きありがとうございました。