Programming Projects Assignment
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(N2) 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(N2) 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.
And here are the respective instruction given by teacher to follow
3_1 Develop bidirectional method bidiBubbleSort().
The main( ) may look like:
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayBub arr; // reference to array
arr = new ArrayBub(maxSize); // create the array
arr.insert(7); // insert 7 items
arr.insert(6);
arr.insert(5);
arr.insert(4);
arr.insert(3);
arr.insert(2);
arr.insert(1);
arr.display(); // display items
arr.bidiBubbleSort(); // bidirectional bubble sort
arr.display(); // display them again
} // end main()
The output may look like:
7 6 5 4 3 2 1
1 2 3 4 5 6 7
3_2 It is a simple project and will give you minimum points.
Define the median( ) method.
The main( ) may look like:
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayIns arr; // reference to array
arr = new ArrayIns(maxSize); // create the array
arr.insert(77); // insert 10 items
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33); // even number of elems
arr.display(); // display items
long med = arr.median(); // find median
System.out.println("Median is " + med); // show median
arr.insert(109); // odd number of elems
med = arr.median(); // find median
arr.display(); // display items
System.out.println("Median is " + med); // show median
} // end main()
The output may look like:
77 99 44 55 22 88 11 0 66 33
Median is 55
0 11 22 33 44 55 66 77 88 99 109
Median is 55
3_3 Define the method noDups( ).
The main( ) may look like:
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayIns arr; // reference to array
arr = new ArrayIns(maxSize); // create the array
arr.insert(12);
arr.insert(12);
arr.insert(13);
arr.insert(13);
arr.insert(15);
arr.insert(27);
arr.insert(27);
arr.insert(27);
arr.insert(27);
arr.insert(32);
arr.insert(33);
arr.insert(34);
arr.insert(44);
arr.insert(44);
arr.insert(55);
arr.insert(56);
arr.insert(57);
arr.insert(57);
arr.display(); // display array
arr.noDups(); // remove duplicates
arr.display(); // display it again
} // end main()
The output may look like:
12 12 13 13 15 27 27 27 27 32 33 34 44 44 55 56 57 57
12 13 15 27 32 33 34 44 55 56 57
3_4 Develop the method oddEvenSort( ). In the textbook in the description there is a small mistake (slip pen): even indexes are 2, 4, ... . But should be 0, 2, 4, ... .
You may use an outer loop. The limit on the outer loop is related to nElems like this:
nElems 1 2 3 4 5 6
k <1 1 2 2 3 3
The main( ) method may look like:
public static void main(String[] args)
{
int maxSize = 14; // array size
ArrayIns arr; // reference to array
arr = new ArrayIns(maxSize); // create the array
arr.insert(81);
arr.insert(77);
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(77);
arr.insert(11);
arr.insert(00);
arr.insert(44);
arr.insert(66);
arr.insert(33);
arr.insert(33);
arr.display(); // display items
arr.oddEvenSort(); // sort them
arr.display(); // display them again
} // end main()
The output may look like:
81 77 99 44 55 22 88 77 11 0 44 66 33 33
0 11 22 33 33 44 44 55 66 77 77 81 88 99
See additionally the output that traces odd-even code:
81 77 99 44 55 22 88 77 11 0 44 66 33 -1 -2
81 77 99 44 55 22 88 11 77 0 44 33 66 -2 -1
77 81 44 99 22 55 11 88 0 77 33 44 -2 66 -1
77 44 81 22 99 11 55 0 88 33 77 -2 44 -1 66
44 77 22 81 11 99 0 55 33 88 -2 77 -1 44 66
44 22 77 11 81 0 99 33 55 -2 88 -1 77 44 66
22 44 11 77 0 81 33 99 -2 55 -1 88 44 77 66
22 11 44 0 77 33 81 -2 99 -1 55 44 88 66 77
11 22 0 44 33 77 -2 81 -1 99 44 55 66 88 77
11 0 22 33 44 -2 77 -1 81 44 99 55 66 77 88
0 11 22 33 -2 44 -1 77 44 81 55 99 66 77 88
0 11 22 -2 33 -1 44 44 77 55 81 66 99 77 88
0 11 -2 22 -1 33 44 44 55 77 66 81 77 99 88
0 -2 11 -1 22 33 44 44 55 66 77 77 81 88 99
-2 0 -1 11 22 33 44 44 55 66 77 77 81 88 99
-2 -1 0 11 22 33 44 44 55 66 77 77 81 88 99
-2 -1 0 11 22 33 44 44 55 66 77 77 81 88 99
You can write a similar code, but it is optional.
3_5 Ad a method
public void put(int index, long value) // insert at index
and modify the method insertionSort( ).
The main( ) method may look like:
public static void main(String[] args)
{
int maxSize = 25; // array size
ArrayIns arr; // reference to array
arr = new ArrayIns(maxSize); // create the array
for(int j=0; j arr.insert(j);
arr.put(10, 7); // out of order item at 10
arr.put(20, 13); // out of order item at 20
arr.display(); // display items
arr.insertionSort(); // insertion-sort them
arr.display();
} // end main()
The output may look like:
0 1 2 3 4 5 6 7 8 9 7 11 12 13 14 15 16 17 18 19 13 21 22 23 24
Copies=58, comparisons=34
0 1 2 3 4 5 6 7 7 8 9 11 12 13 13 14 15 16 17 18 19 21 22 23 24
3_6 Modify insertion sort to remove duplicates.
/* Just after the normal comparison (top of while loop), the two elements are also compared to see if they're duplicates. If so, the one in 'temp' is replaced by a sentinal, which has a value lower than any key. On exit from the while loop, this sentinal will end up inserted at the lowest index, following the shifts of all the larger items to the right.
Now we no longer end the while loop when 'in' gets to 1, but when it gets to 'start', which records the number of duplicates found so far. At the buttom of the for loop, we check if there is a sentinal at the lowest index ('start'). If so, we bump up 'start', which makes the sentinal invisible to the rest of the algorithm. This will happen whenever there's a duplicate, so the array will shrink from the bottom up. The smaller the array, the faster the sorting algorithm runs.
At the end of this method we shift the cells left (writing over the sentinals), so the array again starts at 0. (One can imagine situations where this shift would not be necessary).
*/
The main( ) may look like:
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayIns arr; // reference to array
arr = new ArrayIns(maxSize); // create the array
arr.insert(77);
arr.insert(77);
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(77);
arr.insert(11);
arr.insert(00);
arr.insert(44);
arr.insert(66);
arr.insert(33);
arr.insert(33);
arr.display(); // display array
arr.insertionSort(); // sort and de-dup it
arr.display(); // display it again
} // end main()
The output may look like:
77 77 99 44 55 22 88 77 11 0 44 66 33 33
0 11 22 33 44 55