JAVA programming
Narayan
project3.docxProgramming 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(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.
112 CHAPTER 3 Simple Sorting
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<maxSize; j++) // insert in-order items
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
