Wednesday, October 8, 2008

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)

3 comments: