Week 03 Tutorial Answers

Sorting

Resources

Time Complexity Revision

  1. Consider the following Search Algorithms:

    • Algorithm 1 starts from the left and scans right.
    • Algorithm 2 starts from the right and scans left.
    They both search the array for a given value.

    Search Algorithm 1

    Index 0 1 2 3 4
    Value - - - - -

    Search Algorithm 2

    1. What index results in the Worst-Case for Algorithm 1?
    2. What is the Time Complexity for Algorithm 1?
    3. Are the above questions the same for Algorithm 2?
    4. What method could we use to definitively tell apart both Search Algorithms if we don't have access to code but can execute the programs.

    Answer:

    1. Index 4 would result in the Worst-Case search for Algorithm 1 since it would have to scan through every element starting from index 0.
    2. Algorithm 1 has a Worst-Case Time Complexity \(O(n)\) because it has to search through all \(n\) values in the array.
    3. Algorithm 2 Worst-Case search is index 0 instead. However the Time Complexity is still \(O(n)\) because Algorithm 2 starts at index 4 and will scan through all \(n\) elements.
    4. To tell the two Algorithms apart, we should give a known input and see how the output scales as \(n\) gets larger using the time command.
      Index 0 1 2 ... \(n-2\) \(n-1\)
      Value 10 3 67 ... 1 57
      Make the program search for value 57. If the timing results from time increase as \(n\) increases, then the program is Algorithm 1. Otherwise if the timing results stay constant as \(n\) increases, the program is Algorithm 2.

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. Show how radix sort would sort the following array of strings:

    [0] bug
[1] day
[2] dog
[3] dam
[4] dot

    Why is it important that each sub-sort performed by radix sort is stable?

    Answer:

    First, the words are sorted by their third character:

    [0] bug
[1] dog
[2] dam
[3] dot
[4] day

    Then, they are sorted by their second character:

    [0] dam
[1] day
[2] dog
[3] dot
[4] bug

    Then, they are sorted by their first character:

    [0] bug
[1] dam
[2] day
[3] dog
[4] dot

    It is important for each sub-sort to be stable because if two words have the same letter in the same position (e.g., d in the first position), then they should be ordered based on the letters that come next, which is what the words were sorted by in previous iterations. If the sub-sorts were not stable, then they would be throwing out the sorting work done previously which can cause the words to end up out of order at the end.

  3. Are you familiar with how these algorithms work?

    • Selection sort
    • Bubble sort
    • Insertion sort

    If not, use VisuAlgo to see them in action. Think about their properties, especially their best-case, worst-case and stability - this will help in the group exercises!

    Answer:

    The answer to the question should be "yes"!

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

    Demonstrate how the merge function works by showing how merge(A, 0, 4, 9) would merge the two sorted halves of this array into a single sorted array:

    //    0  1  2  3  4  5  6  7  8  9
A = { 1, 4, 5, 6, 7, 2, 3, 4, 7, 9 }
//    ^           ^              ^
//    lo          mid            hi

    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 }

  5. 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

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

  5. 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