アルゴリズムとデータ構造

はじめに

以前から興味があったアルゴリズムを勉強することになり、rubyのコードにしています。
間違えているところなどあればコメントいただきたいです。
アルゴリズムは今後追加していきます。

エラトステネスの篩（ふるい）

algorithm.rb

def sieve_of_eratosthenes(n)
  numbers = (2..n).to_a
  primes = []

  while numbers.any?
    prime = numbers.shift
    primes << prime
    numbers.reject! { |num| num % prime == 0 }
  end

  primes
end

max_number = 30
primes = sieve_of_eratosthenes(max_number)

puts "Primes up to #{max_number}:"
puts primes.join(', ')

文字列の走査

algorithm.rb

text = "algorithm"
search_text = "b"

def find_character_index(text, search_text)
  index = 0
  while index < text.length
    if search_text == text[index]
      return index
    else
      index += 1
    end
  end
  return index
end

found_index = find_character_index(text, search_text)
puts found_index

文字列照合アルゴリズム

algorithm.rb

text = "algorithm"
search_text = "so"

def pattern_finder(text, search_text)
  i = 0
  j = 0
  
  while i + j < text.length
    if search_text[j] == text[i + j]
      j += 1
      if j == search_text.length
        return i
      end
    else
      i += 1
      j = 0
    end
  end
  return i
end

found_index = pattern_finder(text, search_text)
puts found_index

バブルソート

algorithm.rb

def bubble_sort(array)
  array_length = array.length

  while true
    swap_flag = false

    for j in 0...(array_length - 1)
      if array[j] > array[j + 1]
        array[j], array[j + 1] = array[j + 1], array[j]
        swap_flag = true
      end
    end

    break unless swap_flag
  end

  array
end

array = [2, 3, 6, 1, 5]
sorted_array = bubble_sort(array)
puts sorted_array 

選択ソート

algorithm.rb

def selection_sort(array)
  (array.length - 1).times do |i|
    min_index = i

    for j in (i + 1)...array.length
      min_index = j if array[j] < array[min_index]
    end

    array[i], array[min_index] = array[min_index], array[i] if i != min_index
  end

  array
end


array = [2, 3, 6, 1, 5]
sorted_array = selection_sort(array)
puts sorted_array

挿入ソート

algorithm.rb

def insertion_sort(array)
  (1...array.length).each do |i|
    value_to_insert = array[i]
    j = i - 1

    while j >= 0 && array[j] > value_to_insert
      array[j + 1] = array[j]
      j -= 1
    end

    array[j + 1] = value_to_insert
  end

  array
end


array = [2, 3, 6, 1, 5]
sorted_array = insertion_sort(array)
puts sorted_array

参考

アルゴリズムとデータ構造　藤田　聡　数理工学社
現役シリコンバレーエンジニアが教えるアルゴリズム・データ構造・コーディングテスト入門