Sorting

Probably the greatest source of grief for algorithmics students around the world is the propensity of teachers to talk about sorting. It just so happens that they're an easy introduction into the world of algorithms, so we'll do the same here.

There are surely hundreds of known sorting algorithms. This youtube video Links to an external site. shows some of the most famous ones.

Bubble sort

Iterate through the entire array N times, swapping disordered pairs.

Pseudocode:

bubble( array ):
   for each element in array:
      for each element i in array:
         if array[i] > array[i+1]: swap array[i] and array[i+1]

Insertion sort

Take each element of the array and insert it into the correct position in the already-sorted portion of the array.

Pseudocode:

insertion( array ):
   for j = 2 to length(array):          // for each element
      key = array[j]
      i = j - 1                         
      while i > 0 and array[i] > key:   // until proper place found
         array[i+1] = array[i]          // shift elements left
         i = i+1
      array[i+1] = key                  // insert the element

Quick sort

Somehow, choose a pivot element. Move all the elements less than the pivot to the left side and all other elements to the right. Quicksort the two resulting subarrays.

Pseudocode:

quickSort(arr, beg, end): 
   if (beg < end):
      pivotIndex = partition(arr, beg, end)   
      quickSort(arr, beg, pivotIndex) 
      quickSort(arr, pivotIndex + 1, end)
   
partition(arr, beg, end):
   pivot = arr[end]                   
   pIndex = beg - 1 
   for i = beg to end-1:
      if arr[i] < pivot:
         swap arr[i] and arr[pIndex] 
         pIndex++ 
      swap pivot and arr[pIndex+1] 
   return pIndex + 1

Heap sort

First, build a binary heap out of the array. The heap property guarantees that each node is greater than its children.

The first element, the root, is the largest element and is thus moved to the end of the array. The new first element is sifted down to correct the heap. This is repeated until the entire array is sorted.

Pseudocode:

iParent( i ):            // gives index of parent of i
iLeftChild( i ):         // returns index of left child of i
iRightChild( i ):        // returns index of right child of i

heapify( arr, count ):
   start = iParent( count  -1 )
   while start >= 0:
      siftDown( arr, start, count - 1 )
      start = start - 1 

siftDown( arr ):
   root = start
   while iLeftChild(root) <= end:
      child = iLeftChild(root)
      swapper = root
      if arr[swapper] < arr[child]:
         swapper = child
      if child+1 <= end and arr[swap] < arr[child+1]:
         swapper = child+1
      if swapper = root: 
         return
      else:
         swap(arr[root], arr[swapper])
         root = swapper

Exercise

Pick one of the sorting algorithms and determine its complexity. Links to an external site.