ソートアルゴリズム

ソートアルゴリズムは、データを特定の順序で整理するための手法です。データを整列することは、データの検索や解析を容易にし、効率的なアルゴリズムを設計する上で基本的なステップです。

ソートアルゴリズムの種類と特性

アルゴリズム	時間計算量	安定性	メモリ使用量	説明
バブルソート	最良：$O(n)$ 平均・最悪：$O(n^{2})$	Yes	$O(1)$	隣接する要素を比較・交換して、未整列の要素を順次移動させるアルゴリズム
選択ソート	最良・平均・最悪：$O(n^{2})$	No	$O(1)$	未整列の部分から最小値を見つけて、整列済みの部分の最後に挿入するアルゴリズム
挿入ソート	最良：$O(n)$ 平均・最悪：$O(n^{2})$	Yes	$O(1)$	未整列の要素を適切な位置に挿入していくアルゴリズム
マージソート	最良・平均・最悪：$O(n\log n)$	Yes	$O(n)$	データを分割し、それぞれをソートしてからマージ（結合）するアルゴリズム
クイックソート	最良・平均：$O(n\log n)$ 最悪：$O(n^{2})$	No	$O(\log n)$	ピボットを選択し、ピボットより小さい要素と大きい要素を分割して、それぞれを再帰的にソートするアルゴリズム
ヒープソート	最良・平均・最悪：$O(n\log n)$	No	$O(1)$	ヒープデータ構造を使用して要素を整列させるアルゴリズム
シェルソート	最良・平均：$O(n\log n)$ 最悪：$O(n(\log n^{2})$)	No	$O(1)$	部分的にソートされたリストを作成し、それらを挿入ソートで整列させるアルゴリズム
バケットソート	最良・平均：$O(n+k)$ 最悪：$O(n^{2})$	Yes	$O(n+k)$	データの範囲を分割し、各範囲に対応するバケットを使用して要素を整列させるアルゴリズム
カウントソート	最良・平均・最悪：$O(n+k)$	Yes	$O(n+k)$	各要素の出現回数を数え、その情報を元に要素を整列させるアルゴリズム

この表は一般的なソートアルゴリズムの概要を示しており、実際の使用場面やデータの特性に応じて適切なアルゴリズムを選択することが重要です。

さまざまなソートアルゴリズム

バブルソート

バブルソート（Bubble Sort）は、隣接する要素を比較し、必要に応じて交換を繰り返すことでソートを行います。 交換が一度も行われなくなるまで（ソートが完了するまで）繰り返します。

Rubyでの実装例

def bubble_sort(array)
  n = array.length
  loop do
    swapped = false
    (n - 1).times do |i|
      if array[i] > array[i + 1]
        array[i], array[i + 1] = array[i + 1], array[i]
        swapped = true
      end
    end
    break unless swapped
  end
  array
end

require 'minitest/autorun'

class TestBubbleSort < Minitest::Test
  def test_sort
    assert_equal [], bubble_sort([])
    assert_equal [1], bubble_sort([1])
    assert_equal [1, 2, 3, 4, 5], bubble_sort([5, 3, 2, 4, 1])
    assert_equal [1, 2, 3, 4, 5, 6], bubble_sort([6, 5, 3, 2, 4, 1])
    assert_equal [-5, -4, -3, -2, -1], bubble_sort([-1, -3, -2, -5, -4])
    assert_equal [1, 2, 3, 4, 5], bubble_sort([1, 2, 3, 4, 5])
    ary = (0...1000).to_a
    assert_equal ary, bubble_sort(ary.shuffle)
  end
end

選択ソート

選択ソート（Selection Sort）は、配列を走査しながら最小値を見つけ、それを未整列部分の先頭要素と交換します。これを配列全体に対して繰り返します。

Rubyでの実装例

def selection_sort(array)
  n = array.length
  (n - 1).times do |i|
    min_index = i
    (i + 1).upto(n - 1) do |j|
      min_index = j if array[j] < array[min_index]
    end
    array[i], array[min_index] = array[min_index], array[i] if min_index != i
  end
  array
end

