Week 03 Tutorial Answers

Sorting

Resources

Questions

  1. Consider the following simple table of enrolments, sorted by course code:

    coursenameprogram
    COMP1927Jane3970
    COMP1927John3978
    COMP1927Pete3978
    MATH1231John3978
    MATH1231Adam3970
    PSYC1011Adam3970
    PSYC1011Jane3970

    Now we wish to sort it by student name, so that we can easily see what courses each student is studying. Show an example of what the final array would look like if

    1. we used a stable sorting algorithm
    2. we used an unstable sorting algorithm

    Answer:

    After a stable sort, the relative positions of items with equal sort keys is the same. In the context of this problem, this means that the subjects for a given student should be in the same order as in the original table (which happens to be sorted on subject):

    coursenameprogram
    MATH1231Adam3970
    PSYC1011Adam3970
    COMP1927Jane3970
    PSYC1011Jane3970
    COMP1927John3978
    MATH1231John3978
    COMP1927Pete3978

    An unstable sorting algorithm could produce any order that is sorted on the sort key (in this case name), including the order that is produced by the sorting stable algorithm. For example:

    coursenameprogram
    PSYC1011Adam3970
    MATH1231Adam3970
    PSYC1011Jane3970
    COMP1927Jane3970
    MATH1231John3978
    COMP1927John3978
    COMP1927Pete3978

    The result will definitely be sorted by name, but not necessarily be sorted by course-code within each name.

  2. Compare the performance of bubble sort and insertion sort on the following types of input:

    • Sorted (e.g., \([1, 2, 3, \ldots, n]\))
    • Reverse-sorted (e.g., \([n, n - 1, n - 2, \ldots, 1]\))
    • Sorted, except the first and last numbers are swapped (e.g., \([n, 2, 3, \ldots, n - 1, 1]\))

    Answer:

    • Sorted (e.g., \([1, 2, 3, \ldots, n]\))

      Bubble sort will make one pass through the array and then stop, as no swaps were performed. Thus, bubble sort takes \(O(n)\) time on sorted input.

      Insertion sort will perform only one comparison when inserting each item. For example, when inserting \(2\), it is compared with the item to its left (\(1\)), but since it is greater (as the array is sorted), this means the item does not need to be moved. Hence, insertion sort takes \(O(n)\) time on sorted input.

    • Reverse-sorted (e.g., \([n, n - 1, n - 2, \ldots, 1]\))

      Bubble sort will make \(n - 1\) passes through the array. The first pass swaps \(n\) all the way to the end of the array, requiring \(n - 1\) comparisons and swaps, the second pass swaps \(n - 1\) up next to \(n\), requiring \(n - 2\) comparisons and swaps, and so on. The total number of comparisons/swaps is \((n - 1) + (n - 2) + \ldots + 1 = \frac{1}{2}n(n - 1)\). Thus, bubble sort takes \(O(n^2)\) time on reverse-sorted input.

      Insertion sort will take \(1\) comparison to insert \(n - 1\), \(2\) comparisons to insert \(n - 2\) and so on, each time moving the element to the start of the array. The total number of comparisons is \(1 + 2 + \ldots + (n - 1) = \frac{1}{2}n(n - 1)\). So insertion sort takes \(O(n^2)\) time on reverse-sorted input.

    • Sorted, except the first and last numbers are swapped (e.g., \([n, 2, 3, \ldots, n - 1, 1]\))

      The first pass of bubble sort will swap \(n\) to the end of the array, so the array will look like \([2, 3, \ldots, n - 1, 1, n]\). Each subsequent pass will swap the \(1\) one space to the left, so it will take \(n - 2\) more passes to swap the \(1\) all the way to the start of the array. Thus, \(n - 1\) passes are performed in total, which means there will be \((n - 1) + (n - 2) + \ldots + 1 = \frac{1}{2}n(n - 1)\) comparisons performed in total. Thus, bubble sort takes \(O(n^2)\) time on this type of input.

      To insert \(2\), insertion sort performs one comparison (with \(n\)). After this, the state of the array is \([2, n, 3, 4, \ldots, n - 1, 1]\). To insert the numbers from \(3\) to \(n - 1\), two comparisons are performed (for example, to insert \(3\), it is compared with \(n\) and then with \(2\)). When inserting \(1\), it will be compared with all other elements to move it to the start, which is \(n - 1\) comparisons. This is about \(3n\) comparisons in total, so insertion sort takes \(O(n)\) time on this type of input.

  3. Merge sort is typically implemented as follows:

    void mergeSort(int A[], int lo, int hi) {
	if (lo >= hi) return;
	
	int mid = (lo + hi) / 2;
	mergeSort(A, lo, mid);
	mergeSort(A, mid + 1, hi);
	merge(A, lo, mid, hi);
}

