Week 03 Tutorial Questions

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.

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

  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?

  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!

  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

  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 }

Revision Questions

These questions are intended for revision.

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

    • Stability
    • Adaptability
    • Comparison-based

  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

  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) { ... }

  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) { ... }

  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