Week 09 Tutorial Questions

Sorting

Resources

Questions

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

    • Stability
    • Adaptability
    • Comparison-based

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

    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

  3. Sorting algorithms generally use comparison on the key to determine ordering. Ordering of items with equal keys has been left to the stability of the sorting algorithm used. Sometimes, it is important that items with the same key be ordered on a secondary key.

    Write a function that takes two items and determines an order based on the primary key k and then on the value of a secondary key j. The function should return -1 if the first item is "less than" the second item, 1 if the first item is "greater than" the second item, and 0 if the items are equal. The function has the following signature:

    typedef struct item {
	int k;
	int j;
	/* ... other fields ...*/
} Item;

int itemCmp(Item a, Item b) { ... }

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

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

  6. An important operation in the quicksort algorithm is partition, which takes a 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]; // pivot
	int l = lo + 1;
	int r = hi;
	while (l < r) {
		while (l < r && A[l] <= pivot) l++;
		while (l < r && A[r] >= pivot) r--;
		if (l == r) break;
		swap(A, l, r);
	}
	int m = A[l] <= pivot ? l : l - 1;
	swap(A, lo, m);
	return m;
}

    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. { 5, 9, 8, 7, 6, 0, 1, 2, 3, 4 }
    3. { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
    4. { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }

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

  8. 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:

    typedef struct Node *List;
struct Node {
	int value;
	List next;
};

List selectionSort(List ls) { ... }

  9. Write a program that reads two sorted files and merges them onto standard output. The names of the files are provided as command-line arguments.

    ./merge File1 File2

    If either file is not readable, exit with the error message:

    Invalid input file(s).

  10. Write a program that reads data about students in the form:

    5059413  Daisy  3762  15
3461045  Dotty  3648  42
3474881  Daisy  8543  16
5061020  David  3970   3

    from standard input, and then:

    • stores it in an array of Student structs {zid, name, prog, favnum}
    • uses qsort() to sort it, making use of the stuCmp() function (see below)
    • order is initially by name, and then by zID if the names are the same
    • writes out sorted array, one Student per line
    • use the following format for printing students "%7d %-20s %4d %d\n"

    You can assume that all of the input lines contain valid student entries, and that the MAXxxx constants are defined, and large enough to deal with any input data. You do not need to implement the stuCmp() function; just assume it exists.

    Use the following template for the program:

    typedef struct student {
	int  zid;            // 7-digit number
	char name[MAXNAME];  // names are stored *within* the struct
	int  prog;           // 4-digit number
	int  favnum;         // favourite number
} Student;
 
// return -ve if a < b, +ve if a > b, 0 if a == b
int stuCmp(const void *a, const void *b);
 
int main(int argc, char *argv[]) {
	Student students[MAXSTUDENTS];

	// read stdin line-by-line into students[]

	// sort the students[] array

	// print the contents of the students[] array

}