Rubyで学ぶアルゴリズムとデータ構造

◇前置き

Rubyは、簡潔な文法と高度なオブジェクト指向機能を備えたプログラミング言語です。

この言語を使用することで、アルゴリズムとデータ構造を学ぶことができます。

この記事では、Rubyを使用して、代表的なアルゴリズムとデータ構造を実装する方法を説明します。

◇アルゴリズムとデータ構造の概要

アルゴリズムとデータ構造は、プログラミングにおいて非常に重要な役割を担っています。

アルゴリズムは、問題を解決するための手順や方法論のことです。

データ構造は、データを効率的に保存・操作するための方法論のことです。

◇アルゴリズム

<バブルソート>

バブルソートは、隣り合う要素を比較して、必要に応じて交換することで、リストをソートするアルゴリズムです。

以下は、Rubyでバブルソートを実装する例です。

def bubble_sort(arr)
  n = arr.length
  loop do
    swapped = false
    (n-1).times do |i|
      if arr[i] > arr[i+1]
        arr[i], arr[i+1] = arr[i+1], arr[i]
        swapped = true
      end
    end
    break unless swapped
  end
  arr
end
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
puts bubble_sort(arr) #=> [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

<二分探索>

二分探索は、昇順または降順にソートされたリストを対象として、中央の要素と探索対象の値を比較します。

探索対象の値が中央の要素よりも小さい場合は、中央よりも左側を探索対象とし、大きい場合は中央よりも右側を探索対象とするアルゴリズムです。

以下は、Rubyで二分探索を実装する例です。

def binary_search(arr, target)
  low = 0
  high = arr.length - 1
  while low <= high
    mid = (low + high) / 2
    if arr[mid] == target
      return mid
    elsif arr[mid] < target
      low = mid + 1
    else
      high = mid - 1
    end
  end
  return nil
end
arr = [1, 3, 5, 7, 9, 11, 13, 15]
puts binary_search(arr, 7) #=> 3

◇データ構造

<スタック>

スタックは、データを一時的に保存するためのデータ構造であり、LIFO（Last In, First Out）の方式でデータが保存されます。

以下は、Rubyでスタックを実装する例です。

class Stack
  def initialize
    @stack = []
  end
  def push(item)
    @stack.push(item)
  end
  def pop
    @stack.pop
  end
  def size
    @stack.length
  end
  def empty?
    @stack.empty?
  end
end
stack = Stack.new
stack.push(1)
stack.push(2)
stack.push(3)

puts stack.pop #=> 3
puts stack.pop #=> 2
puts stack.pop #=> 1

<キュー>

キューは、データを一時的に保存するためのデータ構造であり、FIFO（First In, First Out）の方式でデータが保存されます。

以下は、Rubyでキューを実装する例です。

class Queue
  def initialize
    @queue = []
  end
  def enqueue(item)
    @queue.push(item)
  end
  def dequeue
    @queue.shift
  end
  def size
    @queue.length
  end
  def empty?
    @queue.empty?
  end
end
queue = Queue.new
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

puts queue.dequeue #=> 1
puts queue.dequeue #=> 2
puts queue.dequeue #=> 3