CS 127, Data Structures
Project 6: Questions on Sorting
Due at the beginning of class on Friday, 10/27/00.
Hand in your answers on paper. There is no need to electronically submit
anything for this project.
-
On paper, sort 9, 8, 7, 6, 5, 4, 3, 2, 1 using Shellsort with increments
{7, 3, 1}.
-
On paper, sort 3, 1, 4, 1, 5, 9, 2, 6 using merge sort.
-
On paper, sort 3, 1, 4, 1, 5, 9, 2, 6 using quicksort with pivot in the
first position.
-
Suppose that you have an array of n elements, containing only two distinct
keys, true and false. Give an O(n) algorithm to rearrange
the list so that all false elements precede the true elements.
You may use only constant extra space.
-
The choice of pivot for quicksort can dramatically affect its performance.
Some common choices are:
-
The first element
-
The middle element
-
A randomly selected element
-
The median element of the array
-
The median element of the first three elements in the array
Comment on each of the above choices. What are the pros and cons
of each? Under what situations are they good or bad ideas?