Modify the authors\' Sorts.java so that when a sort is executed the number of sw
ID: 3831835 • Letter: M
Question
Modify the authors' Sorts.java so that when a sort is executed the number of swaps and compares is reported out. These counts must be provided for the authors' implementation of the following seven sorts:
provide proper comments.
selectionSort
bubbleSort
shortBubble
insertionSort
mergeSort
quickSort
heapSort
sorts.java
//----------------------------------------------------------------------------
// Sorts.java by Dale/Joyce/Weems Chapter 10
//
// Test harness used to run sorting algorithms.
//----------------------------------------------------------------------------
import java.util.*;
import java.text.DecimalFormat;
public class Sorts
{
static final int SIZE = 50; // size of array to be sorted
static int[] values = new int[SIZE]; // values to be sorted
static void initValues()
// Initializes the values array with random integers from 0 to 99.
{
Random rand = new Random();
for (int index = 0; index < SIZE; index++)
values[index] = Math.abs(rand.nextInt()) % 100;
}
static public boolean isSorted()
// Returns true if the array values are sorted and false otherwise.
{
boolean sorted = true;
for (int index = 0; index < (SIZE - 1); index++)
if (values[index] > values[index + 1])
sorted = false;
return sorted;
}
static public void swap(int index1, int index2)
// Precondition: index1 and index2 are >= 0 and < SIZE.
//
// Swaps the integers at locations index1 and index2 of the values array.
{
int temp = values[index1];
values[index1] = values[index2];
values[index2] = temp;
}
static public void printValues()
// Prints all the values integers.
{
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();
}
/////////////////////////////////////////////////////////////////
//
// Selection Sort
static int minIndex(int startIndex, int endIndex)
// Returns the index of the smallest value in
// values[startIndex]..values[endIndex].
{
int indexOfMin = startIndex;
for (int index = startIndex + 1; index <= endIndex; index++)
if (values[index] < values[indexOfMin])
indexOfMin = index;
return indexOfMin;
}
static void selectionSort()
// Sorts the values array using the selection sort algorithm.
{
int endIndex = SIZE - 1;
for (int current = 0; current < endIndex; current++)
swap(current, minIndex(current, endIndex));
}
/////////////////////////////////////////////////////////////////
//
// Bubble Sort
static void bubbleUp(int startIndex, int endIndex)
// Switches adjacent pairs that are out of order
// between values[startIndex]..values[endIndex]
// beginning at values[endIndex].
{
for (int index = endIndex; index > startIndex; index--)
if (values[index] < values[index - 1])
swap(index, index - 1);
}
static void bubbleSort()
// Sorts the values array using the bubble sort algorithm.
{
int current = 0;
while (current < (SIZE - 1))
{
bubbleUp(current, SIZE - 1);
current++;
}
}
/////////////////////////////////////////////////////////////////
//
// Short Bubble Sort
static boolean bubbleUp2(int startIndex, int endIndex)
// Switches adjacent pairs that are out of order
// between values[startIndex]..values[endIndex]
// beginning at values[endIndex].
//
// Returns false if a swap was made; otherwise, returns true.
{
boolean sorted = true;
for (int index = endIndex; index > startIndex; index--)
if (values[index] < values[index - 1])
{
swap(index, index - 1);
sorted = false;
}
return sorted;
}
static void shortBubble()
// Sorts the values array using the bubble sort algorithm.
// The process stops as soon as values is sorted.
{
int current = 0;
boolean sorted = false;
while ((current < (SIZE - 1)) && !sorted)
{
sorted = bubbleUp2(current, SIZE - 1);
current++;
}
}
/////////////////////////////////////////////////////////////////
//
// Insertion Sort
static void insertItem(int startIndex, int endIndex)
// Upon completion, values[0]..values[endIndex] are sorted.
{
boolean finished = false;
int current = endIndex;
boolean moreToSearch = true;
while (moreToSearch && !finished)
{
if (values[current] < values[current - 1])
{
swap(current, current - 1);
current--;
moreToSearch = (current != startIndex);
}
else
finished = true;
}
}
static void insertionSort()
// Sorts the values array using the insertion sort algorithm.
{
for (int count = 1; count < SIZE; count++)
insertItem(0, count);
}
/////////////////////////////////////////////////////////////////
//
// 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))
{
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.
{
tempArray[index] = values[leftFirst];
leftFirst++;
index++;
}
while (rightFirst <= rightLast)
// Copy remaining items from right half.
{
tempArray[index] = values[rightFirst];
rightFirst++;
index++;
}
for (index = saveFirst; index <= rightLast; index++)
values[index] = tempArray[index];
}
static void mergeSort(int first, int last)
// Sorts the values array using the merge sort algorithm.
{
if (first < last)
{
int middle = (first + last) / 2;
mergeSort(first, middle);
mergeSort(middle + 1, last);
merge(first, middle, middle + 1, last);
}
}
/////////////////////////////////////////////////////////////////
//
// 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 this returns 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;
}
static void reheapDown(int item, int root, int lastIndex)
// Precondition: Current root position is "empty".
//
// Inserts item into the tree and ensures shape and order properties.
{
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()
// Sorts the values array using the heap sort algorithm.
{
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)
{
initValues();
printValues();
System.out.println("values is sorted: " + isSorted());
System.out.println();
// make call to sorting method here (just remove //)
// selectionSort();
// bubbleSort();
// shortBubble();
// insertionSort();
// mergeSort(0, SIZE - 1);
// quickSort(0, SIZE - 1);
// heapSort();
printValues();
System.out.println("values is sorted: " + isSorted());
System.out.println();
}
}
Explanation / Answer
Please find my implementation.
//----------------------------------------------------------------------------
//Sorts.java by Dale/Joyce/Weems Chapter 10
//
//Test harness used to run sorting algorithms.
//----------------------------------------------------------------------------
import java.util.*;
import java.text.DecimalFormat;
public class Sorts
{
static final int SIZE = 50; // size of array to be sorted
static int[] values = new int[SIZE]; // values to be sorted
static int swap = 0;
static int comparison = 0;
static void initValues()
// Initializes the values array with random integers from 0 to 99.
{
Random rand = new Random();
for (int index = 0; index < SIZE; index++)
values[index] = Math.abs(rand.nextInt()) % 100;
}
static public boolean isSorted()
// Returns true if the array values are sorted and false otherwise.
{
boolean sorted = true;
for (int index = 0; index < (SIZE - 1); index++)
if (values[index] > values[index + 1])
sorted = false;
return sorted;
}
static public void swap(int index1, int index2)
// Precondition: index1 and index2 are >= 0 and < SIZE.
//
// Swaps the integers at locations index1 and index2 of the values array.
{
swap++;
int temp = values[index1];
values[index1] = values[index2];
values[index2] = temp;
}
static public void printValues()
// Prints all the values integers.
{
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();
}
/////////////////////////////////////////////////////////////////
//
// Selection Sort
static int minIndex(int startIndex, int endIndex)
// Returns the index of the smallest value in
// values[startIndex]..values[endIndex].
{
int indexOfMin = startIndex;
for (int index = startIndex + 1; index <= endIndex; index++){
comparison++;
if (values[index] < values[indexOfMin])
indexOfMin = index;
}
return indexOfMin;
}
static void selectionSort()
// Sorts the values array using the selection sort algorithm.
{
int endIndex = SIZE - 1;
for (int current = 0; current < endIndex; current++)
swap(current, minIndex(current, endIndex));
}
/////////////////////////////////////////////////////////////////
//
// Bubble Sort
static void bubbleUp(int startIndex, int endIndex)
// Switches adjacent pairs that are out of order
// between values[startIndex]..values[endIndex]
// beginning at values[endIndex].
{
for (int index = endIndex; index > startIndex; index--){
comparison++;
if (values[index] < values[index - 1])
swap(index, index - 1);
}
}
static void bubbleSort()
// Sorts the values array using the bubble sort algorithm.
{
int current = 0;
while (current < (SIZE - 1))
{
bubbleUp(current, SIZE - 1);
current++;
}
}
/////////////////////////////////////////////////////////////////
//
// Short Bubble Sort
static boolean bubbleUp2(int startIndex, int endIndex)
// Switches adjacent pairs that are out of order
// between values[startIndex]..values[endIndex]
// beginning at values[endIndex].
//
// Returns false if a swap was made; otherwise, returns true.
{
boolean sorted = true;
for (int index = endIndex; index > startIndex; index--){
comparison++;
if (values[index] < values[index - 1])
{
swap(index, index - 1);
sorted = false;
}
}
return sorted;
}
static void shortBubble()
// Sorts the values array using the bubble sort algorithm.
// The process stops as soon as values is sorted.
{
int current = 0;
boolean sorted = false;
while ((current < (SIZE - 1)) && !sorted)
{
sorted = bubbleUp2(current, SIZE - 1);
current++;
}
}
/////////////////////////////////////////////////////////////////
//
// Insertion Sort
static void insertItem(int startIndex, int endIndex)
// Upon completion, values[0]..values[endIndex] are sorted.
{
boolean finished = false;
int current = endIndex;
boolean moreToSearch = true;
while (moreToSearch && !finished)
{
comparison++;
if (values[current] < values[current - 1])
{
swap(current, current - 1);
current--;
moreToSearch = (current != startIndex);
}
else
finished = true;
}
}
static void insertionSort()
// Sorts the values array using the insertion sort algorithm.
{
for (int count = 1; count < SIZE; count++)
insertItem(0, count);
}
/////////////////////////////////////////////////////////////////
//
// 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))
{
comparison++;
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.
{
tempArray[index] = values[leftFirst];
leftFirst++;
index++;
}
while (rightFirst <= rightLast)
// Copy remaining items from right half.
{
tempArray[index] = values[rightFirst];
rightFirst++;
index++;
}
for (index = saveFirst; index <= rightLast; index++)
values[index] = tempArray[index];
}
static void mergeSort(int first, int last)
// Sorts the values array using the merge sort algorithm.
{
comparison++;
if (first < last)
{
int middle = (first + last) / 2;
mergeSort(first, middle);
mergeSort(middle + 1, last);
merge(first, middle, middle + 1, last);
}
}
/////////////////////////////////////////////////////////////////
//
// Quick Sort
static int split(int first, int last)
{
int splitVal = values[first];
int saveF = first;
boolean onCorrectSide;
first++;
do
{
>
while (onCorrectSide){ // move first toward last
comparison++;
if (values[first] > splitVal)
>
else
{
first++;
<= last);
}
}
<= last);
while (onCorrectSide) { // move last toward first
comparison++;
if (values[last] <= splitVal)
>
else
{
last--;
<= last);
}
}
comparison++;
if (first < last)
{
swap(first, last);
first++;
last--;
}
} while (first <= last);
swap(saveF, last);
return last;
}
static void quickSort(int first, int last)
{
comparison++;
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 this returns the index
// of the larger child; otherwise it returns the index of hole.
{
int left = (hole * 2) + 1;
int right = (hole * 2) + 2;
comparison++;
if (left > lastIndex)
// hole has no children
return hole;
else{
comparison++;
if (left == lastIndex){
comparison++;
// hole has left child only
if (item < values[left])
// item < left child
return left;
else
// item >= left child
return hole;
}
else{
comparison++;
// hole has two children
if (values[left] < values[right]){
comparison++;
// left child < right child
if (values[right] <= item)
// right child <= item
return hole;
else
// item < right child
return right;
}
else{
comparison++;
// left child >= right child
if (values[left] <= item)
// left child <= item
return hole;
else
// item < left child
return left;
}
}
}
}
static void reheapDown(int item, int root, int lastIndex)
// Precondition: Current root position is "empty".
//
// Inserts item into the tree and ensures shape and order properties.
{
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()
// Sorts the values array using the heap sort algorithm.
{
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)
{
initValues();
printValues();
System.out.println("values is sorted: " + isSorted());
System.out.println();
// make call to sorting method here (just remove //)
Sorts.comparison = 0;
Sorts.swap = 0;
selectionSort();
System.out.println("Number of comparisons: "+Sorts.comparison);
System.out.println("Number of swaps: "+Sorts.swap);
// reseting to zero
Sorts.comparison = 0;
Sorts.swap = 0;
// bubbleSort();
// shortBubble();
// insertionSort();
// mergeSort(0, SIZE - 1);
// quickSort(0, SIZE - 1);
// heapSort();
printValues();
System.out.println("values is sorted: " + isSorted());
System.out.println();
}
}
/*
Sample run:
The values array is:
20 38 95 71 18 29 57 80 97 87
15 38 64 81 69 19 17 31 81 18
03 74 37 87 52 27 56 53 33 65
23 22 87 46 55 69 70 56 32 29
49 64 82 35 17 96 74 38 92 65
values is sorted: false
Number of comparisons: 1225
Number of swaps: 49
The values array is:
03 15 17 17 18 18 19 20 22 23
27 29 29 31 32 33 35 37 38 38
38 46 49 52 53 55 56 56 57 64
64 65 65 69 69 70 71 74 74 80
81 81 82 87 87 87 92 95 96 97
values is sorted: true
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.