ソートのアルゴリズムを実装するその２　交換ソート

今回は、前回実装したバブルソートと同じように順番を交換していくことでソートするアルゴリズムを実装する

シェーカーソート

概要

バブルソートを少しだけ捻ったアルゴリズム バブルソートでは、リストの最初から順に比較して最後に達したらまた最初からという処理を繰り返していた。 シェーカーソートでは、同じように最初から順に比較して最後に達したら、今度は反転して後ろから前へと比較をしていき、最初に戻るとまた反転する、というふうに処理を繰り返す。 バブルソートがリストの最後尾、つまりは最大値から順に並べていたのに対して、シェーカーソートでは最大値と最小値の両極端から１つずつ並べていくというやり方だ。

アルゴリズム

def shaker array
    left = 0　　　#ソートされていない範囲の最前列
    right = array.length - 1　　#ソートされていない範囲の最後尾
    last_swap = 0　　#最後に値を交換した位置
    while true
      (left ... right).each do |i| #前から後ろへのソート
        if array[i] > array[i + 1]
          array[i], array[i + 1] = array[i + 1], array[i]
          last_swap = i + 1　　#この値から後ろの範囲は既にソート済み
        end
      end
      right = last_swap
      if left == right
        break
      end
      (left ... right).reverse_each do |i|#後ろから前へのソート
        if array[i + 1] < array[i]
          array[i], array[i + 1] = array[i + 1], array[i]
          last_swap = i　　#この値から後ろの範囲は既にソート済み
        end
      end
      left = last_swap
      if left == right
        break
      end
    end
end

このアルゴリズムでは前から後ろへの処理と後ろから前への処理の二種類を記述する必要があるのでコード量は多め しかし、アルゴリズム自体は単純なので実装は簡単

奇偶転置ソート

概要

奇数番目とその次の値でペアを作り（一番目と二番目の値、三番目と四番目の値・・・）、そのペアの中身をソートする。（Tier1） 偶数番目とその次の値でペアを作り（二番目と三番目の値、四番目と五番目の値・・・）、そのペアの中身をソートする。（Tier2） この２つの処理を繰り返すアルゴリズム

アルゴリズム

def odd_even array
    flag = true　　#ソートが行われたかどうか
    while flag
      flag = false
      1.step(array.length - 1, 2) do |i|　　#１から最後尾のインデックスの値までの奇数を生成
        if array[i] < array[i - 1]
          array[i], array[i - 1] = array[i - 1], array[i]
          flag = true
        end
      end
      2.step(array.length - 1, 2) do |i|　　#２から最後尾のインデックスの値までの偶数を生成
        if array[i] < array[i - 1]
          array[i], array[i - 1] = array[i - 1], array[i]
          flag = true
        end
      end
   end
end

ステップメソッドを使用してリストの最後尾のインデックスまでの奇数、偶数を生成する。 概要では「奇数番目とその次の値のペア」と説明したが、リストの範囲外を指定しないように「偶数番目とその前の値」というふうにペアを指定した。

このアルゴリズムはどのようにソートされていくのかがイメージしづらい こんな初歩で行き詰まっていたらこの先きついに違いないということで、一度アルゴリズムの学習を中断して、数値のリストから座標の図を作成し、その図の移り変わりを表示したgifを作成するプログラムを作成するのに挑戦してみようと思う。