void merge(int A[], int lo, int mid, int hi) {
	int nitems = hi - lo + 1;
	int *tmp = malloc(nitems * sizeof(int));
	
	int i = lo;
	int j = mid + 1;
	int k = 0;
	
	// scan both segments into tmp
	while (i <= mid && j <= hi) {
		if (A[i] <= A[j]) {
			tmp[k++] = A[i++];
		} else {
			tmp[k++] = A[j++];
		}
	}
	
	// copy items from unfinished segment
	while (i <= mid) tmp[k++] = A[i++];
	while (j <= hi)  tmp[k++] = A[j++];
	
	// copy items from tmp back to main array
	for (i = lo, k = 0; i <= hi; i++, k++) {
		A[i] = tmp[k];
	}
	free(tmp);
}

    Suppose that at a particular point during the execution of the mergeSort function, the array A looks like this:

    { 1, 4, 5, 6, 7, 2, 3, 4, 7, 9 }

    Show how the call merge(A, 0, 4, 9) would merge the elements of the two sorted subarrays into a single sorted array.

    Answer:

    At the beginning of the function, a temporary array is created to sort the elements (before they are copied back into the original array at the end).

    Then, three index variables are created: i is 0, which is the index into the beginning of the first sorted subarray, j is 5, which is the index into the beginning of the second sorted subarray, and k is 0, which is just an index into tmp so we know how many elements we have inserted into tmp so far (and where the next element should be inserted).

    A:   { 1, 4, 5, 6, 7, 2, 3, 4, 7, 9 }
       ^              ^
       i              j

tmp: {  ,  ,  ,  ,  ,  ,  ,  ,  ,   }
       ^
       k

    Now we enter the first loop, which does the majority of the merging. The loop compares the smallest elements of each subarray that haven't been consumed yet (i.e., A[i] and A[j]), and inserts the smaller of the two elements into tmp. If the two elements are the same, it takes the element from the first subarray - this ensures stability. It continues to do this until one of the subarrays has been exhausted.

    A[i] (1) is less than A[j] (2) - so copy A[i] into tmp and advance i and k

A:   { 1, 4, 5, 6, 7, 2, 3, 4, 7, 9 }
          ^           ^
          i           j

tmp: { 1,  ,  ,  ,  ,  ,  ,  ,  ,   }
          ^
          k

    A[j] (2) is less than A[i] (4) - so copy A[j] into tmp and advance j and k

A:   { 1, 4, 5, 6, 7, 2, 3, 4, 7, 9 }
          ^              ^
          i              j

tmp: { 1, 2,  ,  ,  ,  ,  ,  ,  ,   }
             ^
             k

    A[j] (3) is less than A[i] (4) - so copy A[j] into tmp and advance j and k

A:   { 1, 4, 5, 6, 7, 2, 3, 4, 7, 9 }
          ^                 ^
          i                 j

tmp: { 1, 2, 3,  ,  ,  ,  ,  ,  ,   }
                ^
                k

    A[i] (4) is equal to  A[j] (4) - so copy A[i] into tmp and advance i and k

A:   { 1, 4, 5, 6, 7, 2, 3, 4, 7, 9 }
             ^              ^
             i              j

tmp: { 1, 2, 3, 4,  ,  ,  ,  ,  ,   }
                   ^
                   k

    A[j] (4) is less than A[i] (5) - so copy A[j] into tmp and advance j and k

A:   { 1, 4, 5, 6, 7, 2, 3, 4, 7, 9 }
             ^                 ^
             i                 j

tmp: { 1, 2, 3, 4, 4,  ,  ,  ,  ,   }
                      ^
                      k

    ...

    A[i] (7) is equal to  A[j] (7) - so copy A[i] into tmp and advance i and k

