Sorting algorithms - Data Structures and Problem Solving Using Java - page 390

Exercise 8.2 addressed stable sorting. Write a method that performs a
stable quicksort. To do so, create an array of objects; each object is to
contain a data item and its initial position in the array. (This is the Com-
posite pattern; see Section 3.9.) Then sort the array; if two objects have
identical data items, use the initial position to break the tie. After the
array of objects has been sorted, rearrange the original array.

8.28

Write a simple sorting utility, sort. The sort command takes a filename
as a parameter, and the file contains one item per line. By default the
lines are considered strings and are sorted by normal lexicographic
order (in a case-sensitive manner). Add two options: The -c option
means that the sort should be case insensitive; the -n option means that
the lines are to be considered integers for the purpose of the sort.

8.29

Write a program that reads N points in a plane and outputs any group
of four or more colinear points (i.e., points on the same line). The
obvious brute-force algorithm requires O ( N 4 ) time. However, there is
a better algorithm that makes use of sorting and runs in O ( N 2 log N )
time.

8.30

Suppose a DoubleKeyed object has two keys: a primary key, and a sec-
ondary key. When sorting, if there are ties among the primary key, the
secondary key is used to determine ordering. Rather than modify an
existing algorithm, write a sort routine that invokes quicksort as
needed to sort an array of DoubleKeyed objects.

8.31

In quicksort, instead of selecting three elements, as is done for
median-of-three partitioning, suppose we are willing to select nine
elements, including the first and last, with the other seven equally
spaced in the array.
a.

8.32

Write code to implement median-of-nine partitioning.

b. Consider the following alternate to median-of-nine: group the

items into three groups of three. Find the medians of the three
groups. Then use the median of those medians. Write code to
implement this alternative, and compare its performance to
median-of-nine partitioning.

Two words are anagrams if they contain the same letters in the same
frequency. For instance, stale and least are anagrams of each other.
A simple way to check this is to sort the characters in each word; if
you get the same answer (in the example, we get aelst ), the words are
anagrams of each other. Write a method that tests if two words are
anagrams of each other.

8.33