Exploring Sorting Algorithms with Ruby: A Comprehensive Guide

Sorting Algorithms

Bubble Sort

Bubble sort is one of the simplest sorting algorithms. It works by repeatedly stepping through the list, comparing each pair of adjacent items and swapping them if they are in the wrong order. This process continues until the list is sorted.

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

array = [64, 34, 25, 12, 22, 11, 90]
puts "Sorted array using Bubble Sort: #{bubble_sort(array)}"

Selection Sort

Selection sort works by repeatedly finding the minimum element from the unsorted portion of the array and moving it to the beginning. This process is repeated until the entire array is sorted.

def selection_sort(arr)
  n = arr.length
  (0...n).each do |i|
    min_index = i
    (i + 1...n).each do |j|
      min_index = j if arr[j] < arr[min_index]
    end
    arr[i], arr[min_index] = arr[min_index], arr[i]
  end
  arr
end

array = [64, 34, 25, 12, 22, 11, 90]
puts "Sorted array using Selection Sort: #{selection_sort(array)}"

Merge Sort

Merge sort is a divide-and-conquer algorithm. It divides the input array into two halves, recursively sorts each half, and then merges them back together.

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

  mid = arr.length / 2
  left_half = arr[0...mid]
  right_half = arr[mid..]

  merge(merge_sort(left_half), merge_sort(right_half))
end

def merge(left, right)
  result = []
  until left.empty? || right.empty?
    result << (left.first <= right.first ? left.shift : right.shift)
  end
  result.concat(left).concat(right)
end

array = [64, 34, 25, 12, 22, 11, 90]
puts "Sorted array using Merge Sort: #{merge_sort(array)}"

Conclusion

Sorting algorithms play a crucial role in various applications, from simple data organization tasks to complex data analysis. In this blog post, we’ve explored three different sorting algorithms: Bubble Sort, Selection Sort, and Merge Sort, using Ruby as our implementation language. Each algorithm has its own characteristics and performance considerations, and understanding them allows us to make informed choices when sorting data in our programs.

Tags: Ruby