section 8 11

Adapt the Dutch National Flag algorithm to do the quicksort partitioning. Consider the red region to be those values less than the pivot, the white region to be those values equal to the pivot, and the blue region to be those values equal to the pivot. You should initially sort the first, middle, and last items and use the middle value as the pivot value.

Chapter Review

We analyzed several sorting algorithms; their performance is summarized in Table 8.4.
Two quadratic algorithms, O(n²), are selection sort and insertion sort. They give satisfactory performance for small arrays (up to 100 elements). Generally, insertion sort is considered to be the best of the quadratic sorts.
Shell sort, O(n^5/4), gives satisfactory performance for arrays up to 5000 elements.
Quicksort has average-case performance of O(n log n), but if the pivot is picked poorly, the worst-case performance is O(n²).
Merge sort and heapsort have O(n log n) performance.
The Java API contains â€œindustrial-strengthâ€ sort algorithms in the classes java.util.Arrays and java.util.Collections. The methods in Arrays use a mixture of quicksort and insertion sort for sorting arrays of primitive-type values and merge sort for sorting arrays of objects. For primitive types, quicksort is used until the size of the subarray reaches the point where insertion sort is quicker (seven elements or less). The sort method in Collections merely copies the list into an array and then calls Arrays.sort.