Consider the following sorting algorithms:

1. Discuss the "worst case" behavior for these two sorts?
2. How many comparisons were required for each "worst case?"
3. Under what conditions would you select an Insertion sort over the Selection sort?
4. How many comparisons for "worst case" would be made with each sort for 1000 elements?

5. The following function, which is intended to sort an array into ascending order, contains four serious mistakes.
What are they?

void sort (apvector list)
{
    double copy;
    int n = list.length( );
    for (int j = 0;  j < n - 1; j++)
	for (int k = j + 1;  k < n;  k++)
	    if (list[j] < list[k]) // if smaller
		copy = list[k];
		list[k] = list[j];
		list[j] = copy;
}

MATCHING: Name the Sort:

(A) Straight Selection sort
(B) Selection sort with temporary variable
(C) Insertion sort

TRUE / FALSE
T F 1. A sequential or linear search is not always slower than a binary search for an item in an ordered list.
T F 2. A linear search for an item is slowest when the item sought is at the end of a list.
T F 3. Both binary searching and linear searching of an ordered list rely on different forms of trial-and-error to locate a list item.
T F 4. Binary searching works best with unordered lists.
T F 5. The maximum number of comparisons made by a linear search of a list of n items is 1 + log2N.
T F 6. Linear searching works better with ordered lists.

COMPLETION

1. Give an example of an ordered list where a linear search would be faster than a binary search.
2. How long will it take a binary search to find the item you chose in the linear search in 1?
3. Given an example of an ordered list where a linear search will be slower than a binary search for the same item.
4. What is a drawback of binary searching?
5. It is said that it takes n - 1 passes through an array for n data items to complete an insertion sort. Why?