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 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.