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
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;
}
| Complexity | Adaptive | Stable | In-place | ||
|---|---|---|---|---|---|
| Shell | O(n^(3/2)) for these h values | Yes (it is based on insertion sort) | No (except for small n where starting h is 1) | Yes | |
| Merge Sort | O(nlogn) | No | Yes | No | |
| Quick sort | O(n^2) | No | No | No - in terms of stack space for recursion |
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.
void medianOfThreePivot(int items[], int low, int high){
// Swap median (value mid-way between low and high) with items[high - 1]
exch(items[(low+high)/2],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]
if(less(items[high-1],items[low])){
exch(items[high-1], items[low]);
}
if(less(items[high],items[low]){
exch(items[high],items[low]);
}
if(less(items[high],items[high-1]){
exch(items[high],items[high-1]);
}
}
We would rearrange the array 1 2 3 4 9 6 7 8 5 10 then call partition from 1 8 with pivot 5 After 2 3 4 5 6 7 8 9 We would then call quicksort again on 1 2 3 4 and 6 7 8 9 10 Thus the pivot has split the data in half (good for efficiency). Normal quicksort would use the 10 as the pivot resulting in everything being on the left of the pivot. (bad for efficiency) So the next call to quicksort would be for the data 1 2 3 4 5 6 7 8 9
Sorting Linked Lists
Given the following definition of a linked list
typedef struct node * link;
struct node{
Item item;
link next;
};
link merge(link list1, link list2){
link merged = NULL;
link mergedEnd = NULL;
while(list1 != NULL && list2 != NULL){
if(list1->item <= list2->item){
//Move the element from list1 to the merged list
if(merged == NULL){
merged = list1;
mergedEnd = list1;
}else{
mergedEnd->next = list1;
mergedEnd = list1;
}
list1 = list1->next;
}else{
//Move the element from list1 to the merged list
if(merged == NULL){
merged = list2;
mergedEnd = list2;
}else{
mergedEnd->next = list2;
mergedEnd = list2;
}
list2 = list2->next;
}
}
//One of the lists is empty
if(list1 == NULL){
mergedEnd->next = list2;
}else{
mergedEnd->next = list1;
}
return merged;
}
link mergeSort(link list){
link p1, p2;
link list1, list2;
if(list == NULL){
return NULL;
}
if(list->next == NULL){
return list;
}
p1 = list;
p2 = list->next;
while(p2 != NULL && p2->next != NULL){
p1 = p1->next;
p2 = p2->next->next;
}
p2 = p1->next;
p1->next = NULL;
list1 = mergeSort(list);
list2 = mergeSort(p2);
return merge(list1,list2);
}
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; }
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.
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.
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.
If swap() were implemented as the above function, it would not work. Parameters are pased by value in C, and parameters can be viewed as local variables that have their values initialised at the time the function is called. With this perspective, it is hopefully clear that the swap() function will simply change the values of objects that are local to the function and all effects will be lost once the function exits.
The macro works because the swapping statements are inserted into any function that uses the macro and so the effects take place within the environment of that function, rather than within the local environment of an invoked function.
The macro definition could be used effectively to exchange the values stored in two list nodes, e.g.
Link curr, next;
...
swap(curr->value, next->value);
... which, after macro expansion, would become ...
{ Item tmp; tmp = curr->value; curr->value = next->value; next->value = tmp; }
A function to modify variables from the calling function would need to use pointers to the objects in the calling function. The following definition would be suitable:
void swap(Item *i1, Item *i2) {
Item tmp; tmp = *i1; *i1 = *i2; *i2 = tmp;
}
And you would use it as:
Item a[...]; ... swap(&a[i], &a[j]); List L; Link curr, next; ... swap(&(curr->value), &(next->value));