require 'minitest/autorun'

class TestSelectionSort < Minitest::Test
  def test_sort
    assert_equal [], selection_sort([])
    assert_equal [1], selection_sort([1])
    assert_equal [1, 2, 3, 4, 5], selection_sort([5, 3, 2, 4, 1])
    assert_equal [1, 2, 3, 4, 5, 6], selection_sort([6, 5, 3, 2, 4, 1])
    assert_equal [-5, -4, -3, -2, -1], selection_sort([-1, -3, -2, -5, -4])
    assert_equal [1, 2, 3, 4, 5], selection_sort([1, 2, 3, 4, 5])
    ary = (0...1000).to_a
    assert_equal ary, selection_sort(ary.shuffle)
  end
end

挿入ソート

挿入ソート（Insertion Sort）は、未整列部分の先頭要素を取り出し、それを整列済み部分に適切な位置に挿入します。 配列全体を整列済み部分と未整列部分に分け、未整列部分の要素を取り出して挿入することを繰り返します。

Rubyでの実装例

def insertion_sort(array)
  n = array.length
  1.upto(n - 1) do |i|
    key = array[i]
    j = i - 1
    while j >= 0 && array[j] > key
      array[j + 1] = array[j]
      j -= 1
    end
    array[j + 1] = key
  end
  array
end

require 'minitest/autorun'

class TestInsertionSort < Minitest::Test
  def test_sort
    assert_equal [], insertion_sort([])
    assert_equal [1], insertion_sort([1])
    assert_equal [1, 2, 3, 4, 5], insertion_sort([5, 3, 2, 4, 1])
    assert_equal [1, 2, 3, 4, 5, 6], insertion_sort([6, 5, 3, 2, 4, 1])
    assert_equal [-5, -4, -3, -2, -1], insertion_sort([-1, -3, -2, -5, -4])
    assert_equal [1, 2, 3, 4, 5], insertion_sort([1, 2, 3, 4, 5])
    ary = (0...1000).to_a
    assert_equal ary, insertion_sort(ary.shuffle)
  end
end

マージソート

マージソート（Merge Sort）は、データを分割し、それぞれをソートしてからマージ（結合）するアルゴリズムです。分割統治法を利用し、再帰的にデータを分割していきます。ソートされた部分列はマージ操作で結合され、最終的に全体がソートされます。

Rubyでの実装例

def merge_sort(array)
  return array if array.length <= 1

  mid = array.length / 2
  left_half = merge_sort(array[0...mid])
  right_half = merge_sort(array[mid..])

  merge(left_half, right_half)
end

def merge(left, right)
  sorted = []
  until left.empty? || right.empty?
    sorted << (left.first <= right.first ? left.shift : right.shift)
  end
  sorted.concat(left).concat(right)
end

require 'minitest/autorun'

class TestMergeSort < Minitest::Test
  def test_sort
    assert_equal [], merge_sort([])
    assert_equal [1], merge_sort([1])
    assert_equal [1, 2, 3, 4, 5], merge_sort([5, 3, 2, 4, 1])
    assert_equal [1, 2, 3, 4, 5, 6], merge_sort([6, 5, 3, 2, 4, 1])
    assert_equal [-5, -4, -3, -2, -1], merge_sort([-1, -3, -2, -5, -4])
    assert_equal [1, 2, 3, 4, 5], merge_sort([1, 2, 3, 4, 5])
    ary = (0...1000).to_a
    assert_equal ary, merge_sort(ary.shuffle)
  end
end

クイックソート

クイックソート（Quick Sort）は、分割統治法を用いた効率的なソートアルゴリズムで、特に大きなデータセットに対して高速に動作します。ピボットと呼ばれる要素を選択し、その要素より小さい要素と大きい要素を分割することでソートを行います。その後、再帰的に各部分配列をソートします。

Rubyでの実装例

def quick_sort(array)
  return array if array.length <= 1

  pivot = array.sample
  left, right = array.partition { |element| element < pivot }
  quick_sort(left) + quick_sort(right)
end

require 'minitest/autorun'

