Nathan Bolser

Sorting and Searching Algorithms in Ruby

May 30, 2019

Writing programs isn’t the goal of computer science. The real goal of computer science is to solve problems efficiently and effectively. So, here we go with sorting algorithms.

Sorting problem descriptions could be summarized as follows:

Given a list of arbitrarily ordered elements in a list, reorder them so that the appear according to their ordinal values from lowest to highest.

Select Sort

The selection sort solution is to essentially look for the smallest item in a list and bring that element to the front. To do this, two array would need to be maintained. One to hold the processed list, the other maintains the unprocessed list.

Definition

Start with a list as unprocessed.
Find the smallest element in the unprocessed list and reset the unprocessed list starting with the second element.
Repeat step 2 for an additional n-2 times for the remaining n-1 numbers in the list. After n - 1 iterations, the nth element is the largest and in the correct location.

def selection_sort(array)
  n = array.length - 1
  n.times do |i|
    min = i
    for j in (i + 1)..n
      min = j if array[j] < array[min]
    end
    array[i], array[min] = array[min], array[i] unless min == i
  end
  array
end

Insertion Sort

Insertion sorts work by leaving the first element alone and declaring it as a sorted list the size of one. The next element is inserted into the right position in the newly sorted list, above or below the element the sort was started with. This process continues by taking each new element and inserting it into the correct position in the list. The end results is a single, sorted list.

Definition

Consider the first element of the input list as sorted
Examine the next element and insert that element into the proper position in the already sorted list.
Repeat this process of adding one new number for all numbers in the list.

def insertion_sort(array)
  array.length.times do |j|
    while j > 0
      if array[j-1] > array[j]
        array[j], array[j-1] = array[j-1], array[j]array[j] is smaller
      else
        break
      end
      j-=1
    end
  end
  array
end

Bubble Sort

The premise of the bubble sort is that if we repeatedly place successive elements in order, eventually the smallest elements will “bubble” towards the beginning, while the larger elements will “bubble” towards the end of the list. The bubble sort works by comparing the element to the right of the current element. If the element to the right is smaller a swap occurs and the smaller element now the current element. The bubble sort must iterate over each element in the array which could result in a performance hit.

Definition

Loop through all entries of the list.
Compare each entry to all successive entries and swap the entries if they are out of order.
Repeat this process.

def bubble_sort(array, swap=true)
  return array unless array.size >= 1
    while swap
      swap = false
      (array.length - 1).times do |i|
        if array[i] > array[i+1]next element
          array[i], array[i+1] = array[i+1], array[i]
          swap = true
        end
      end
    end
  array
end

It's me... Nathan. Technical lead living in Denver, CO. Enjoys working with Ruby, Rails, Javascript, React, AWS. Also enjoys mountain biking, fly fishing, skiing, travel, and spending time with my Labrador Retriever, Bart.

← Hello World