Tutorial Week 07

Exercise 1

  1. Explain what stability means in the context of sorting
  2. Suppose you have an implementation of a sorting algorithm that sorts strings and is case insensitive (for example 'a' and 'A' are considered to be equal). Explain what is wrong with the following argument:

    I ran the following input through the program 

    AAAAA
zzzzz
abcde
aaaaa
    and the output of the program was 
    AAAAA
aaaaa
abcde
zzzzz
    This means my sorting program is stable

Exercise 2

Naive Bubble Sort 

1 void bubbleSort(int items[], int n) {
2    int i, j;
3        
4    for(i = n - 1; i > 0 ; i--) {
5        for(j = 1; j <= i; j++) {
6            if (items[j] <  items[j - 1]) {
7                swap(j,j-1,items);
8            }
9        }
10    }
11}
Random order: 3,2,4,8,1
Sorted order: 1,2,3,4,5
Reverse order: 5,4,3,2,1
  1. Show how each of these arrays above change as they are sorted by the program above.
  2. How many swaps are performed on the random, sorted, reverse ordered data sets shown above
  3. How many comparisons are peformed on the random, sorted and reverse ordered data sets shown above. By comparison we mean comparing two data elements from the array - we are not including the loop counter comparisons.
  4. With each line of code associate a cost and a formula expressing the number of times the C statement on that line will be executed when sorting n items in the worst case.
  5. What is the asymptotic worst case time complexity of the algorithm implemented by this program.
  6. What is the time complexity of the algorithm in the best case?
  7. Modify the program to implement bubble sort with early exit. What is the asymptotic worst case time complexity now? What is the time complexity now in the best case?

Exercise 3

Sorting Linked Lists

Implement selection sort, given the following definition of a linked list 

typedef struct node * link;
struct node{
    Item item;
    link next;
};

Exercise 4

Quick Sort

The following is the implementation of quicksort and the partition function as discussed in the lectures. 

   
   void quickSort (int 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 (int a[], int l, int r) {   
   int i = l-1;
   int j = r;   
   int pivot = a[r]; //rightmost is pivot  	
   for(;;) {   
	while ( a[++i] < pivot) ;    
	while ( pivot <  a[--j] && j != l);
	if (i >= j) { 
      		break;
    	}    
	swap(i,j,a);  
    }
    //put pivot into place  
    swap(i,r,a);  
    return i; //Index of the pivot
}

Trace the execution of the partition function on sorting the following input sequence of numbers: 4 7 1 1 4 6 7 2 5 6.

Trace the execution of the partition function on the following sequence of numbers: 1 2 3 4 5 6 7 8 9 10

Note that this sequence results in 10 being chosen as the pivot. This is one of the worst case scenarios for a pivot as it is larger than all the elements in the sequence.

Exercise 5

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. Given the code below, trace the call of medianOfThreePivot and then partition on the sequence 1 2 3 4 5 6 7 8 9 10

// 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 l and r) with a[r - 1]
       // Compare a[l], a[r - 1] and a[r]
       // Rearrange values:
       // lowest value to be stored in a[l]   
       // highest value to be stored in a[r]
       // median value to be stored in a[r-1]
       //  You are required to provide an implementation for this in lab 07 
}

int partition (int a[], int l, int r) {   
   int i = l-1;
   int j = r;   
   int pivot = a[r]; //rightmost is pivot  	
   for(;;) {   
	while ( a[++i] < pivot) ;    
	while ( pivot <  a[--j] && j != l);
	if (i >= j) { 
      		break;
    	}    
	swap(i,j,a);  
    }
    //put pivot into place  
    swap(i,r,a);  
    return i; //Index of the pivot
}

void swap(int index1, int index2, int items[]){
    int tmp;
    tmp = items[index1];
    items[index1] = items[index2];
    items[index2] = tmp;
}

Exercise 6

Mergesort

Among the good points of Mergesort:

Bad points of Mergesort: