Quicksort in Ruby

One of the fastest sorting algorithms is quicksort. To sort a list of items via quicksort:

(1) Pick a random element from the list; this is the pivot.

(2) Go through each of the other elements of the list. For each element, if it’s smaller than the pivot, it goes into a new “left array” to the left of the pivot; if it’s larger than the pivot, it goes into a new “right array” to the right of the pivot.

(3) After that, if the new arrays each contain only one element, you’re basically done: the sorted list consists of the left array + pivot + right array.

(3) If the new arrays each contain more than one element, recursively perform steps 1-3 on the new arrays.

Essentially, a quicksort involves breaking the array into smaller and smaller pieces, and then sorting each of these smaller pieces until you work your way up to a complete sorted array.

Which element should you use as the pivot in order to perform quicksort the fastest? It depends. If you choose the first element of the array as the pivot, and the array is sorted in reverse order, you’re in the worst-case scenario, because every single element will go into an array to the left of the pivot, and you’ll have to perform the recursive function n times, where n is the number of elements in the array. In this worst-case scenario, checking n elements n times gives a runtime of n * n, or O(n2) – very slow.

It turns out the best way to even out the extremes is to pick a random pivot. This gives you an average-case runtime of O(n log n). Why? Because you’re checking each element of the array, but in each round on average, you’re cutting the length of the left and right arrays in half. If the array has 8 elements, it will take 3 rounds to get down to sub-arrays of 1 element each: starting from 8, you go to 4, then 2, then 1. That’s log2 8, or log n. So you’re checking n element of the array and you’re doing it log n times, or n * log n, for a runtime of O(n log n).

I decided to try implementing quicksort via Ruby. Here’s my program:

def quicksort(array)
  return array if array.length < 2
  pivot = array.delete_at(rand(array.length))
  left_array = []
  right_array = []
  array.each do |item|
    if item < pivot
      left_array << item
    else
      right_array << item
    end
  end
  return quicksort(left_array) + [pivot] + quicksort(right_array)
end

That's quicksort.

Binary Search in Ruby

I just started reading Grokking Algorithms, by Aditya Bhargava, which has really user-friendly explanations of common programming algorithms.

One basic algorithm every programmer should know is binary search. Binary search is the most efficient way to search through an array of sorted data to find what you’re looking for. (It’s crucial that the data be sorted first.) Here are the steps:

(1) Compare the item you’re looking for to the median value of the array. If your item is the median, congrats, you’ve found it! Otherwise:

(2) If your item is higher than the median, chop off the lower half of the array (since it won’t be in there). If it’s lower, chop off the upper half.

(3) Go back to step 1, comparing the item with the median of the new, smaller array.

The nice thing about binary search is that its runtime is O(log n), i.e. logarithmic. If your array has 128 items, it will take at most 7 steps to find your item; double the array to 256 items, and you need only add one more step.

I decided to implement binary search in Ruby. My program accounts for the possibility that your item is not in the data. Here’s my program, assuming the data is already sorted:

def in_list?(item, array)
  median = array[array.length/2]
  if item == median
    return true
  elsif array.length == 1
    return false
  elsif item < median
    array = array[0...array.length/2]
    in_list?(item, array)
  elsif item > median
    array = array[array.length/2..-1]
    in_list?(item, array)
  end
end

If the array is not already sorted, it’s a little longer:

def in_list?(item, array)
  check(item, array.sort)
end

def check(item, array)
  median = array[array.length/2]
  if item == median
    return true
  elsif array.length == 1
    return false
  elsif item < median
    array = array[0...array.length/2]
    check(item, array)
  elsif item > median
    array = array[array.length/2..-1]
    check(item, array)
  end
end

That’s binary search.

How to Implement Counting Sort in Ruby

There are various ways to sort data in computer programming: bubble sort, quick sort, merge sort. Another method, which I recently learned about, is counting sort. This method is useful when the data you’re sorting has a relatively small range of values between the minimum and maximum – for instance, if you’re sorting individual letters or individual digits. There are only 26 digits – not a very large range. For large data sets of this type, counting sort can be faster than merge sort.

Here’s a visualization of counting sort. Here are the steps, which are kind of hard to understand without the visualization:

(1) Create an empty array of n elements, where n is the range of possible values. If we’re sorting letters, we create an empty array with a length of 26 (lowest index is 0, highest index is 25).

(2) Into each space in the empty array, put the total number of that element that exists in the original unsorted list. For instance, suppose the original unsorted list contains 3 g‘s. Since g is the 7th letter of the alphabet, the seventh index of the array – array[6] – should be assigned the value 3.

(3) Take this newly-populated array. Starting from the beginning, add the value of each index to the value of the index after it. If you do this correctly, the last index of the array will contain the number of all elements in the unsorted list. (This is easier to understand if you look at the visualization linked above.)

(4) Finally, create another empty array the same length as the number of elements in the original unsorted list. Then, for each value in the original unsorted list, find the element in the array that has that index value. Confusing? In other words, if a value in the original unsorted list is the letter g, go to array[6].

Then reduce that value by 1. Next, whatever value array[6] holds, go to the new array at new_array[that_value]. For instance, if array[6] contains 4, reduce it to 3, then go to new_array[3].

Now, assign new_array[3] the value 6.

Do that for every element in the original unsorted list, and you will now have an array containing all the elements, sorted.

Here’s how I implemented counting sort in Ruby, where init_string is the original unsorted data. I created a key array to use to convert letters to their numerical equivalents.

key = "abcdefghijklmnopqrstuvwxyz".split("")

init_string = "zyxwvutdcba"

init_array = init_string.split("")

mid_array = Array.new(26, 0)   #[0,0,0,0,0,0...]
final_array = Array.new(init_array.length, 0)   #[0,0,0,0,0,0...]

# put each character in the array at its proper index
init_array.each do |letter|
  i = key.index(letter)
  mid_array[i] += 1
end

# increment each value in the array by the sum of the number before it
mid_array.each_with_index do |value, index|
  mid_array[index] = mid_array[index-1] + mid_array[index] if index > 0
end

# for each value in init_array:
init_array.each do |value|
  # take the value (init_array[i])
  i = key.index(value)
  # find the value in mid_array that has the index of that first value; decrement that value in mid_array by 1
  mid_array[i] -= 1
  final_index = mid_array[i]
  # go to final_array with the index of that new decremented value; put the initial value there
  final_array[final_index] = value
end

final_array = final_array.join

print final_array