Ruby Programming Language and Its Most Used Set of Algorithms

Ruby Programming Language and Its Most Used Set of Algorithms 30/03/2023 ~ Views: 929

Ruby is a popular object-oriented programming language known for its simplicity, expressiveness, and flexibility. It was created in the mid-1990s by Yukihiro "Matz" Matsumoto and has since gained popularity among developers for its ease of use and readability. In this post, we will take a look at some of the most commonly used algorithms in Ruby, along with code examples for each.

Sorting Algorithms

Sorting algorithms are used to arrange a list of elements in a specific order, such as ascending or descending. The following are some of the most commonly used sorting algorithms in Ruby:

Bubble Sort

Bubble sort is one of the simplest sorting algorithms and works by repeatedly swapping adjacent elements if they are in the wrong order. Here's an implementation of bubble sort in 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 if not swapped
  end

  array
end

arr = [3, 5, 2, 1, 4]
p bubble_sort(arr)

Insertion Sort

Insertion sort works by building a final sorted array one element at a time, by comparing each new element with the already sorted elements and inserting it at the correct position. Here's an implementation of insertion sort in Ruby:

def insertion_sort(array)
  for i in 1...(array.length)
    key = array[i]
    j = i - 1

    while j >= 0 and array[j] > key
      array[j+1] = array[j]
      j -= 1
    end

    array[j+1] = key
  end

  array
end

arr = [3, 5, 2, 1, 4]
p insertion_sort(arr)

Selection Sort

Selection sort works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning. Here's an implementation of selection sort in Ruby:

def selection_sort(array)
  n = array.length

  for i in 0...(n-1)
    min_index = i

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

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

  array
end

arr = [3, 5, 2, 1, 4]
p selection_sort(arr)

Quick Sort

Quick sort is a divide-and-conquer sorting algorithm that works by selecting a 'pivot' element and partitioning the array around the pivot, recursively sorting the left and right subarrays. Here's an implementation of quick sort in Ruby:

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

  pivot = array.delete_at(rand(array.length))
  left, right = array.partition { |num| num < pivot }

  return *quick_sort(left), pivot, *quick_sort(right)
end

arr = [3, 5, 2, 1, 4]
p quick_sort(arr)

Merge Sort

Merge sort is another divide-and-conquer algorithm that works by recursively dividing the array into halves, sorting them, and then merging them. Here's an implementation of merge sort in Ruby:

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

  mid = array.length / 2
  left = array[0...mid]
  right = array[mid..-1]

  merge(merge_sort(left), merge_sort(right))
end

def merge(left, right)
  sorted = []

  until left.empty? || right.empty?
    if left.first <= right.first
      sorted << left.shift
    else
      sorted << right.shift
    end
  end

  sorted.concat(left).concat(right)
end

arr = [3, 5, 2, 1, 4]
p merge_sort(arr)

Searching Algorithms

Searching algorithms are used to find the position or occurrence of a specific element in a list. The following are some of the most commonly used searching algorithms in Ruby:

Linear Search

Linear search is the simplest search algorithm that works by iterating through each element in the list until the target element is found. Here's an implementation of linear search in Ruby:

def linear_search(array, target)
  array.each_with_index do |element, index|
    return index if element == target
  end

  nil
end

arr = [1, 2, 3, 4, 5]
p linear_search(arr, 3)

Binary Search

Binary search is a more efficient search algorithm that works by dividing the list in half at each step and eliminating half of the remaining elements until the target element is found. Here's an implementation of binary search in Ruby:

def binary_search(array, target)
  low = 0
  high = array.length - 1

  while low <= high
    mid = (low + high) / 2

    if array[mid] == target
      return mid
    elsif array[mid] < target
      low = mid + 1
    else
      high = mid - 1
    end
  end

  nil
end

arr = [1, 2, 3, 4, 5]
p binary_search(arr, 3)

Graph Algorithms

Breadth-First Search (BFS)

Breadth-first search is a graph traversal algorithm that visits all the vertices of a graph in breadth-first order, i.e., it visits all the vertices at the same level before moving to the next level. Here's an implementation of BFS in Ruby:

def bfs(graph, start)
  queue = [start]
  visited = []

  until queue.empty?
    vertex = queue.shift
    next if visited.include?(vertex)

    visited << vertex
    queue.concat(graph[vertex])
  end

  visited
