Week 03 Tutorial Questions

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

  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]\))

  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.

  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 }

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

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