Sorting

One of the most common algorithm tasks when developing an application is sorting. Here I’ll go over MergeSort and QuickSort in Ruby in more detail.

MergeSort — class MergeSortAlgorithm # Break’s the array down into two numbers (number A and number B) and sorts them. def sort(numbers) if numbers.size <= 1 return numbers end array_size = numbers.size half_of_size = (array_size / 2).round left_array = numbers.take(half_of_size) right_array = numbers.drop(half_of_size) sorted_left_array = sort(left_array) sorted_right_array = sort(right_array) merge(sorted_left_array, sorted_right_array) end # This then creates a new array, loops through the left/right arrays and places the lowest number into the array. def merge(left_array, right_array) if right_array.empty? return left_array # We have nothing to compare. Left wins. end if left_array.empty? return right_array # We have nothing to compare. Right wins. end smallest_number = if left_array.first <= right_array.first left_array.shift else right_array.shift end # We keep doing it until the left or right array is empty. recursive = merge(left_array, right_array) # Okay, either left or right array are empty at this point. So we have a result. [smallest_number].concat(recursive) endend # Let’s give this a spin?merge_sort = MergeSortAlgorithm.newputs merge_sort.sort([4, 92, 1, 39, 19, 93, 49, 10].shuffle) # => [1, 4, 10, 19, 39, 49, 92, 93] # How it works# 1. Let’s say the input is [4, 92, 1, 39, 19, 93, 49, 10]# 2. Break them down in halfs. So we now have [4, 92, 1, 39] and [19, 93, 49, 10]# 3. Break them again in halfs. Let’s start with the first. So now we have [4, 92] and [1, 39]# 4. Break until there’s only one item in each. So now we have [4] and [92]# 5. Check which one is lower. So in this case, we know 4 is lower than 92. Let’s rearrange it if necessary.# 6. Now we have [4, 92] and we do the same for [1, 39]# 7. We now create a new array. []# 8. We check the first element on the left array versus the first element on the right array (i.e. 4 >= 9) and then add them to the new array.# 9. Keep doing that until it’s done.

QuickSort — def quicksort(array, from=0, to=nil) if to == nil # Sort the whole array, by default to = array.count — 1 end if from >= to # Done sorting return end # Take a pivot value, at the far left pivot = array[from] # Min and Max pointers min = from max = to # Current free slot free = min while min < max if free == min # Evaluate array[max] if array[max] <= pivot # Smaller than pivot, must move array[free] = array[max] min += 1 free = max else max -= 1 end elsif free == max # Evaluate array[min] if array[min] >= pivot # Bigger than pivot, must move array[free] = array[min] max -= 1 free = min else min += 1 end else raise “Inconsistent state” end end array[free] = pivot quicksort array, from, free — 1 quicksort array, free + 1, toend def mergesort(array) if array.count <= 1 # Array of length 1 or less is always sorted return array end # Apply “Divide & Conquer” strategy # 1. Divide mid = array.count / 2 part_a = mergesort array.slice(0, mid) part_b = mergesort array.slice(mid, array.count — mid) # 2. Conquer array = [] offset_a = 0 offset_b = 0 while offset_a < part_a.count && offset_b < part_b.count a = part_a[offset_a] b = part_b[offset_b] # Take the smallest of the two, and push it on our array if a <= b array << a offset_a += 1 else array << b offset_b += 1 end end # There is at least one element left in either part_a or part_b (not both) while offset_a < part_a.count array << part_a[offset_a] offset_a += 1 end while offset_b < part_b.count array << part_b[offset_b] offset_b += 1 end return arrayend # Search a sorted array in O(lg(n)) timedef binary_search(array, value, from=0, to=nil) if to == nil to = array.count — 1 end mid = (from + to) / 2 if value < array[mid] return binary_search array, value, from, mid — 1 elsif value > array[mid] return binary_search array, value, mid + 1, to else return mid endend a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15].shuffle# Quicksort operates inplace (i.e. in “a” itself)# There’s no need to reassignquicksort aputs “quicksort”puts a b = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15].shuffle# Mergesort operates in new array# So we need to reassignb = mergesort bputs “mergesort”puts b offset_3 = binary_search a, 3puts “3 is at offset #{offset_3} in a” offset_15 = binary_search b, 15puts “15 is at offset #{offset_15} in b”