**Tom Kelliher, CS23**

**Apr. 23, 1997**

Solve the recurrences:

- Bubble sort.
- Selection sort.
- Insertion sort.

How slow are they?

What distinguishes them?

Stirling's approximation:

Permutations and decision trees:

Algorithm:

Split the array, A, into two pieces, A1 and A2 Recursively sort each piece Empty A while neither A1 nor A2 is empty if the first item in A1 is smaller than the first item in A2 add A1's item to the end of A, removing it from A1 else Add A2's item to the end of A, removing it from A2 end_if end_while one of A1, A2 is not empty -- move its elements to the end of A

See the home page for an implementation.

Efficiency:

- Number of comparisons.
- Memory used.

Internal/External sorting method.

- Worst-case, average-case.
- Pivot Selection.
- Key: efficiency of partitioning.

Algorithm:

QuickSort(A[], f, l) { if (f < l) { choose a pivot, p, from A[f...l] partition A about p // index of p is pIndex QuickSort(A, f, pIndex - 1) QuickSort(A, pIndex, l) } }

Satisfaction of recursive requirements?

What happens if one of the partitions is always empty?

How can we guarantee a ``good'' pivot value?

/********************************************************************** * Precondition: A has len elements and A[0] is the desired pivot * element. * * Postcondition: Returns the index, s, of the pivot element. * A[i] < A[s] for 0 <= i < s and A[s] <= A[j] for s < j < len. **********************************************************************/ int partition(int A[], int len) { int s = 1; int l = len - 1; // invariant: A[i] < A[0] for 1 <= i < s and // A[0] <= A[j] for l < j < len. while (s < l) { if (A[s] < A[0]) // A[s] belongs in first partition. ++s; else // A[s] belongs in second partition: make room. { swap(A[s], A[l]); --l; } } // A[s] could either be in first or second partition. if (A[s] >= A[0]) // A[s] is in second partition --- don't move it. --s; swap(A[0], A[s]); // Swap partition element with last element in // first partition. return s; }

Number of comparisons?

Consider sorting ``constant width'' numbers.

Constant time sort.

Bucket implementation.

Mon Apr 21 14:43:28 EDT 1997