============================================================================
           Faculty of Applied Science and Engineering, University of Toronto
                     CSC181: Introduction to Computer Programming, Fall 2000

Questions of Week 7
============================================================================

------------------
Answered questions
------------------

1. Write the insertion sort.

What we want: a[0..n-1] is sorted

Basic idea:

    +-----------------------------------+
  a |    sorted    |     unsorted       |
    +-----------------------------------+
     0              j                    n

a[0..j-1] is sorted in non-decreasing order
a[j..n-1] is unsorted

Initialization: j = 1 (since the array a[0..0] is sorted)

Exit condition: j == n

Body: Insert a[j] into appropriate place in a[0..j-1]

Code:

void insertionSort(int a[], int n) {
	int j = 1;
	while (j < n) {
		int k = a[j];
		int i = j - 1;
		while (i != -1 && a[i] > k) {
			a[i+1] = a[i];
			i--;
		}
		a[i+1] = k;
		j++;
	}
}

2. Write the selection sort:

What we want: a[0..n-1] is sorted

Basic idea:

    +-----------------------------------+
  a |  j smallest   |    unsorted       |
    +-----------------------------------+
     0               j                   n

a[0..j-1] contains j smallest elements, in non-decreasing order
a[j..n-1] is unsorted

Initialization: j = 0

Exit condition: j == n

Body: Find jth smallest element, and swap it with a[j]

Code:

void selectionSort(int a[], int n) {
	int j;
	for (j = 0; j != n; j++) {
		int i, m, k;
		for (m = j, i = m+1; i < n; i++) {
			if (a[i] < a[m]) {
				m = i;
			}
		}
		k = a[m];
		a[m] = a[j];
		a[j] = k;
	}
}

3. Write the binary search:

What we want: For an array a of size n sorted in non-decreasing order,
we want the index of the rightmost element <= k.

Basic idea:

    +-----------------------------------+
  a |   <= k   |      ??      |   > k   |
    +-----------------------------------+
     0        i                j         n

a[0..i] contains elements <= k
a[j..n-1] contains elements > k
a[i+1..j-1] contains unknown elements

Initialization: i = -1, j = n

Exit condition: i+1 == j

Body: Pick middle element of a[i+1..j-1], use it to reduce unknown
range in half

int binarySearch(int a[], int n, int k) {
	int i = -1;
	int j = n;
	while (i+1 != j) {
		int m = (i+j)/2;
		if (a[m] <= k)
			i = m;
		else
			j = m;
	}
	return i;
}

--------------------
Unanswered questions
--------------------

4. Suppose that insertions account for 10% of the operations on an
array, and that searches account for the other 90%.

You know that:

- insertion sort takes running time in the order of pow(n,2)

- binary search takes running time in the order of lg n

- linear search takes running time in the order of n

- inserting into a sorted array takes running time in the order of n

- inserting into an unsorted array takes running time in the order of
  1

Compare the following insert-and-search schemes. Is any of the schemes
definitively better than the others?

a) Use unsorted array; insert, then use linear search

b) Use unsorted array; insert, then use insertion sort, then use
binary search

c) Use sorted array; insert, then use binary search

You can assume that insertions are done in a batch, and then searches
are done in a batch.