class TestQuickSort < Minitest::Test
  def test_sort
    assert_equal [], quick_sort([])
    assert_equal [1], quick_sort([1])
    assert_equal [1, 2, 3, 4, 5], quick_sort([5, 3, 2, 4, 1])
    assert_equal [1, 2, 3, 4, 5, 6], quick_sort([6, 5, 3, 2, 4, 1])
    assert_equal [-5, -4, -3, -2, -1], quick_sort([-1, -3, -2, -5, -4])
    assert_equal [1, 2, 3, 4, 5], quick_sort([1, 2, 3, 4, 5])
    ary = (0...1000).to_a
    assert_equal ary, quick_sort(ary.shuffle)
  end
end

ヒープソート

ヒープソート（Heap Sort）は、ヒープデータ構造を使用して要素を整列させるアルゴリズムです。ヒープは完全二分木であり、最大（最小）ヒープを構築し、根から順に要素を取り出してソートします。効率的であり、安定性を持ちません。

Rubyでの実装例

def heap_sort(array)
  n = array.length

  # 最大ヒープを構築
  (n / 2 - 1).downto(0) do |i|
    heapify(array, n, i)
  end

  # ヒープから要素を取り出してソート
  (n - 1).downto(1) do |i|
    array[0], array[i] = array[i], array[0] # 最大要素を末尾に移動
    heapify(array, i, 0) # ヒープサイズを減らしてヒープを再構築
  end

  array
end

def heapify(array, n, i)
  largest = i
  left = 2 * i + 1
  right = 2 * i + 2

  largest = left if left < n && array[left] > array[largest]
  largest = right if right < n && array[right] > array[largest]

  if largest != i
    array[i], array[largest] = array[largest], array[i]
    heapify(array, n, largest)
  end
end

require 'minitest/autorun'

class TestHeapSort < Minitest::Test
  def test_sort
    assert_equal [], heap_sort([])
    assert_equal [1], heap_sort([1])
    assert_equal [1, 2, 3, 4, 5], heap_sort([5, 3, 2, 4, 1])
    assert_equal [1, 2, 3, 4, 5, 6], heap_sort([6, 5, 3, 2, 4, 1])
    assert_equal [-5, -4, -3, -2, -1], heap_sort([-1, -3, -2, -5, -4])
    assert_equal [1, 2, 3, 4, 5], heap_sort([1, 2, 3, 4, 5])
    ary = (0...1000).to_a
    assert_equal ary, heap_sort(ary.shuffle)
  end
end

シェルソート

シェルソート（Shell Sort）は、部分的にソートされたリストを作成し、それらを挿入ソートで整列させるアルゴリズムです。挿入ソートと同様に要素を逐次挿入しますが、要素間の間隔を広げることで効率化を図ります。

Rubyでの実装例

def shell_sort(array)
  n = array.length
  gap = n / 2

  while gap > 0
    gap.upto(n - 1) do |i|
      temp = array[i]
      j = i
      while j >= gap && array[j - gap] > temp
        array[j] = array[j - gap]
        j -= gap
      end
      array[j] = temp
    end
    gap /= 2
  end

  array
end

require 'minitest/autorun'

class TestShellSort < Minitest::Test
  def test_sort
    assert_equal [], shell_sort([])
    assert_equal [1], shell_sort([1])
    assert_equal [1, 2, 3, 4, 5], shell_sort([5, 3, 2, 4, 1])
    assert_equal [1, 2, 3, 4, 5, 6], shell_sort([6, 5, 3, 2, 4, 1])
    assert_equal [-5, -4, -3, -2, -1], shell_sort([-1, -3, -2, -5, -4])
    assert_equal [1, 2, 3, 4, 5], shell_sort([1, 2, 3, 4, 5])
    ary = (0...1000).to_a
    assert_equal ary, shell_sort(ary.shuffle)
  end
end

バケットソート

バケットソート（Bucket Sort）は、要素を複数のバケットに分割し、各バケットごとに別のソートアルゴリズム（通常は挿入ソートなど）を使用してソートし、最後にバケットを結合することでソートを行うアルゴリズムです。以下に、バケットソートの実装例とそのテストコードを示します。

