Lecture 19

Towers of Hanoi Continued,
void transfer(int n, char start, char end, char work)  {
  if (n > 0)  {
    transfer(n-1, start, work, end);
    printf("Move disk from %c to %c\n",start, end);
    transfer(n-1, work, end, start);
  }
}
When called for three disks, the execution profile of transfer is: The function prints:


Another example: decimal to binary

Consider the problem of printing an unsigned integer in binary. In the very first lecture we did this by finding the largest power of two smaller than the number and printing 0's and 1' for all the powers of two present. We can use recursion to do this much more elegantly. The end case is when n=0.

Our first attempt might be:

but this will not work for n=0, we note that the end case should be when n=0 or n=1:
In this program we have replaced a 12 line iterative function by a 3 line recursive one.

Sorting

This is one of the simplest sorting algorithms - the bubble sort. An array is sorted by repeatedly passing through the array swapping adjacent elements that are not in order.

Quicksort

Quicksort sorts an array using a recursive technique.
int n[10]={53,12,98,63,18,72,80,46,32,21};
53
12
98
63
18
72
80
46
32
21
Consider the problem of sorting the array given above

We attempt to 'partition' the elements in the array with respect to the first element, 53 ( this element is usually referred to as the pivot). This means that we try to put 53 in such a position that all elements to its left are smaller and all elements to its right are larger. If this is done, then the 53 must be in its final position in the sorted array. For example, one method of partitioning might produce:

21
12
32
46
18
53
80
72
63
98
If we sort the portions to the left and right of 53, we will have sorted the entire array. Sorting the original array has been reduced to sorting two smaller arrays. To sort n[0] to n[4], we can partition this portion with respect to the first element, 21. This puts 21 in its final sorted position, leaving us to sort two smaller arrays. This is illustrated by:
 
18
12
21
46
32
53
80
72
63
98
The portions which remain to be sorted are: The process is continued until all the little pieces have been sorted.

This sort is easily written as a recursive function.

void quicksort(int n[], int left,int right) {
  int dp;
  if (left<right)  {
    dp=partition(n,left,right);
    quicksort(n,left,dp-1);
    quicksort(n,dp+1,right);
  }
}
The function quicksort, when given two values left and right, sorts an array from elements left to right inclusive. It calls the function 'partition' to partition the elements with respect to some pivot. 'partition' returns the new position of the pivot (called the division point -dp). Now we need to write the partition function.

Assume the first element (n[left] is the pivot)

  1. Assign pivot to the first element.
  2. Scan from the right for an element that is smaller than pivot.
  3. Scan from the left for an element that is larger than the pivot.
  4. Swap these two elements.
  5. repeat until the scans meet.
  6. swap element at division point and n[left]
Consider the array n from earlier;
 
53
12
98
63
18
72
80
46
32
21
After this partition the array looks like this:
 
46
12
21
32
18
53
80
72
63
98
The following function implements the above algorithm.
int partition(int n[],int left,int right)  {
  int lo,hi,pivot,t;
  pivot=n[left];
  lo=left-1;
  hi=right+1;
  while(lo+1!=hi)  {
    if(n[lo+1]<=pivot)
      lo++;
    else if(n[hi-1]>pivot)
      hi--;
    else {
      t=n[lo+1];
      n[++lo]=n[hi-1];
      n[--hi]=t;
    }
  }
  n[left]=n[lo];
  n[lo]=pivot;
  return lo;
}
Here is a program to test the bubblesort and quicksort.

If you have a browser with Java - here
is a graphical comparison of four sorting algorithms.