【アルゴリズムの勉強】Rubyでシェルソートを書いてみる

Ruby アルゴリズム

アルゴリズムの勉強としてRubyでシェルソートを実装する。

シェルソートとは

シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、in-placeな比較ソートのアルゴリズムの一種である。シェルソートは、交換によるソート（バブルソート）あるいは挿入によるソート（挿入ソート）の一般化と見なすことができる[2]。ソートの方法は、まず、間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返す、というものである。離れた場所の要素からソートを始めることで、単純に近くの要素を比較する場合よりも速く、要素を所定の位置に移動させることができる。ただし、安定ソートではない。ドナルド・シェル（Donald L. Shell）が、1959年に、シェルソートの最初のバージョンを公開した[3][4] 。シェルソートの実行時間は、比較時に選ぶ間隔によって大きく異なる。多くの実用的な方法が提案されているが、正確な時間計算量を求める方法は、未解決問題である。

シェルソート - Wikipedia

Rubyで実装

arr = [4, 20, 6, 10, 15, 2, 60, 9, 25, 12]
number_of_elements = arr.count

def shell_sort(arr, number_of_elements)
  h = 1
  # 効率を上げるため、121, 40, 13, 4, 1となるような間隔を作る
  while h < (number_of_elements / 9)
    h = h * 3 + 1
  end
  while h > 0
    for i in h..(number_of_elements - 1)
      j = i - h
      target = arr[i]
      while j >= 0 && arr[j] > target
        arr[j + h] = arr[j]
        j += -h
      end
      arr[j + h] = target
    end
    h = h / 3
  end
  return arr
end

sorted_arr = shell_sort(arr, number_of_elements)
p sorted_arr
# => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]

参考文献、参考リンク

【アルゴリズムの勉強】Rubyで選択ソートを書いてみる

Ruby アルゴリズム

アルゴリズムの勉強としてRubyで選択ソートを実装する。

選択ソートとは

選択ソート（英: selection sort）は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。後述するように、安定ソートではない。
このアルゴリズムを改良したソート法として、ヒープソートが挙げられる。

選択ソート - Wikipedia

Rubyで実装

arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12]
number_of_elements = arr.count

def selection_sort(arr, number_of_elements)
  (number_of_elements - 1).times{|i|
    min = i
    for j in (i + 1)..(number_of_elements - 1)
      if arr[j] < arr[min]
        min = j;
      end
    end
    arr[i], arr[min] = arr[min], arr[i]
  }
  return arr
end

sorted_arr = selection_sort(arr, number_of_elements)
p sorted_arr
# => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]

参考文献

【アルゴリズムの勉強】Rubyで挿入ソートを書いてみる

Ruby アルゴリズム

アルゴリズムの勉強としてRubyで挿入ソートを実装する。

挿入ソートとは

挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。
挿入ソートを高速化したソート法として、シェルソートが知られている。

挿入ソート - Wikipedia


Rubyで実装

arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12]
number_of_elements = arr.count
DESC, ASC = 1, 2

def insertion_sort(arr, number_of_elements, order)
  for i in 1..(number_of_elements - 1)
    target = arr[i]
    j = i
    if order == ASC
      while (j > 0) && (arr[j - 1] > target)
        arr[j] = arr[j - 1]
        j += -1
      end
    elsif order == DESC
      while (j > 0) && (arr[j - 1] < target)
        arr[j] = arr[j - 1]
        j += -1
      end
    end
    arr[j] = target
  end
  return arr
end

asc_sorted_arr = insertion_sort(arr, number_of_elements, ASC)
p asc_sorted_arr
# => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]
desc_sorted_arr = insertion_sort(arr, number_of_elements, DESC)
p desc_sorted_arr
# => [60, 25, 20, 15, 12, 10, 9, 6, 4, 2]

参考文献

【アルゴリズムの勉強】Rubyでバブルソートを書いてみる

Ruby アルゴリズム

アルゴリズムの勉強としてRubyでバブルソートを実装する。

バブルソートとは

ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある）

バブルソート - Wikipedia


Rubyで実装

arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12]
number_of_elements = arr.count
# 降順, 昇順
ASC, DESC = 1, 2

def bubble_sort(arr, number_of_elements, order)
  for i in 1..(number_of_elements - 1)
    (number_of_elements - i).times{|j|
      if order == ASC
        if (arr[j] > arr[j + 1])
          arr[j], arr[j + 1] = arr[j + 1], arr[j]
        end
      elsif order == DESC
        if (arr[j] < arr[j + 1])
          arr[j], arr[j + 1] = arr[j + 1], arr[j]
        end
      end
    }
  end
  return arr
end

asc_sorted_arr = bubble_sort(arr, number_of_elements, ASC)
p asc_sorted_arr
# => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]
desc_sorted_arr = bubble_sort(arr, number_of_elements, DESC)
p desc_sorted_arr
# => [60, 25, 20, 15, 12, 10, 9, 6, 4, 2]

参考文献