## Programming Projects

Writing programs that solve the Programming Projects helps to solidify your understanding of the material and demonstrates how the chapter's concepts are applied. (As noted in the Introduction, qualified instructors may obtain completed solutions to the Programming Projects on the publisher's Web site.)

** 3.1** In the `bubbleSort.java` program (Listing 3.1) and the
BubbleSort Workshop applet, the `in` index always goes from left to
right, finding the largest item and carrying it toward `out` on the
right. Modify the `bubbleSort()` method so that it's bidirectional.
This means the `in` index will first carry the largest item from left
to right as before, but when it reaches `out`, it will reverse and
carry the smallest item from right to left. You'll need two outer indexes,
one on the right (the old `out`) and another on the left.

**3.2** Add a method called `median()` to the `ArrayIns`
class in the `insertSort.java` program (Listing 3.3). This method should
return the median value in the array. (Recall that in a group of numbers half
are larger than the median and half are smaller.) Do it the easy way.

**3.3** To the `insertSort.java` program (Listing 3.3), add a
method called `noDups()` that removes duplicates from a previously
sorted array without disrupting the order. (You can use the `insertionSort()`
method to sort the data, or you can simply use `main()` to insert the
data in sorted order.) One can imagine schemes in which all the items from
the place where a duplicate was discovered to the end of the array would be
shifted down one space every time a duplicate was discovered, but this would
lead to slow O(N^{2}) time, at least when there were a lot of duplicates.
In your algorithm, make sure no item is moved more than once, no matter how
many duplicates there are. This will give you an algorithm with O(N) time.

**3.4** Another simple sort is the odd-even sort. The idea is to repeatedly
make two passes through the array. On the first pass you look at all the pairs
of items, `a[j]` and `a[j+1]`, where `j` is odd (`j`
= 1, 3, 5, ...). If their key values are out of order, you swap them. On the
second pass you do the same for all the even values (`j` = 2, 4, 6,
...). You do these two passes repeatedly until the array is sorted. Replace
the `bubbleSort()` method in `bubbleSort.java` (Listing 3.1)
with an `oddEvenSort()` method. Make sure it works for varying amounts
of data. You'll need to figure out how many times to do the two passes.

The odd-even sort is actually useful in a multiprocessing environment, where a separate processor can operate on each odd pair simultaneously and then on each even pair. Because the odd pairs are independent of each other, each pair can be checked—and swapped, if necessary—by a different processor. This makes for a very fast sort.

**3.5** Modify the `insertionSort()` method in `insertSort.java`
(Listing 3.3) so it counts the number of copies and the number of comparisons
it makes during a sort and displays the totals. To count comparisons, you'll
need to break up the double condition in the inner `while` loop. Use
this program to measure the number of copies and comparisons for different
amounts of inversely sorted data. Do the results verify O(N^{2}) efficiency?
Do the same for almost-sorted data (only a few items out of place). What can
you deduce about the efficiency of this algorithm for almost-sorted data?

**3.6** Here's an interesting way to remove duplicates from an array.
The insertion sort uses a loop-within-a-loop algorithm that compares every
item in the array with every other item. If you want to remove duplicates,
this is one way to start. (See also Exercise 2.6 in Chapter 2.) Modify the
`insertionSort()` method in the `insertSort.java` program so
that it removes duplicates as it sorts. Here's one approach: When a duplicate
is found, write over one of the duplicated items with a key value less than
any normally used (such as –1, if all the normal keys are positive).
Then the normal insertion sort algorithm, treating this new key like any other
item, will put it at index 0. From now on the algorithm can ignore this item.
The next duplicate will go at index 1, and so on. When the sort is finished,
all the removed dups (now represented by –1 values) will be found at
the beginning of the array. The array can then be resized and shifted down
so it starts at 0.