Question: You will be given a Java program with the logic for five basic sorts, along with supporting methods so this logic can be exercised by
You will be given a Java program with the logic for five basic sorts, along with supporting methods so this logic can be exercised by putting a set of random integer values in order, from least to greatest.
Add a Better Bubble Sort this program
? The Better Bubble uses the same approach as the Bubble, but includes optimization logic that efficiently checks whether the data is sorted and the sort can stop.
Add an Insertion Sort to this program
Add logic so that the number of swaps executed and number of comparisons made are tracked and reported out each time a sort is executed.
A brief description of the project, along with a table that documents the swap and compare counts your modifications produce for a set of test runs, is also required.
? Source code all source code in a single Eclipse project
? Overall description of the project including the swap and comparison counts
/*----------------------------------------------------------------------------
* SortTestHarness.java
*
* based on program developed by Dale/Joyce/Weems
* for Object-Oriented Data Structures Using Java Chapter 10
*
---------------------------------------------------------------------------- */
package pp6;
import java.util.*;
import java.text.DecimalFormat;
public class SortTestHarness {
static final int SIZE = 50; // size of array to be sorted
static int[] values = new int[SIZE]; // values to be sorted
static int[] valuesBup = new int[SIZE]; // backup of values
// initialize the values array with random integers from 0 to 99
static void initializeValues() {
Random rand = new Random();
for (int index = 0; index < SIZE; index++)
values[index] = Math.abs(rand.nextInt()) % 100;
}
// checker method that returns true if the array values are sorted, false otherwise
static public boolean isSorted() {
boolean sorted = true;
for (int index = 0; index < (SIZE - 1); index++)
if (values[index] > values[index + 1])
sorted = false;
return sorted;
}
// swap the integers at locations index1 and index2 in the values array
// pecondition: index1 and index2 are >= 0 and < SIZE
static public void swap(int index1, int index2) {
int temp = values[index1];
values[index1] = values[index2];
values[index2] = temp;
}
// displays the contents of the values array
static public void displayValues() {
int value;
DecimalFormat fmt = new DecimalFormat("00");
System.out.println("The values array is:");
for (int index = 0; index < SIZE; index++)
{
value = values[index];
if (((index + 1) % 10) == 0)
System.out.println(fmt.format(value));
else
System.out.print(fmt.format(value) + " ");
}
System.out.println();
}
/*--------------------------------------------------------------*/
// use these methods so that the same set of unsorted data can be
// used for each of the sorts
static void backupValues() {
valuesBup = Arrays.copyOf(values, values.length);
}
static void restoreValues() {
values = Arrays.copyOf(valuesBup, valuesBup.length);
}
/////////////////////////////////////////////////////////////////
static void selectionSort() {
for (int i = 0; i < SIZE-1; i++) {
int indexSmallest = i;
for (int j = indexSmallest+1; j < SIZE; j++) {
if (values[j] < values[indexSmallest]) {
indexSmallest = j;
}
}
swap(i, indexSmallest);
}
}
static void bubbleSort() {
int lastIndex = SIZE-1;
int i = 0;
while (i < lastIndex) {
for (int j = lastIndex; j > i; j--) {
if (values[j] < values[j-1]) {
swap(j, j-1);
}
}
i++;
}
}
// please put your better bubble sort here, thanks
static void insertionSort() {
for (int i = 1; i < SIZE; i++) {
int j = i;
while (j > 0 && values[j] < values[j-1]) {
swap(j, j-1);
j--;
}
}
}
/////////////////////////////////////////////////////////////////
// Merge Sort
static void merge (int leftFirst, int leftLast, int rightFirst, int rightLast)
// Preconditions: values[leftFirst]..values[leftLast] are sorted
// values[rightFirst]..values[rightLast] are sorted
//
// Sorts values[leftFirst]..values[rightLast] by merging the two subarrays.
{
int[] tempArray = new int [SIZE];
int index = leftFirst;
int saveFirst = leftFirst; // to remember where to copy back
while ((leftFirst <= leftLast) && (rightFirst <= rightLast)) {
//compareCount +=3;
if (values[leftFirst] < values[rightFirst]) {
tempArray[index] = values[leftFirst];
leftFirst++;
}
else {
tempArray[index] = values[rightFirst];
rightFirst++;
}
index++;
}
while (leftFirst <= leftLast) { // copy remaining items from left half
//compareCount++;
tempArray[index] = values[leftFirst];
leftFirst++;
index++;
}
while (rightFirst <= rightLast) { // copy remaining items from right half
//compareCount++;
tempArray[index] = values[rightFirst];
rightFirst++;
index++;
}
for (index = saveFirst; index <= rightLast; index++)
values[index] = tempArray[index];
}
// sort the values array using the merge sort algorithm
static void mergeSort(int first, int last) {
if (first < last) {
int middle = (first + last) / 2;
mergeSort(first, middle);
mergeSort(middle + 1, last);
merge(first, middle, middle + 1, last);
}
}
//--- end of DJW merge sort
/////////////////////////////////////////////////////////////////
//
// Quick Sort
static int split(int first, int last) {
int splitVal = values[first];
int saveF = first;
boolean onCorrectSide;
first++;
do
{
onCorrectSide = true;
while (onCorrectSide) { // move first toward last
if (values[first] > splitVal) {
onCorrectSide = false;
}
else
{
first++;
onCorrectSide = (first <= last);
}
}
onCorrectSide = (first <= last);
while (onCorrectSide) { // move last toward first
if (values[last] <= splitVal) {
onCorrectSide = false;
}
else
{
last--;
onCorrectSide = (first <= last);
}
}
if (first < last)
{
swap(first, last);
first++;
last--;
}
} while (first <= last);
swap(saveF, last);
return last;
}
static void quickSort(int first, int last) {
if (first < last) {
int splitPoint;
splitPoint = split(first, last);
// values[first]..values[splitPoint - 1] <= splitVal
// values[splitPoint] = splitVal
// values[splitPoint+1]..values[last] > splitVal
quickSort(first, splitPoint - 1);
quickSort(splitPoint + 1, last);
}
}
/////////////////////////////////////////////////////////////////
//
// Heap Sort
static int newHole(int hole, int lastIndex, int item) {
// If either child of hole is larger than item, return the index
// of the larger child; otherwise it returns the index of hole.
int left = (hole * 2) + 1;
int right = (hole * 2) + 2;
if (left > lastIndex)
// hole has no children
return hole;
else {
if (left == lastIndex) {
// hole has left child only
if (item < values[left])
// item < left child
return left;
else
// item >= left child
return hole;
}
else {
// hole has two children
if (values[left] < values[right]) {
// left child < right child
if (values[right] <= item)
// right child <= item
return hole;
else
// item < right child
return right;
}
else {
// left child >= right child
if (values[left] <= item)
// left child <= item
return hole;
else
// item < left child
return left;
}
}
}
}
// insert item into the tree and ensure shape and order properties
// precondition: current root position is "empty"
static void reheapDown(int item, int root, int lastIndex) {
int hole = root; // current index of hole
int newhole; // index where hole should move to
newhole = newHole(hole, lastIndex, item); // find next hole
while (newhole != hole) {
values[hole] = values[newhole]; // move value up
hole = newhole; // move hole down
newhole = newHole(hole, lastIndex, item); // find next hole
}
values[hole] = item; // fill in the final hole
}
static void heapSort() {
int index;
// Convert the array of values into a heap.
for (index = SIZE/2 - 1; index >= 0; index--)
reheapDown(values[index], index, SIZE - 1);
// Sort the array.
for (index = SIZE - 1; index >=1; index--)
{
swap(0, index);
reheapDown(values[0], 0, index - 1);
}
}
/////////////////////////////////////////////////////////////////
//
// Main
public static void main(String[] args)
{
initializeValues();
backupValues();
displayValues();
System.out.println("values is sorted: " + isSorted());
System.out.println();
selectionSort();
displayValues();
System.out.println("values is selection sorted: " + isSorted());
System.out.println();
restoreValues();
bubbleSort();
displayValues();
System.out.println("values is bubble sorted: " + isSorted());
System.out.println();
/* /
restoreValues();
betterBubble();
displayValues();
System.out.println("values is better bubble sorted: " + isSorted());
System.out.println();
/**/
restoreValues();
insertionSort();
displayValues();
System.out.println("values is insertion sorted: " + isSorted());
System.out.println();
restoreValues();
mergeSort(0,SIZE-1);
displayValues();
System.out.println("values is merge sorted: " + isSorted());
System.out.println();
restoreValues();
quickSort(0,SIZE-1);
displayValues();
System.out.println("values is quick sorted: " + isSorted());
System.out.println();
restoreValues();
heapSort();
displayValues();
System.out.println("values is heap sorted: " + isSorted());
System.out.println();
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help