Rubyでの実装例

def bucket_sort(array, bucket_size = 5)
  return array if array.length < 2

  # 入力配列の最小値と最大値を取得
  min_value = array.min
  max_value = array.max

  # バケットを作成
  bucket_count = ((max_value - min_value) / bucket_size).floor + 1
  buckets = Array.new(bucket_count) { [] }

  # 配列の各要素を適切なバケットに振り分ける
  array.each do |element|
    index = ((element - min_value) / bucket_size).floor
    buckets[index] << element
  end

  # 各バケットをソートし、結合
  sorted_array = []
  buckets.each do |bucket|
    insertion_sort(bucket) # ここで別のソートアルゴリズムを使用
    sorted_array.concat(bucket)
  end

  sorted_array
end

# 挿入ソート
def insertion_sort(array)
  n = array.length
  1.upto(n - 1) do |i|
    key = array[i]
    j = i - 1
    while j >= 0 && array[j] > key
      array[j + 1] = array[j]
      j -= 1
    end
    array[j + 1] = key
  end
  array
end

require 'minitest/autorun'

class TestBucketSort < Minitest::Test
  def test_sort
    assert_equal [], bucket_sort([])
    assert_equal [1], bucket_sort([1])
    assert_equal [1, 2, 3, 4, 5], bucket_sort([5, 3, 2, 4, 1])
    assert_equal [1, 2, 3, 4, 5, 6], bucket_sort([6, 5, 3, 2, 4, 1])
    assert_equal [-5, -4, -3, -2, -1], bucket_sort([-1, -3, -2, -5, -4])
    assert_equal [1, 2, 3, 4, 5], bucket_sort([1, 2, 3, 4, 5])
    ary = (0...1000).to_a
    assert_equal ary, bucket_sort(ary.shuffle)
  end
end

カウントソート

カウントソート（Counting Sort）は、整数配列のソートアルゴリズムの一種です。一般的な比較ソートとは異なり、カウントソートは要素の大小関係を比較せず、要素の出現回数を数え上げてソートを行います。

具体的な手順は以下の通りです：

1. 入力配列の要素の最小値と最大値を調べます。これにより、カウンティング用の配列のサイズを決定します。

カウンティング用の配列を初期化します。この配列は、入力配列の最大値と最小値の範囲内の要素の出現回数をカウントします。

1. 入力配列を走査し、各要素の出現回数をカウンティング用の配列に記録します。
2. カウンティング用の配列を使って、ソート済みの配列を構築します。
3. 入力配列を再度走査し、要素をソート済みの配列に配置します。この際、カウンティング用の配列の情報を利用して、各要素の正しい位置を特定します。

カウントソートは要素の出現回数をカウントするため、非負整数である必要があります。また、要素の範囲が大きい場合や要素が疎な場合には効率が悪くなる傾向がありますが、要素の範囲が比較的狭く、要素の重複が多い場合には高速に動作する特性があります。

Rubyでの実装例

def count_sort(array)
  return array if array.length < 2
  min_value, max_value = array.minmax
  count_array = Array.new(max_value - min_value + 1, 0)

  array.each { |value| count_array[value - min_value] += 1 }

  sorted_array = []
  count_array.each_with_index do |count, i|
    count.times { sorted_array << i + min_value }
  end

  sorted_array
end

require 'minitest/autorun'

class TestCountSort < Minitest::Test
  def test_sort
    assert_equal [], count_sort([])
    assert_equal [1], count_sort([1])
    assert_equal [1, 2, 3, 4, 5], count_sort([5, 3, 2, 4, 1])
    assert_equal [1, 2, 3, 4, 5, 6], count_sort([6, 5, 3, 2, 4, 1])
    assert_equal [-5, -4, -3, -2, -1], count_sort([-1, -3, -2, -5, -4])
    assert_equal [1, 2, 3, 4, 5], count_sort([1, 2, 3, 4, 5])
    ary = (0...1000).to_a
    assert_equal ary, count_sort(ary.shuffle)
    assert_equal [28, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31], count_sort([31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31])
  end
end