Rewbie Newbie

Documenting my path on becoming a Rails Developer.

Sorting Algorithms

Being able to code in an awesome language such as Ruby does not excuse one from not knowing how to reconstruct something that is already built into the language, case in point is the sort method in class Array. I will use this blog post to analyze the numerous sort algorithms and discuss why quicksort is the sort algorithm used in the Array#sort method.

Before I dig into each specific sorting algorithm, I want to lay down some ground-rules and prevent any ambiguities or confusion. Each algorithm will sort an unordered array from the smallest value to the largest value ordered from left to right.

Bubblesort

Bubblesort is a simple search algorithm where an array is sorted by comparing adjacent pairs of elements and swapping the element positions if the left element is greater than the right element. Each step-through of the array will always yield the correct position for the next largest value in the array, thus the next largest value is ‘bubbled’ to the right. This can be illustrated with a simple example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Bubblesort from least to greatest

starting array
=> [3,2,4,1]

1. compare the 3 and 2, since 3 is greater than 2, swap positions.
=> [2,3,4,1]

2. compare the 3 and 4, they are in the correct position, move to next pair.

3. compare the 1 and 4, 1 is less than 4, swap positions. 4 is in the correct position since it is the largest, so it will not be compared with another number again.
=> [2,3,1,4]

4. compare 2 and 3, they are in the correct postion, move to next pair.

5. compare 3 and 1, swap positions. 3 is in its correct position, it will not be compared again.
=> [2,1,3,4]

6. compare 2 and 1, swap positions. 2 is in its correct position, it will not be compared again. Sorting is complete.
=> [1,2,3,4]

Below is the bubblesort algorithm implemented in Ruby.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def bubble_sort(array)
  size = array.size
  if size == 1
    return array
  end
  size.downto(2).each do |step|
    (0...step-1).each do |p|
      if array[p] > array[p+1]
        array[p], array[p+1] = array[p+1], array[p]
      end
    end
  end
end

test = [60,37,3,21,3,2,5,6,33,44,55,7,3,4,2]

bubble_sort(test)

puts test
#=> [2, 2, 3, 3, 3, 4, 5, 6, 7, 21, 33, 37, 44, 55, 60]

Since there are n-1 + n-2 + … 2 + 1 comparisons made to execute bubblesort, the total comparisons made is (n-1)(n)/2 => (n2)/2 - n/2 and since n2 dominates as the dataset becomes large, bubblesort has an efficiency of Ο(n2).

Selection Sort

Selection sort sorts an array by repeatedly stepping through an array, keeping track of the successive smallest value’s position and swapping it with the starting position of each sweep.

1
2
3
4
5
6
7
8
9
10
11
12
Selection Sort from smallest to largest.

starting array
=> [3,2,4,1]

1. starting at 3, go through the array and keep track of the position of the smallest value. Since 1 is the smallest value, 3 and 1 swap places.
=> [1,2,4,3]

2. Starting at 2, go through the remaining array to its right and keep track of the successive smallest value. Since 2 is the next smallest value, no swap is needed.

3. Starting at 4 and going right, 3 and 4 are swapped and the array is sorted.
=> [1,2,3,4]

Below is the selection sort algorithm implemented in ruby.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
selection sort from smallest to largest

def selection_sort(array)
  size = array.size
  (0...size-1).each do |once|
    smallest = array[once]
    spot = once
    (once...size).each do |repeat|
      if array[repeat] < smallest
        smallest = array[repeat]
        spot = repeat
      end
    end
    array[spot], array[once] = array[once], array[spot]
  end
end

test = [44,2,5,2,7,11,87,99,66]

selection_sort(test)

puts test
#=> [2, 2, 5, 7, 11, 44, 66, 87, 99]

Selection sort also has an efficiency of Ο(n2).

Insertion Sort

Insertion sort is a search algorithm where a new number is introduced to an already sorted array and the new number is inserted into the correct position in the sequence. An example follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
unsorted array
=> [4,2,3,1]

1. Start with 4 as the only element in the sorted array.
=> [4]

2. Compare 2 with the 4, since 2 is less than 4 and there is no other number infront of 4, insert 2 in the position of 4.
=> [2,4]

3. Compare 3 with 4, since it is less than 4, compare 3 to the next number after 4, since 3 is greater than 2, insert 3 after 2.
=> [2,3,4]

4. Compare 1 with 4, 3, and 2, since it is smaller than all of them, it is inserted into the position of 1.
=> [1,2,3,4]

Below is the insertion sort algorithm implemented in ruby.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def insertion_sort(array)
  size = array.size
  (1...size).each do |once|
    (0..once).each do |repeat|
      if array[once] < array[repeat]
        array.insert(repeat, array[once])
        array.delete_at(once+1)
        break
      end
    end
  end
end

test = [5,2,3,7,9,2,4,5,2,0,1]

insertion_sort(test)

puts test
#=> [0, 1, 2, 2, 2, 3, 4, 5, 5, 7, 9]

Since the worst case scenario is that the array to be sorted is arranged from largest to smallest, it would take (n-1)(n)/2 steps, so insertion sort also has an efficiency of Ο(n2).

Merge Sort

Merge sort is a divide-and-conquer search algorithm where the array is broken down into smaller and smaller arrays until each number is the only element in its own array. Then each array is merged with adjacent array and this process is repeated until one long sorted array is formed.

1
2
3
4
5
6
7
8
9
10
11
unsorted array
=> [4,2,3,1]

1. Divide until each number is contained in its own array.
=> [4], [2], [3], [1]

2. Compare with adjacent array and merge.
=> [2,4], [1,3]

3. Compare each term of the merged arrays and merge again. Since 1 is less than 2, 1 is merged into the new array first. Then, comparing 2 and 3, 2 is merged and so on.
=> [1,2,3,4]

Below is the insertion sort algorithm implemented in ruby.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def merge(left, right)
  result = []
  while left.size > 0 || right.size > 0
    if left.size > 0 && right.size > 0
      if left.first <= right.first
        result << left.shift
      else
        result << right.shift
      end
    elsif left.size > 0
      result << left.shift
    elsif right.size > 0
      result << right.shift
    end
  end
  result
end

def merge_sort(array)
  if array.size <= 1
    return array
  end
  middle = array.size/2
  left = array[0..middle-1]
  right = array[middle..-1]
  left = merge_sort(left)
  right = merge_sort(right)
  return merge(left,right)
end

test = [33,77,23,34,49,1,2,5,2,3,7]

result = merge_sort(test)

puts result
#=> [1, 2, 2, 3, 5, 7, 23, 33, 34, 49, 77]

Merge Sort has an efficiency of Ο(n log n).

(More algorithms to come.)