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:

transfer(3,'A','B','C');
  transfer(2,'A','C','B');
    transfer(1,'A','B','C');
      Move disk from A to B
    Move disk from A to C
    transfer(1,'B','C','A');
      Move disk from B to C
  Move disk A to B
  transfer(2,'C','B','A');
    transfer(1,'C','A','B');
      Move disk from C to A
    Move disk from C to B
    transfer(1,'A','B','C');
      Move disk from A to B

The function prints:

Move disk from A to B
Move disk from A to C
Move disk from B to C
Move disk from A to B
Move disk from C to A
Move disk from C to B
Move disk from A to B

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.

To print n in binary, print n/2 in binary and then print n%2 (the remainder when n is divided by 2). The end case is when n=0.

Our first attempt might be:

void binary(int n)  {
  if (n > 0) {
    binary(n/2);
    printf("%d",n%2);
  }
}

but this will not work for n=0, we note that the end case should be when n=0 or n=1:

void binary(unsigned int n)  {
  if (n > 1) 
    binary(n/2);
  printf("%d",n%2); 
}

#include <stdio.h>  

void binary(int n)  {
  if (n > 1) 
    binary(n/2);
  printf("%d",n%2);  
}

void main() { 
   int i;        

   for(i=0;i<1000;i++) { // Print all binary numbers
      printf("\n %d = ",i);
      binary(i);         // from 0 to 999
   }        
}

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.

void bubble(int n[],int no) {
  int i,j,t;
  for(i=0;i<no;i++)
    for(j=0;j<no-i-1;j++)
      if(n[j]>n[j+1])  {
        t=n[j];
        n[j]=n[j+1];
        n[j+1]=t;
      }
}

Quicksort

Quicksort sorts an array using a recursive technique.

int n[10]={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:

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:

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)

Assign pivot to the first element.
Scan from the right for an element that is smaller than pivot.
Scan from the left for an element that is larger than the pivot.
Swap these two elements.
repeat until the scans meet.
swap element at division point and n[left]

Consider the array n from earlier;

pivot=53.
scan from right for value less than or equal to 53 - 21 is found.
scan from left for a value greater than 53 - 98.
next, 21 is moved to location 2 and 98 to location 9
scanning finds 32 and 63
32 is moved to location 3 and 63 to location 8
scanning finds 46 and 72
46 is moved to location 5 and 72 to location 7
no move moves are possible and so the pivot (53) is swapped with location 5.

After this partition the array looks like this:

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.

#include <stdio.h> 

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;
}

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);
  }
}

void bubble(int n[],int no) {
  int i,j,t;
  for(i=0;i<no;i++)
    for(j=0;j<no-i-1;j++)
      if(n[j]>n[j+1])  {
        t=n[j];
        n[j]=n[j+1];
        n[j+1]=t;
      }
}

void print(int n[],int no) {
int i;
  printf("[");
  for(i=0;i<no;i++) {
     if(i) printf(",");
     printf("%d",n[i]);
  }
  printf("]\n");
}

void main() { 
   
int n[10]={53,12,98,63,18,72,80,46,32,21};        
int n1[10]={53,12,98,63,18,72,80,46,32,21};        

   print(n,10);
   bubble(n,10);  
   print(n,10);
   quicksort(n1,0,9);
   print(n1,10);
}

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