Popular Sorting Algorithms in Ruby

Bubble Sort:

    1 def bubble_sort(list)
    2   sl = list.clone
    3   sl.each_index do |i|
    4     ( sl.length - i - 1 ).times do |j|
    5         if ( sl[j+1] < sl[j] )
    6             sl[j], sl[j+1] = sl[j+1], sl[j]
    7         end
    8     end
    9   end
   10 end
   11
   12 list = [1, 3, 6, 7, 8, 11, 43, 2, 4, 5]
   13 p list
   14 p bubble_sort(list)
   15 

Take the first element , compare it to the second element, if the
second is smaller, swap the elements, repeat until you hit the end of
the list. start again , this time repeat till you get to the end of
the list - 1. repeat n times.

Selection Sort:

    1 def selection_sort (list)
    2   sl = list.clone
    3   sl.each_index do |i|
    4     min = i
    5     (i..(sl.size-1)).each do |j|
    6          min = j  if sl[j] < sl[min]
    7      end
    8      sl[i], sl[min] = sl[min], sl[i]
    9   end
   10 end
   11
   12 list = [1, 3, 6, 7, 8, 11, 43, 2, 4, 5]
   13 p list
   14 p selection_sort(list)
   15 

Same as Bubble Sort except that you only swap one element at each pass


Insertion Sort: (in place)

    1 def insertion_sort(list)
    2   sl = list.clone
    3   sl.each_index do |i|
    4     j = i
    5     while j > 0 && sl[j] < sl[j-1]
    6       sl[j], sl[j-1]= sl[j-1], sl[j]
    7       j -=1
    8     end
    9   end
   10 end
   11
   12 list = [1, 3, 6, 7, 8, 11, 43, 2, 4, 5]
   13 p list
   14 p insertion_sort(list)
   15 

Split the list to be sorted into two lists, sorted and unsorted. Start with a sorted list of 1 element and work up until n inserting each new element into its correct place in the sub list. Easily improvable running time.


Merge Sort:

    1 def merge_sort(ls)
    2   return ls if ls.size <= 1
    3   left = ls[0, ls.length/2]
    4   right = ls[ls.length/2, ls.length]
    5   merge(merge_sort(left), merge_sort(right))
    6 end
    7 def merge(l, r)
    8   sl = []
    9   until l.empty? or r.empty?
   10     sl << (l[0] <= r[0] ? l.shift : r.shift)
   11   end
   12   sl.concat(l).concat(r)
   13 end
   14
   15 list = [1, 3, 6, 7, 8, 11, 43, 2, 4, 5]
   16 p list
   17 p merge_sort(list) 

First reasonable running time. Take the list and split it in half. Take each half and split those in half until you have done so lg(n) times.
Merge the bottom row of elements which are at this point 1 element each. O(1) * n/2
Merge the higher up elements which are at this point 2 sorted elements each. O(3) *n/4
Merge the higher up elements which are at this point 4 sorted elements each. O(7) *n/8
Do so until you reach the n/2 sorted list

lgN steps max N comparisons at each step.


Heap Sort:

    1 def heap_sort (list)
    2   sl = []
    3   heap = build_heap(list)
    4   heap.size.times do
    5     sl << heap.shift
    6     heap = heapify(heap, 0)
    7   end
    8   sl.reverse
    9 end
   10 def left(i); ((i+1)*2)-1; end
   11 def right(i); (i+1)*2; end
   12 def heapify(h, root)
   13   max = root
   14   l, r = left(root), right(root)
   15   if ( l < h.size && h[l] > h[max])
   16     max = l
   17   end
   18   if ( r < h.size && h[r] > h[max])
   19     max = r
   20   end
   21   if( root != max)
   22       h[root], h[max] = h[max], h[root]
   23     return heapify(h, max)
   24   else
   25     return h
   26   end
   27 end
   28 def build_heap(list)
   29   heap = list.clone
   30   (((heap.size)-1)/2).downto(0) do |e|
   31     heap = heapify(heap, e)
   32   end
   33   heap
   34 end
   35
   36 list = [1, 3, 6, 7, 8, 11, 43, 2, 4, 5]
   37 p list
   38 p heap_sort(list)
   39

Heap sort relies on the fact that a heap structure will have a constant speed get max. and a lgn heapify method. as well as an nlogn build heap method.

First step build a binary heap. where every parent is bigger than its (2 for binary heap) children. So you pull the first object off of a list.


QuickSort:

    1 def quick_sort(list)
    2   sl = list.clone
    3   return sl if sl.size <= 1
    4   pivot = sl.pop
    5   left, right = sl.partition { |e| e < pivot }
    6   quick_sort(left) + [pivot] + quick_sort(right)
    7 end
    8
    9 list = [1, 3, 6, 7, 8, 11, 43, 2, 4, 5]
   10 p list
   11 p quick_sort(list)
   12

Very similar to Merge only that this time you randomly pick a pivot point, then divide the resulting list to be sorted into two sublists. One containing numbers smaller than your pivot and the other containing the numbers larger than your pivot. You recursively call this method on the sublists and return when the sublist is of size 0 or 1.(or even two if you want to speed it up a bit.)


Counting Sort:

Equivalent to bucket sort with size 1 bucket ranges.

    1 def counting_sort(list, max)
    2   counts = Array.new(max+1, 0)
    3   list.each do |i| 
    4     counts[i] += 1
    5   end
    6   sorted = []
    7   counts.each_index do |index| 
    8     counts[index].times { sorted << index } 
    9   end
   10   sorted
   11 end
   12 
   13 list = [1, 3, 6, 7, 8, 11, 43, 2, 4, 5]
   14 p list
   15 p counting_sort(list, 43)