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.