A:   { 1, 4, 5, 6, 7, 2, 3, 4, 7, 9 }
                      ^        ^
                      i        j

tmp: { 1, 2, 3, 4, 4, 5, 6, 7,  ,   }
                               ^
                               k

    The first subarray has been exhausted, which means the condition (i <= mid) is false, so the loop stops executing. (If the second subarray was exhausted instead, then the condition (j <= hi) would be false, so the loop would also stop executing.) The next two loops simply copy the remaining elements from the non-exhausted subarray into tmp. In this example, the first subarray was exhausted, so the first loop doesn't actually do anything - the second loop copies the remaining elements from the second subarray into tmp.

    A:   { 1, 4, 5, 6, 7, 2, 3, 4, 7, 9 }
                      ^              ^
                      i              j

tmp: { 1, 2, 3, 4, 4, 5, 6, 7, 7, 9 }
                                     ^
                                     k

    Notice that tmp contains all of the elements of the entire subarray in sorted order. All that needs to be done now is to copy the elements from tmp back into the original array. tmp is no longer needed, so it is freed.

    A:   { 1, 2, 3, 4, 4, 5, 6, 7, 7, 9 }

  4. An important operation in the quicksort algorithm is partition, which takes an element called the pivot, and reorganises the elements in the subarray A[lo..hi] such that all elements to the left of the pivot in the subarray are less than or equal to the pivot, and all elements to the right of the pivot in the subarray are greater than the pivot.

    Here is one possible implementation of partition:

    int partition(int A[], int lo, int hi) {
	int pivot = A[lo];

	int l = lo + 1;
	int r = hi;
	while (true) {
		while (l < r && A[l] <= pivot) l++;
		while (l < r && A[r] >= pivot) r--;
		if (l == r) break;
		swap(A, l, r);
	}

	if (pivot < A[l]) l--;
	swap(A, lo, l);
	return l;
}

    Show how the call partition(A, 0, 9) would partition each of these arrays. What index is returned by each of these calls?

    1. { 5, 3, 9, 6, 4, 2, 9, 8, 1, 7 }
    2. { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
    3. { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }

    Answer:

    1. { 4, 3, 1, 2, 5, 6, 9, 8, 9, 7 } => returns index 4
    2. { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } => returns index 0
    3. { 0, 8, 7, 6, 5, 4, 3, 2, 1, 9 } => returns index 9

  5. Consider the following shell sort algorithm (based on Sedgewick's implementation):

    void shellSort(int a[], int lo, int hi)
{
	int h;
	for (h = 1; h <= (hi - lo) / 9; h = 3 * h + 1);

	for (; h > 0; h /= 3) {
		for (int i = lo + h; i <= hi; i++) {
			int val = a[i];
			int j = i;
			while (j >= lo + h && val < a[j - h]) {
				a[j] = a[j - h];
				j -= h;
			}
			a[j] = val;
		}
	}
}

    Describe how this would sort an array containing the first 100 positive integers sorted in descending order (i.e. {100, 99, 98, 97, 96, 95, ... , 1}).

    Answer:

    Execution of shell sort on {100, 99, 98, 97, 96, 95, ... , 1}:

    • the first loop sets h = 13
    • the main loop uses values of h = 13, 4, 1
    • on the first pass (h == 13) it effectively does insertion sort using subsets of the array consisting of every 13th element (e.g. subsets with indices (0, 13, 26, 39, ...) and (1, 14, 27, 40, ...) and so on)
    • on the second pass (h == 4) it effectively does insertion sort using subsets of the array consisting of every 4th element (e.g. subsets with indices (0, 4, 8, 12, 16, ...) and (1, 5, 9, 13, 20, ...) and so on)
    • on the final pass (h == 1) it does an insertion sort over the whole array, but with fewer moves because the array is already somewhat sorted

  6. Show how radix sort would sort the following array of strings:

    [0] set
[1] how
[2] cup
[3] hob
[4] paw
[5] hat
[6] cob
[7] pot

    Answer:

    Radix sort works by performing multiple stable sorts. It first sorts the strings by their last character, then sorts them by their second-last character, and so on, with the final sort sorting the strings by their first character.

    After sorting by the third character:

    [0] hob
[1] cob
[2] cup
[3] set
[4] hat
[5] pot
[6] how
[7] paw

    After sorting by the second character:

    [0] hat
[1] paw
[2] set
[3] hob
[4] cob
[5] pot
[6] how
[7] cup

    After sorting by the first character:

    [0] cob
[1] cup
[2] hat
[3] hob
[4] how
[5] paw
[6] pot
[7] set

Revision Questions

These questions are intended for revision.

  1. Explain what these properties mean in relation to sorting algorithms:

    • Stability
    • Adaptability
    • Comparison-based

    Answer:

    • Stability: A sorting algorithm is stable if it maintains the relative order of items with equal sort keys.
    • Adaptiveness: Whether or not the pre-sortedness of the input affects the running time. A sorting algorithm is adaptive if it runs faster when the input is already partially sorted.
    • Comparison-based: A sorting algorithm is comparison-based if it examines the data only through comparison operators (such as < and ≤). Examples of where sorting algorithms are not comparison based are when an item is used with the modulo operator (as in radix sort) or as an index (as in counting sort).

  2. How many comparisons would be required to sort this array

    int a[] = {4, 3, 6, 8, 2};

    for each of the following sorting algorithms:

    1. selection sort
    2. bubble sort
    3. insertion sort

    Answer:

    The comparisons are highlighted in red.

    1. selection sort

      Iteration 1:
4  3  6  8  2  # assume 4 is the smallest item
4  3  6  8  2  # found a smaller item, 3
4  3  6  8  2
4  3  6  8  2
4  3  6  8  2  # found a smaller item, 2
2  3  6  8  4  # swap smallest item with item at index 0

Iteration 2:
2  3  6  8  4  # assume 3 is the next-smallest item
2  3  6  8  4
2  3  6  8  4
2  3  6  8  4
2  3  6  8  4  # swap next-smallest item with item at index 1

Iteration 3:
2  3  6  8  4  # assume 6 is the next-smallest item
2  3  6  8  4
2  3  6  8  4  # found a smaller item, 4
2  3  4  8  6  # swap next-smallest item with item at index 2

Iteration 4:
2  3  4  8  6  # assume 8 is the next-smallest item
2  3  4  8  6  # found a smaller item, 6
2  3  4  6  8  # swap next-smallest item with item at index 3

Done

      10 comparisons are made in total.

    2. bubble sort (bubble-up)

      Iteration 1:
4  3  6  8  2  # 4 and 3 are out of order, swap
3  4  6  8  2
3  4  6  8  2
3  4  6  8  2  # 8 and 2 are out of order, swap
3  4  6  2  8

Iteration 2:
3  4  6  2  8
3  4  6  2  8
3  4  6  2  8  # 6 and 2 are out of order, swap
3  4  2  6  8

Iteration 3:
3  4  2  6  8
3  4  2  6  8  # 4 and 2 are out of order, swap
3  2  4  6  8

Iteration 4:
3  2  4  6  8  # 3 and 2 are out of order, swap
2  3  4  6  8

Done

      10 comparisons are made in total.

      adaptive bubble sort (bubble-down)

      Iteration 1:
4  3  6  8  2  # 8 and 2 are out of order, swap
4  3  6  2  8  # 6 and 2 are out of order, swap
4  3  2  6  8  # 3 and 2 are out of order, swap
4  2  3  6  8  # 4 and 2 are out of order, swap
2  4  3  6  8

Iteration 2:
2  4  3  6  8
2  4  3  6  8
2  4  3  6  8  # 4 and 3 are out of order, swap
2  3  4  6  8

Iteration 3:
2  3  4  6  8
2  3  4  6  8
2  3  4  6  8

Finished an iteration without swaps, done

      9 comparisons are made in total.

    3. insertion sort

      Iteration 1:
4  3  6  8  2  # in this iteration, we "insert" 3
4  3  6  8  2  # 4 and 3 are out of order, so we shift 3 down
3  4  6  8  2  # reached bottom of array, so 3 must be in the right place

Iteration 2:
3  4  6  8  2  # in this iteration, we "insert" 6
3  4  6  8  2  # 4 and 6 are in order, so we stop
3  4  6  8  2

Iteration 3:
3  4  6  8  2  # in this iteration, we "insert" 8
3  4  6  8  2  # 6 and 8 are in order, so we stop
3  4  6  8  2

Iteration 4:
3  4  6  8  2  # in this iteration, we "insert" 2
3  4  6  8  2  # 8 and 2 are out of order, so we shift 2 down
3  4  6  2  8  # 6 and 2 are out of order, so we shift 2 down
3  4  2  6  8  # 4 and 2 are out of order, so we shift 2 down
3  2  4  6  8  # 3 and 2 are out of order, so we shift 2 down
2  3  4  6  8  # reached bottom of array, so 2 must be in the right place

Done

      7 comparisons are made in total.

  3. It is easy to check whether an array of integers is sorted. A trickier problem is to determine whether a sorting algorithm produced a stable sort. Assume that the array is composed of Items with two fields, as in:

    typedef struct {
	int a;
	int b;
} Item;

    Assume also that the array has been sorted on the Item.a field.

    Given the final sorted array alone, you cannot determine whether the sort was stable. We also assume that the sorting client keeps a copy of the original array, which is available for checking.

    Given the above, write a function that takes the original array, the sorted array, and determines whether the sort was stable. The function has the following interface:

    int isStableSort(Item original[], Item sorted[], int size) { ... }

    Answer:

    A simple solution would be to run a sorting algorithm that is known to be stable (such as bubble sort, insertion sort, or merge sort) on the original array, and check whether the output of this algorithm matches the given sorted array. If they match, then the sort was stable (as a stable sorting algorithm has only one possible output). If they don't, then the sort was unstable.

    Here is a more inefficient solution, which uses the definition of stability to check that items with the same sort key remain in the same relative order.

    bool isStableSort(Item original[], Item sorted[], int size) {
    int i, j, k, key;
    
    for (i = 0; i < size; i++) {
        key = sorted[i].a;
        
        j = 0; k = 0;
        
        while (j < size && k < size) {
            for (; j < size; j++)
                if (sorted[j].a == key) break;
            
            for (; k < size; k++)
                if (original[k].a == key) break;
                
            if (j < size && k < size) {
                if (sorted[j].b != original[k].b)
                    return false;
                    
                j++; k++;
            }
        }
    }
    return true;
}

    Here is an efficient solution which uses a hash table that maps the type of the key (in this case, an integer) to a Queue.

    bool isStableSort(Item original[], Item sorted[], int size) {
	HashTable ht = HashTableNew();

	for (int i = 0; i < size; i++) {
		if (!HashTableContains(ht, original[i].a)) {
			HashTableSet(ht, original[i].a, QueueNew());
		}
		Queue q = HashTableGet(ht, original[i].a);
		QueueEnqueue(q, original[i].b);
	}
	
	for (int i = 0; i < size; i++) {
		Queue q = HashTableGet(ht, sorted[i].a);
		if (QueueDequeue(q) != sorted[i].b) {
			return false;
		}
	}
	
	return true;
}

  4. Write a version of selection sort that sorts a linked list. The sort should modify the original list - do not create any new nodes. The function has the following signature:

    struct node {
	int value;
	struct node *next;
};

struct node *selectionSort(struct node *list) { ... }

    Answer:

    Keeping the spirit of array-based selection sort, each iteration of this algorithm does the following:

    • find the largest element remaining in the original list
    • remove the largest element from the original list
    • insert the element at the front of the new list

    struct node *selectionSort(struct node *list) {
	struct node *old = list;
	struct node *sorted = NULL; // result
	
	while (old != NULL) {
		// find largest node in old list
		struct node *max = listMax(old);
		
		// unlink largest node in old list
		old = listUnlinkNode(old, max);
		
		// add node to beginning of list
		max->next = sorted;
		sorted = max;
	}
	
	return sorted;
}

// Returns a pointer to the node containing the largest
// element of the given list.
static struct node *listMax(struct node *list) {
	struct node *max = list;
	for (struct node *curr = list; curr != NULL; curr = curr->next) {
		if (curr->value > max->value) {
			max = curr;
		}
	}
	return max;
}

// Removes a given node from a list without freeing it.
static struct node *listUnlinkNode(struct node *list, struct node *node) {
	if (list == node) {
		return list->next;
	} else {
		list->next = listUnlinkNode(list->next, node);
		return list;
	}
}