end

graph = {
  'A' => ['B', 'C'],
  'B' => ['A', 'D', 'E'],
  'C' => ['A', 'F'],
  'D' => ['B'],
  'E' => ['B', 'F'],
  'F' => ['C', 'E']
}

p bfs(graph, 'A')

Depth-First Search (DFS)

Depth-first search is a graph traversal algorithm that visits all the vertices of a graph in depth-first order, i.e., it visits all the vertices in a branch before moving to the next branch. Here's an implementation of DFS in Ruby:

def dfs(graph, start)
  stack = [start]
  visited = []

  until stack.empty?
    vertex = stack.pop
    next if visited.include?(vertex)

    visited << vertex
    stack.concat(graph[vertex])
  end

  visited
end

graph = {
  'A' => ['B', 'C'],
  'B' => ['A', 'D', 'E'],
  'C' => ['A', 'F'],
  'D' => ['B'],
  'E' => ['B', 'F'],
  'F' => ['C', 'E']
}

p dfs(graph, 'A')

Dijkstra's Algorithm

Dijkstra's algorithm is a shortest path algorithm that finds the shortest path from a source vertex to all other vertices in a weighted graph. Here's an implementation of Dijkstra's algorithm in Ruby:

def dijkstra(graph, source)
  distances = {}
  previous = {}
  unvisited = graph.keys

  graph.each do |vertex, edges|
    distances[vertex] = Float::INFINITY
    previous[vertex] = nil
  end

  distances[source] = 0

  until unvisited.empty?
    current = unvisited.min_by { |vertex| distances[vertex] }
    unvisited.delete(current)

    graph[current].each do |neighbor, weight|
      alt = distances[current] + weight

      if alt < distances[neighbor]
        distances[neighbor] = alt
        previous[neighbor] = current
      end
    end
  end

  [distances, previous]
end

graph = {
  'A' => { 'B' => 5, 'C' => 10 },
  'B' => { 'D' => 7, 'E' => 2 },
  'C' => { 'F' => 5 },
  'D' => { 'E' => 1 },
  'E' => { 'F' => 3 },
  'F' => {}
}

distances, previous = dijkstra(graph, 'A')

p distances
p previous

String Manipulation Algorithms

Reverse a String

Reversing a string involves reversing the order of characters in the string. Here's an implementation of string reversal in Ruby:

def reverse_string(string)
  string.reverse
end

Palindrome Detection

A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward. Here's an implementation of palindrome detection in Ruby:

def palindrome?(string)
  string == string.reverse
end

String Permutations

A string permutation is any possible rearrangement of the characters in a string. Here's an implementation of string permutation generation in Ruby:

def string_permutations(string)
  return [string] if string.size == 1

  result = []

  string.chars.each_with_index do |char, index|
    remaining = string[0...index] + string[index+1..-1]
    string_permutations(remaining).each do |perm|
      result << char + perm
    end
  end

  result
end

p string_permutations("abc")

Longest Common Substring

A common substring of two strings is a substring that appears in both strings. The longest common substring is the longest substring that appears in both strings. Here's an implementation of longest common substring finding in Ruby:

def longest_common_substring(str1, str2)
  m = str1.length
  n = str2.length
  l = Array.new(m+1) { Array.new(n+1, 0) }
  result = ""

  (0..m).each do |i|
    (0..n).each do |j|
      if i == 0 || j == 0
        l[i][j] = 0
      elsif str1[i-1] == str2[j-1]
        l[i][j] = l[i-1][j-1] + 1
        result = str1[i-l[i][j]..i-1] if l[i][j] > result.length
      else
        l[i][j] = 0
      end
    end
  end

  result
end

p longest_common_substring("abcdef", "abcde")

These are just a few examples of the many algorithms and techniques available in Ruby for sort, search, graph traversal and string manipulation. With the power of Ruby's concise syntax and built-in data structures, these algorithms can be implemented with ease, making Ruby a popular choice among developers for a wide range of applications.

Tags: #ruby #programminglanguage #algorithms #graph #chatgpt #stringmanipulation #depthfirstsearch #dijkstrasalgorithm #sortalgorithms #searchalgorithms

Back

OPEN TO HIRE

Nezir Zahirovic

Ruby On Rails Full stack last 8 years.
C#, ASP.NET, JavaScript, SQL, CSS, Bootstrap 11 years.