Week 03 Tutorial Questions
Sorting
Resources
- USFCA's sorting algorithm visualizers
- VisuAlgo's sorting algorithm visualizers
- structs.sh sorting algorithm visualizers
Questions
-
Consider the following simple table of enrolments, sorted by course code:
course name program COMP1927 Jane 3970 COMP1927 John 3978 COMP1927 Pete 3978 MATH1231 John 3978 MATH1231 Adam 3970 PSYC1011 Adam 3970 PSYC1011 Jane 3970 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
- we used a stable sorting algorithm
- we used an unstable sorting algorithm
-
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]\))
-
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 arrayA
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. -
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?{ 5, 3, 9, 6, 4, 2, 9, 8, 1, 7 }
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
{ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }
-
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.
-
Explain what these properties mean in relation to sorting algorithms:
- Stability
- Adaptability
- Comparison-based
-
How many comparisons would be required to sort this array
int a[] = {4, 3, 6, 8, 2};
for each of the following sorting algorithms:
- selection sort
- bubble sort
- insertion sort
-
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
Item
s 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) { ... }
-
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) { ... }