Tutorial Exercises Week 05

Exercise 1

Break into three groups.

One group should prepare a short demonstration of shell sort, one on top down merge sort and one on quicksort.

Try to demonstrate how the algorithms work and what their properties are.

Shellsort

void shellSort(int items[], int n) {
    int i, j, h;

    //Find starting h value
    for (h = 1; h <= (n - 1)/9; h = (3 * h) + 1);
    
    for (; h > 0; h /= 3) {
       //This inner loop is just like simple insertion sort when h is 1
       for (i = h; i < n; i++) {
            int key = items[i];
            for (j = i; j >= h && key <  items[j - h] ; j -=h) {
                items[j] = items[j - h];
            }
            items[j] = key;
        }
    }
   
}

Mergesort

void merge(int a[], int l, int mid, int r) ;
void mergesort (Item a[], int l, int r){   
    int m = (l+r)/2;  
    if  (r <= l) {    
        return;  
    }  
    mergesort (a, l, m);   
    mergesort (a, m+1, r);
    merge (a, l, m, r);
}


void merge(int a[], int l, int mid, int r) {
	int i, j, k, nitems = r-l+1; 
	int *tmp = malloc(nitems*sizeof(int)); 
	i = l; j = mid+1; k = 0; 
	while (i <= mid && j <= r) { 
		if ( a[i] < a[j] ) {
			tmp[k++] = a[i++]; 
		}else{ 
			tmp[k++] = a[j++]; 
       }
	}
	while (i <= mid) tmp[k++] = a[i++]; 
	while (j <= r) tmp[k++] = a[j++]; 

	//copy back 
	for (i = l, k = 0; i <= r; i++, k++) 
		a[i] = tmp[k]; 
	free(tmp); 
}

Quicksort

The following implementation for quicksort is taken from Sedgewick Algorithms in C:

typedef int Item;
#define key(A) (A)
#define less(A, B) (key(A) < key(B))
#define exch(A, B) { Item t = A; A = B; B = t; } 


int partition(Item a[], int l, int r);

void quicksort (Item a[], int l, int r) { 
  int i;

  if (r <= l) return;
  i = partition (a, l, r);
  quicksort (a, l, i-1);
  quicksort (a, i+1, r);
}

int partition (Item a[], int l, int r) { 
  int i = l-1, j = r; Item v = a[r];

  for (;;) { 
    while (less(a[++i], v)) ;
    while (less(v, a[--j])) if (j == l) break;
    if (i >= j) break;
    exch(a[i], a[j]);
  }
  exch(a[i], a[r]);
  return i;
}

Exercise 2

Quicksort with median of three partitioning

One improvement to the Quicksort algorithm that we discussed was the use of Median-of-Three partitioning. In this version of Quicksort, three items in the array are sampled and the median of the three values is used to partition the array. Without looking at the C code given in lectures, complete the following program by replacing the comments with the relevant C program statements.

// Quick sort with Median of Three Partitioning
void quicksortMT (Item a[], int l, int r) { 
  int i;

  if (r <= l) return;
  if(r-l > 1){
      medianOfThreePivot(a,l,r);   
      i = partition (a, l+1, r-1);
  } else {
      i = partition (a, l, r);
  }

  quicksortMT (a, l, i-1);
  quicksortMT (a, i+1, r);
}


void medianOfThreePivot(int items[], int low, int high){   
   // Swap median (value mid-way between low and high) with items[high - 1]
   // Compare items[low], items[high - 1] and items[high]
   // Rearrange values:
   //  lowest value to be stored in items[low]
   //  highest value to be stored in items[high]
   //  median value to be stored in items[high-1]
}

Trace the call of medianOfThreePivot and then partition on the sequence 1 2 3 4 5 6 7 8 9 10

Compare it to standard quicksort.

Exercise 3

Sorting Linked Lists

Given the following definition of a linked list
typedef struct node * link;
struct node{
    Item item;
    link next;
};

Exercise 4

Sorting algorithms generally require a swap operation which exchanges two values which are out of order. The swap() operation used in the textbook is implemented as a C macro:

#define swap(i1,i2)  { Item tmp; tmp = i1; i1 = i2; i2 = tmp; }
  1. Could this be re-implemented as a function like:

    void swap(Item i1, Item i2) {
    	Item tmp; tmp = i1; i1 = i2; i2 = tmp;
    }
    

    If so, how would you use it? If it would not be suitable, explain why not.

  2. Consider the implementation of swap() in the context of linked lists, where Lists are defined as:

    typedef struct Node *Link;
    typedef struct Node { Item value; Link next; } Node;
    typedef struct ListRep { int  nitems; Link first; } ListRep;
    typedef ListRep *List;
    

    Would the macro above be suitable? If so, how would you use it? If it would not be suitable, explain why not.

  3. Give a function to implement swap() that would work for both arrays and linked lists. Show examples of how your function would be used for each structure.