ソートアルゴリズムは、データを特定の順序で整理するための手法です。データを整列することは、データの検索や解析を容易にし、効率的なアルゴリズムを設計する上で基本的なステップです。
この表は一般的なソートアルゴリズムの概要を示しており、実際の使用場面やデータの特性に応じて適切なアルゴリズムを選択することが重要です。
バブルソート（Bubble Sort）は、隣接する要素を比較し、必要に応じて交換を繰り返すことでソートを行います。
交換が一度も行われなくなるまで（ソートが完了するまで）繰り返します。
[https://paiza.io/projects/8ra8JiUwQ5KeoyFvvkcwQw?language=ruby 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）は、配列を走査しながら最小値を見つけ、それを未整列部分の先頭要素と交換します。これを配列全体に対して繰り返します。
[https://paiza.io/projects/x6wGDW0xe5xSZUo3vUSV7w?language=ruby 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）は、未整列部分の先頭要素を取り出し、それを整列済み部分に適切な位置に挿入します。
配列全体を整列済み部分と未整列部分に分け、未整列部分の要素を取り出して挿入することを繰り返します。
[https://paiza.io/projects/Zjj5fOEjmVY1NPa7FzubiA?language=ruby 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）は、データを分割し、それぞれをソートしてからマージ（結合）するアルゴリズムです。分割統治法を利用し、再帰的にデータを分割していきます。ソートされた部分列はマージ操作で結合され、最終的に全体がソートされます。
[https://paiza.io/projects/QRsy8lYKBWNc6BqI75LIkw?language=ruby 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）は、分割統治法を用いた効率的なソートアルゴリズムで、特に大きなデータセットに対して高速に動作します。ピボットと呼ばれる要素を選択し、その要素より小さい要素と大きい要素を分割することでソートを行います。その後、再帰的に各部分配列をソートします。
[https://paiza.io/projects/tQOoEG8ZSe1QWBrgFb5mvQ?language=ruby 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）は、ヒープデータ構造を使用して要素を整列させるアルゴリズムです。ヒープは完全二分木であり、最大（最小）ヒープを構築し、根から順に要素を取り出してソートします。効率的であり、安定性を持ちません。
[https://paiza.io/projects/Vj7IRxSf81FMzWN0U8nYoA?language=ruby 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）は、部分的にソートされたリストを作成し、それらを挿入ソートで整列させるアルゴリズムです。挿入ソートと同様に要素を逐次挿入しますが、要素間の間隔を広げることで効率化を図ります。
[https://paiza.io/projects/Ac8mfmWK3zF3c6Y-dXq7Mw?language=ruby 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）は、要素を複数のバケットに分割し、各バケットごとに別のソートアルゴリズム（通常は挿入ソートなど）を使用してソートし、最後にバケットを結合することでソートを行うアルゴリズムです。以下に、バケットソートの実装例とそのテストコードを示します。
[https://paiza.io/projects/gEEpwXHp9t7b4LgooEQTug?language=ruby 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）は、整数配列のソートアルゴリズムの一種です。一般的な比較ソートとは異なり、カウントソートは要素の大小関係を比較せず、要素の出現回数を数え上げてソートを行います。
具体的な手順は以下の通りです：
入力配列の要素の最小値と最大値を調べます。これにより、カウンティング用の配列のサイズを決定します。
カウンティング用の配列を初期化します。この配列は、入力配列の最大値と最小値の範囲内の要素の出現回数をカウントします。
入力配列を走査し、各要素の出現回数をカウンティング用の配列に記録します。
カウンティング用の配列を使って、ソート済みの配列を構築します。
入力配列を再度走査し、要素をソート済みの配列に配置します。この際、カウンティング用の配列の情報を利用して、各要素の正しい位置を特定します。
カウントソートは要素の出現回数をカウントするため、非負整数である必要があります。また、要素の範囲が大きい場合や要素が疎な場合には効率が悪くなる傾向がありますが、要素の範囲が比較的狭く、要素の重複が多い場合には高速に動作する特性があります。
[https://paiza.io/projects/W3ycjY6kZUgjOH59ugjdSA?language=ruby 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