Often we need to sort data as part of our processing logic, and it is also a common interview question to construct a sort. There various methods to generate a sorted list of items. In this post I will take a look at sorting array data with Ruby. I will look at merge sort, quick sort and the bubble sort.

Merge Sort - This sort methods works by dividing the array into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. When the sorting and merging is completed you have the sorted array. A short example of a merge sort can be found here: https://gist.github.com/kimhunter/1284454 and is presented below.

def merge_sort(array)
  return array if array.size <= 1
  l, r = split_array(array)

  # Here we are going to recursively call merge_sort
  # until all elements are split out
  # Then merge them back in to one sorted array via #combine
  result = combine(merge_sort(l), merge_sort(r))
end

def split_array(array)
  # find the mid point of the array
  mid = (array.size / 2).round

  # return 2 arrays. One of the first half of the array,
  # and one of the second half
  [array.take(mid), array.drop(mid)]
end

def combine(a, b)
  # return either a if b is empty or b if a is empty
  return b.empty? ? a : b if a.empty? || b.empty?

  # Smallest is either the first element of a or b whichever is smaller
  # Then remove that element from the array it came from; either a or b
  smallest = a.first <= b.first ? a.shift : b.shift

  # Make a recursive call to combine with the remaining array elements
  # Prepend our smaller value to the front of the resulting array returned
  combine(a, b).unshift(smallest)
end

# Driver code
a = [6,23,53,1,2,5,62,61,33,21,14,6,23].shuffle
p a # => [61, 21, 23, 6, 33, 5, 53, 6, 62, 14, 23, 1, 2]
p merge_sort(a) # => [1, 2, 5, 6, 6, 14, 21, 23, 23, 33, 53, 61, 62]

Quick Sort - A quick sort is a sorting method that works by selecting a "pivot" element of the array and then roughly sorts the other elements relative to the pivot. The smaller value elements are placed before the pivot and the higher value elements are placed after the pivot. This process is repeated across the array recursively.

def quick_sort(array)
  return array if array.length <= 1

  pivot = array.sample # pick a random element for the pivot
  array.delete_at(array.index(pivot)) # remove the pivot
  #puts "Picked pivot of: #{pivot}"
  lesser = []
  greater = []

  # divide the array into lesser than pivot and a greater than pivot arrays
  array.each do |x|
    if x <= pivot
      lesser << x
    else
      greater << x
    end
  end

  # build our sorted array
  sorted_array = []
  # recursively sort the lesser array values
  sorted_array << quick_sort(lesser)
  sorted_array << pivot # add our pivot value
  # reccursively sort our greater array
  sorted_array << quick_sort(greater)
  # flatten out our resulting array and return this
  sorted_array.flatten!
end

# Driver code
a = [6,23,53,1,2,5,62,61,33,21,14,6,23].shuffle
p a # => [61, 21, 23, 6, 33, 5, 53, 6, 62, 14, 23, 1, 2]
p quick_sort(a) # => [1, 2, 5, 6, 6, 14, 21, 23, 23, 33, 53, 61, 62]

Bubble Sort - A bubble sort is a simple method that works by repeatedly stepping through the array, comparing each pair of adjacent items and swapping them if they are in the wrong order. The sorting passes through the array are repeated until no further swaps are needed. For a large set of data, it is easy to see that this method could take a long time to process.

def bubble_sort(array)
  return array if array.size <= 1

  swapped = true # this flag indicates we did a swap, and we need to loop again

  while swapped do
    # set the flag to false so we can break out of this loop if there was no swap
    swapped = false

    # loop trough the array from first element to the next to last element
    0.upto(array.size-2) do |i|
      # if the value is greater than the next value, swap them
      if array[i] > array[i+1]
        array[i], array[i+1] = array[i+1], array[i]
        swapped = true # set the flag since we swapped
      end
    end
  end

  # return back the sorted array
  array
end

# Driver code
a = [6,23,53,1,2,5,62,61,33,21,14,6,23].shuffle
p a # => [61, 21, 23, 6, 33, 5, 53, 6, 62, 14, 23, 1, 2]
p bubble_sort(a) # => [1, 2, 5, 6, 6, 14, 21, 23, 23, 33, 53, 61, 62]