COSC 282 Lab 7.1 — Partitioning

Introduction

Partitioning, as discussed in chapter 7, can be used as a basis for sorting. In this lab you will modify existing code to carry out partitioning on a set of strings. Various other modifications will prepare you for a future programming project. For each release described below, you should turn clean, commented, code that compiles and runs as intended.

Specific requirements

Working, documented code that compiles, runs without error, and performs according to specification.
Generated HTML javadoc documentation.
A lab report with standard sections (Problem Statement, Program Flow, Classes Needed, Discussion, and Project Code)

Due date

Submit your assignment as a single .zip archive file titled LAB71_lastname.zip.

Steps

Familiarize yourself with the code in partition.java (available in the Example Programs Sakai resources folder). Run the code several times to see what happens.

First, separate the code for the two classes into two files and rename the classes as follows:

ArrayPar --> PArray in file PArray.java
PartitionApp --> PartitionApp in file PartitionApp.java

Make sure your code compiles with no errors and runs properly.
Modify the code in PArray.java to manipulate Strings instead of longs. Change PartitionApp accordingly, using names as the testing data. Sample output should look something like this:
```
A = erin julio fred dennis bob kevin xanadu 
Pivot is julio, Partition is at index 4
A = erin bob fred dennis julio kevin xanadu 
```
Write a second display method in PArray.java; the existing one takes no args and displays the entire array. Make a new display method that takes two ints as arguments and displays from the first to the second.
```
public void display(int low, int high) {  }
```
Modify the output in JArray so it displays the following format:
```
A[0-3] = { erin bob fred dennis } 
```
Note: When you overload methods, it's good practice to put the bulk of the code in the single most specific method; then have less specific methods call the more specific one, sending appropriate values as arguments. In this case, that means that display() should make a call to display(0, nElems).

Modify the code in PartitionApp so that it calls the array.display() methods to print out somthing like this:

A[0-6] = { erin julio fred dennis bob kevin xanadu }

The selected pivot is fred. The partition is at index 3. 

A[0-2] = { bob dennis erin } 
A[4-6] = { julio kevin xanadu }

In your main method, write code to create and partition several different arrays. Use a variety of array sizes(some smaller, some larger); a variety of ranges for the array elements; and a variety of pivots.

In your lab report, discuss your results.

A[0-6] = { erin julio fred dennis bob kevin xanadu }
Pivot is fred, Partition is at index 3
A[0-6] = { erin bob dennis fred julio kevin xanadu }

Note that the following is a proper partition. Even though the pivot [paul] does not end up at the partition point, it is still in the correct portion of the partitioned array:

A[0-9] = { paul xanadu fred dennis bob kevin julio clancy zimbo erin }
Pivot is paul, Partition is at index 7
A[0-9] = { erin clancy fred dennis bob kevin julio xanadu zimbo paul }