this like the thired time posting this question and i haven\'t get an answer. Pl
ID: 3681915 • Letter: T
Question
this like the thired time posting this question and i haven't get an answer.
Please help, This is in java and please show each steps. it would be nice if you could put the number for the steps.
Directed Lab Work
The basic sorts have already been implemented in the SortArray class. You will make a new class
SortArrayInstrumented that will be based on that class. It will allow you to gather statistics about the
sorts. The SortDriver class will generate the arrays, call the sorts, and then display the statistical results.
Adding Statistics to Selection Sort
Step 1. If you have not done so, look at the implementation of the sorts in SortArray.java. Look at
the skeleton in SortDriver.java. Compile the classes SortArray, and SortDriver. Run the main method
in SortDriver.
Checkpoint: The program will ask you for an array size. Enter 20. An array of 20 random values between 0
and 20 should be generated and displayed. Selection sort will be applied to array and the sorted array will be
displayed. Verify that this works correctly.
The first goal is to create a new class SortArrayInstrumented that will be used to collect statistics about the
performance of the sorts. Private variables of the class will be used to record the number of comparisons
made.
Step 2. Create a new class name SortArrayInstrumented.
Step 3. Copy the contents of SortArray into SortArrayInstrumented. Change the name in the class
declaration from SortArray to SortArrayInstrumented.
Step 4. Create a default constructor that does nothing. (It will have work to do later.)
Step 5. Remove static from all the methods in the SortArrayInstrumented class.
Checkpoint: You should be able to compile SortArrayInstrumented without errors.
Since the sort methods are no longer static, SortDriver must be changed to create an instance of
SortArrayInstrumented and then invoke the sort method using the instance.
Step 6. In main of sortDriver declare and create a new instance of SortArrayInstrumented named
sai.
Step 7. Change SortArray.selectionSort(data, arraySize) to sai.selectionSort(data,
arraySize).
Checkpoint: Compile and run the program. Enter 20 for the array size. Verify that this works correctly.
The next goal is to add code to the selection sort to count the number of times that a comparison of data values
is made. Methods will be added to the SortArrayInstrumented class to allow the number of comparisons to be
recovered.
Step 8. Add a private variable comparisons of type long to the SortArrayInstrumented class.
Initialize it to zero in the constructor.
Step 9. Add a public accessor method getComparisons to the SortArrayInstrumented class.
Step 10. In order to count the number of times that compareTo() is called by selection sort, put the line
comparisons++;
just before the if statement in indexOfSmallest(). If the code is inserted inside the then clause, only the
comparisons that result in true will be counted.
Step 11. In SortDriver, add the line
System.out.println(" comparison made: "+sai.getComparisons());
after the call to selection sort.
Checkpoint: Compile and run the program. Enter 20 for the array size. Verify that the sort still works
correctly. The number of comparisons should be 190.
The next goal is to compute the average number of comparisons made by the sort with many different arrays
(all of the same size). Only SortDriver will be changed.
Step 12. In SortDriver, use the method getInt() to set the variable trials.
Step 13. Starting with the call to generateRandomArray, wrap the remainder of the code in main in
SortDriver with a for loop that runs the given number of trials.
Checkpoint: Compile and run the program. Enter 20 for the array size. Enter 3 for the number of trials. Verify
that each of the three trials sorted the values correctly and is for a different array of 20 values. The number of
comparisons should be 190, 380, and 570.
Notice that the number of comparisons gives a running total for all calls. The next goal is to compute and
report the minimum and maximum number of comparisons made over all the calls to the sort. To do this, the
use of the comparisons variable will be changed slightly. It will only be the number of comparisons made by
the last call to the sort. The total number of comparisons made by all calls will be held in a new variable. This
aids in the computation of the maximum and minimum.
Step 14. Add a private variable totalComparisons of type long to the SortArrayInstrumented
class. Initialize it to zero in the constructor.
Step 15. Add a private variable minComparisons of type long to the SortArrayInstrumented class.
Initialize it to Long.MAX_VALUE in the constructor.
Step 16. Add a private variable maxComparisons of type long to the SortArrayInstrumented class.
Initialize it to zero in the constructor.
Step 17. Add three public accessor methods (one for each of the new variables) to the
SortArrayInstrumented class.
To compute the minimum and maximum number of comparisons, code needs to be added at the beginning and
end of the sort. While the needed code could be added directly to the sorts, it is better to encapsulate it in a
couple new methods.
Step 18. Add a private method startStatistics() to the SortArrayInstrumented class. It should
initialize comparisons to zero.
Step 19. Add a private method endStatistics() to the SortArrayInstrumented class. It should add
comparisons to totalComparisons. It should compare comparisons to minComparisons and set
minComparisons to whichever is smaller. It should also set maxComparisons in an analogous fashion.
Step 20. Call startStatistics() at the beginning of the selectionSort method. Call
endStatistics() at the end of the selectionSort method.
Step 21. After the for loop in main of SortDriver, add in three statements that print the total, minimum,
and maximum number of comparisons.
Checkpoint: Compile and run the program. Enter 20 for the array size. Enter 3 for the number of trials. Verify
that each of the three trials sorted the values correctly and is for a different array of 20 values. The number of
comparisons should be 190 for each of the three trials. The total should be 570 and the minimum and maximum
should both be 190. Refer to the pre-lab exercises and compare.
Enter 10 for the array size. Enter 3 for the number of trials. Verify that each of the three trials sorted the values
correctly and is for a different array of 10 values. The number of comparisons should be 45 for each of the
three calls. The total should be 135 and the minimum and maximum should both be 45.
Step 22. Compute the average number of comparisons made over the trials and print it. (The average is the
total number of comparisons divided by the number of trials.)
Step 23. In preparation for filling in the table, comment out the print statements inside the for loop in
main.
Final checkpoint: Compile and run the program. Enter 20 for the array size. Enter 1000 for the number of
trials. The total should be 19000 and the average, minimum, and maximum should all be 190.
Step 24. Fill in this table and record the average in the appropriate column in the table at the end of the
directed lab. Use 100 trials.
Comparisons for Selection Sort
MINIMUM
COMPARISONS
AVERAGE
COMPARISONS
MAXIMUM
COMPARISONS
Adding Statistics to Recursive Insertion Sort
Most of the work needed has been done before. It is now just a matter of adding the appropriate code to the
insertion sort code.
Step 25. Add calls to startStatistics() and endStatistics() to the public, nonrecursive
insertionSort() method.
Step 26. In the insertInOrder() method place code to add one to comparisons when compareTo() is
invoked.
Step 27. In main in SortDriver, change the call from selectionSort to insertionSort.
Step 28. Uncomment the print statements in the for loop in main in SortDriver.
Checkpoint: Compile and run the program. Enter 20 for the array size. Enter 3 for the number of trials. Verify
that each of the three trials sorted the values correctly and is for a different array of 20 values. The number of
comparisons should typically be in the range of 85 to 130 for each of the three with an average of
approximately 107[3]. If you get values that are outside this range, retry the test a few times. If you consistently
get results outside the range, check the code you added for errors. Verify that the total, minimum, and maximum
are correct for the reported number of comparisons.
Enter 10 for the array size. Enter 3 for the number of trials. Verify that each of the three trials sorted the values
correctly and is for a different array of 10 values. The number of comparisons should be approximately 28 for
each of the three trials. Verify that the total, minimum, and maximum are correct for the reported number of
comparisons.
Step 29. Recomment the print statements from the previous step.
Final checkpoint: Compile and run the program. Enter 20 for the array size. Enter 10000 for the number of
trials. The average should be approximately 107.
Step 30. Fill in this table and record the average in the appropriate column in the table at the end of the
directed lab. Use 100 trials.
Warning: Depending on the computer you are using, there may be a limit on the number of recursive calls that
can be made. If this happens you will get the error java.lang.StackOverflowError. While this often indicates
that you have entered an infinite recursion, as long as the sort worked for a smaller array, that is not the case
here. If we examine the pattern of calls, we see that we need to make one recursive call for each entry in the
array. As you apply the algorithm to larger and larger arrays, the size of the stack must be larger and we can
hit the upper limit. If this happens, find the limit and mark it on the table.
Comparisons for Insertion Sort
MINIMUM
COMPARISONS
AVERAGE
COMPARISONS
MAXIMUM
COMPARISONS
Adding Statistics to Shell Sort
Step 1. Add calls to startStatistics() and endStatistics() to the public shellSort() method.
Step 2. In the incrementalInsertionSort() method place code to add one to comparisons when
compareTo() is invoked. Since the comparison is in the condition of a while loop, this is a bit trickier to
handle for than with the other two sorts. Certainly the compareTo method was invoked once for each time the
body of the loop executed. CompareTo will have been invoked one more time if the first clause in the condition
( index first) was true and the result of the compareTo method caused the loop to finish. Make sure you
count both possibilities.
Step 3. In main in SortDriver, change the call from insertionSort to shellSort.
Step 4. Uncomment the print statements in the for loop in main in SortDriver.
Checkpoint: Compile and run the program. Enter 20 for the array size. Enter 3 for the number of trials. Verify
that each of the three trials sorted the values correctly and is for a different array of 20 values. The number of
comparisons should typically be in the range of 73 to 94 for each of the three with an average of approximately
85[4]. Verify that the total, minimum, and maximum are correct for the reported number of comparisons.
Enter 10 for the array size. Enter 3 for the number of trials. Verify that each of the three trials sorted the values
correctly and is for a different array of 10 values. The number of comparisons should be approximately 28 for
each of the three trials. Verify that the total, minimum, and maximum are correct for the reported number of
comparisons.
Step 5. Recomment the print statements from the previous step.
Final checkpoint: Compile and run the program. Enter 20 for the array size. Enter 10000 for the number of
trials. The average should be approximately 85.
Step 6. Fill in this table and record the average in the appropriate column in the table below.
Comparisons for Shell Sort
MINIMUM
COMPARISONS
AVERAGE
COMPARISONS
MAXIMUM
COMPARISONS
Size=10
Size=50
Size=100
Size=200
Size=300
Size=400
Size=500
Size=750
Size=1000
Average Comparisons for All Three Sorts
SELECTION
SORT
INSERTION
SORT
SHELL
SORT
Size=10
Size=50
Size=100
Size=200
Size=300
Size=400
Size=500
Size=750
Size=1000
Here is SortArray class
/********************************************************************
* Class for sorting an array of Comparable objects from smallest to
* largest.
*
* This code is from Chapter 8 of
* Data Structures and Abstractions with Java 4/e
* by Carrano
*
********************************************************************/
public class SortArray
{
/**************************************************************
* ITERATIVE SELECTION SORT
**************************************************************/
/** Sorts the first n objects in an array into ascending order.
* @param a An array of Comparable objects.
* @param n An integer > 0.
*/
public static <T extends Comparable<? super T>> void selectionSort(T[] a, int n)
{
for (int index = 0; index < n - 1; index++)
{
int indexOfNextSmallest = getIndexOfSmallest(a, index, n - 1);
swap(a, index, indexOfNextSmallest);
// Assertion: a[0] <= a[1] <= . . . <= a[index] <= all other a[unsorted]
} // end for
} // end selectionSort
/** Finds the index of the smallest value in an array a.
* @param a An array of Comparable objects.
* @param first An integer >= 0 and < a.length that is the index of the first
* array entry to consider.
* @param last An integer >= 0 and < a.length that is the index of the last
* array entry to consider.
* @return The index of the smallest value among
* a[first], a[first+1], . . . , a[last].
*/
public static <T extends Comparable<? super T>>
int getIndexOfSmallest(T[] a, int first, int last)
{
T min = a[first];
int indexOfMin = first;
for (int index = first + 1; index <= last; index++)
{
if (a[index].compareTo(min) < 0)
{
min = a[index];
indexOfMin = index;
} // end if
// Assertion: min is the smallest of a[first] through a[index].
} // end for
return indexOfMin;
} // end getIndexOfSmallest
/** Swaps the array entries a[i] and a[j].
* @param a An array of objects.
* @param i An integer >= 0 and < a.length.
* @param j An integer >= 0 and < a.length.
*
* Modified from Carrano to use generics.
*/
private static <T> void swap(T[] a, int i, int j)
{
T temp = a[i];
a[i] = a[j];
a[j] = temp;
} // end swap
/**************************************************************
* RECURSIVE INSERTION SORT WITH A RECURSIVE INSERT
**************************************************************/
/** Sorts the first n objects in an array into ascending order.
* @param a An array of Comparable objects.
* @param n An integer > 0.
*/
public static <T extends Comparable<? super T>> void insertionSort(T[] a, int n)
{
insertionSort(a, 0, n-1);
} // end insertionSort
/** Recursively sorts the objects in a range of locations in
* an array into ascending order.
* @param a An array of Comparable objects.
* @param first An integer > 0 and < a.length.
* @param last An integer > first and< a.length.
*/
private static <T extends Comparable<? super T>>
void insertionSort(T[] a, int first, int last)
{
if (first < last)
{
// Sort all but the last entry
insertionSort(a, first, last-1);
// Insert the last entry in sorted order
insertInOrder(a[last], a, first, last-1);
} // end if
} // end insertionSort
/** Recursively insert a value into its correct location
* @param entry The item to insert.
* @param a An array of Comparable objects.
* @param begin An integer >= 0 that is the index of the first
* array entry to consider.
* @param end An integer >= 0 that is the index of the last
* array entry to consider.
*/
public static <T extends Comparable<? super T>>
void insertInOrder(T anEntry, T[] a, int begin, int end)
{
// Inserts entry into the sorted array entrys a[first] through a[last].
if (anEntry.compareTo(a[end]) >= 0)
a[end+1] = anEntry;
else if (begin < end)
{
a[end+1] = a[end];
insertInOrder(anEntry, a, begin, end-1);
}
else // begin == end and enEntry < a[end]
{
a[end+1] = a[end];
a[end] = anEntry;
}
} // end insertInOrder
/**************************************************************
* ITERATIVE INSERTION SORT (PROVIDED FOR REFERNCE)
**************************************************************/
/** Sorts the first n objects in an array into ascending order.
* @param a An array of Comparable objects.
* @param n An integer > 0.
*/
/* Provided for reference. Modify the recursive insertion sort
* for the lab.
*
public static <T extends Comparable<? super T>> void insertionSort(T[] a, int n)
{
insertionSort(a, 0, n - 1);
} // end insertionSort
*/
/** Iterative insertion sort of the objects in a range of locations in
* an array into ascending order.
* @param a An array of Comparable objects.
* @param first An integer >= 0 and < a.length.
* @param last An integer > first and< a.length.
*/
/* Provided for reference. Modify the recursive insertion sort
* for the lab.
*
public static <T extends Comparable<? super T>>
void insertionSort(T[] a, int first, int last)
{
T nextToInsert;
boolean foundLocation;
int loc;
for (int unsorted = first + 1; unsorted <= last; unsorted++)
{
nextToInsert = a[unsorted];
insertInOrder(nextToInsert, a, first, unsorted - 1);
} // end for
} // end insertionSort
*/
/** Inserts anEntry into the sorted entries a[begin] through a[end].
* @param anEntry The entry to be inserted into the sorted portion of the array.
* @param a An array of Comparable objects.
* @param begin An integer >= 0 and < a.length.
* @param end An integer > first and< a.length.
*/
/* Provided for reference. Modify the recursive insertion sort
* for the lab.
*
public static <T extends Comparable<? super T>>
void insertInOrder(T anEntry, T[] a, int begin, int end)
{
int index = end; // index of last entry in the sorted portion
// Make room, if needed, in sorted portion for another entry
while ((index >= begin) && (anEntry.compareTo(a[index])) < 1)
{
a[index + 1] = a[index]; // make room
index--;
} // end while
// Assertion: a[index + 1] is available.
a[index + 1] = anEntry; // insert
} // end insertionSort
*/
/**************************************************************
* ITERATIVE SHELL SORT
**************************************************************/
/** Sorts the first n objects in an array into ascending order.
* @param a An array of Comparable objects.
* @param n An integer > 0.
*/
public static <T extends Comparable<? super T>> void shellSort(T[] a, int n)
{
shellSort(a, 0, n - 1);
} // end shellSort
/** Use incremental insertion sort with different increments to
* sort a range of values in the array.
* @param a An array of Comparable objects.
* @param first An integer >= 0.
* @param last An integer > first and< a.length.
*/
public static <T extends Comparable<? super T>>
void shellSort(T[] a, int first, int last)
{
int n = last - first + 1; // number of array entries
int space = n/2;
while (space > 0)
{
for (int begin = first; begin < first + space; begin++)
{
incrementalInsertionSort(a, begin, last, space);
}
space = space/2;
} // end while
} // end shellSort
/** Sorts equally spaced entries of an array into ascending order.
@param a An array of Comparable objects.
@param first The integer index of the first array entry to
consider; first >= 0 and < a.length.
@param last The integer index of the last array entry to
consider; last >= first and < a.length.
@param space the difference between the indices of the
entries to sort.
*/
public static <T extends Comparable<? super T>>
void incrementalInsertionSort(T[] a, int first, int last, int space)
{
int unsorted, index;
for (unsorted = first + space;
unsorted <= last;
unsorted = unsorted + space)
{
T nextToInsert = a[unsorted];
index = unsorted - space;
while ((index >= first) && (nextToInsert.compareTo(a[index]) < 0))
{
a[index + space] = a[index];
index = index - space;
} // end while
a[index + space] = nextToInsert;
} // end for
} // end incrementalInsertionSort
}// end SortArray
/
/
/
/
/
/
Here is SortDriver class
import java.util.*;
import java.io.*;
/**
* A class for generating statistical information about the basis sort performance.
*
* @author Charles Hoot
* @version 4.0
*/
public class SortDriver
{
public static void main(String args[])
{
int arraySize;
int trials;
Integer data[];
//CREATE THE INSTANCE OF THE INSTRUMENTED SORT CLASS HERE
System.out.println("What size arrays should be used?");
arraySize = getInt(" It should be an integer value greater than or equal to 1.");
// MODIFY THE FOLLOWING TO GET THE NUMBER OF TRIALS AND LOOP
data = generateRandomArray(arraySize);
System.out.println("The array is: " + getString(data));
SortArray.selectionSort(data, arraySize);
System.out.println("The sorted array is: " + getString(data));
// ADD CODE TO REPORT THE NUMBER OF COMPARISONS
}
/**
* Generate an array of random integer values. The values will be between 0 and size.
*
* @param size The size of the array to generate.
* @return The array of integers.
*/
private static Integer[] generateRandomArray(int size)
{
Integer result[] = new Integer[size];
Random generator = new Random();
for(int i = 0; i< size; i++)
{
int value = generator.nextInt(size);
result[i] = new Integer(value);
}
return result;
}
/**
* A displayable representation of an array of Objects where toString is
* applied on each object in the array
*
* @param data The array to display.
* @return A printable string.
*/
private static String getString(Object [] data)
{
String result = new String("[ ");
for(int i = 0; i< data.length; i++)
{
result = result + data[i].toString() + " ";
}
result = result + "]";
return result;
}
/**
* Get an integer value
*
* @return An integer.
*/
private static int getInt(String rangePrompt)
{
Scanner input;
int result = 10; //default value is 10
try
{
input = new Scanner(System.in);
System.out.println(rangePrompt);
result = input.nextInt();
}
catch(NumberFormatException e)
{
System.out.println("Could not convert input to an integer");
System.out.println(e.getMessage());
System.out.println("Will use 10 as the default value");
}
catch(Exception e)
{
System.out.println("There was an error with System.in");
System.out.println(e.getMessage());
System.out.println("Will use 10 as the default value");
}
return result;
}
}
MINIMUM
COMPARISONS
AVERAGE
COMPARISONS
MAXIMUM
COMPARISONS
Size=10 Size=50 Size=100 Size=200 Size=300 Size=400 Size=500 Size=750 Size=1000Explanation / Answer
SortDriver.java
import java.util.*;
import java.io.*;
public class SortDriver
{
public static void main(String args[])
{
int arraySize;
int trials;
Integer data[];
//CREATE THE INSTANCE OF THE INSTRUMENTED SORT CLASS HERE
SortArrayInstrumented sai = new SortArrayInstrumented();
System.out.println("What size arrays should be used?");
arraySize = getInt(" It should be an integer value greater than or equal to 1.");
// MODIFY THE FOLLOWING TO GET THE NUMBER OF TRIALS AND LOOP
trials = getInt("How many trials?");
for (int i = 0; i < trials; i++) {
data = generateRandomArray(arraySize);
System.out.println("The array is: " + getString(data));
sai.shellSort(data, arraySize);
System.out.println("The sorted array is: " + getString(data));
}
// ADD CODE TO REPORT THE NUMBER OF COMPARISONS
System.out.println(" Comparison made: "+sai.getComparisons());
System.out.println(" Total: "+sai.getTotalComparisons());
System.out.println(" Min: "+sai.getMinComparisons());
long avg = (sai.getTotalComparisons())/trials;
System.out.println(" Avg: "+avg);
System.out.println(" Max: "+sai.getMaxComparisons());
}
/**
* Generate an array of random integer values. The values will be between 0 and size.
*
* @param size The size of the array to generate.
* @return The array of integers.
*/
private static Integer[] generateRandomArray(int size)
{
Integer result[] = new Integer[size];
Random generator = new Random();
for(int i = 0; i< size; i++)
{
int value = generator.nextInt(size);
result[i] = new Integer(value);
}
return result;
}
/**
* A displayable representation of an array of Objects where toString is
* applied on each object in the array
*
* @param data The array to display.
* @return A printable string.
*/
private static String getString(Object [] data)
{
String result = new String("[ ");
for(int i = 0; i< data.length; i++)
{
result = result + data[i].toString() + " ";
}
result = result + "]";
return result;
}
/**
* Get an integer value
*
* @return An integer.
*/
private static int getInt(String rangePrompt)
{
Scanner input;
int result = 10; //default value is 10
try
{
input = new Scanner(System.in);
System.out.println(rangePrompt);
result = input.nextInt();
}
catch(NumberFormatException e)
{
System.out.println("Could not convert input to an integer");
System.out.println(e.getMessage());
System.out.println("Will use 10 as the default value");
}
catch(Exception e)
{
System.out.println("There was an error with System.in");
System.out.println(e.getMessage());
System.out.println("Will use 10 as the default value");
}
return result;
}
}
SortArray.java
/********************************************************************
* Class for sorting an array of Comparable objects from smallest to
* largest.
*
* This code is from Chapter 8 of
* Data Structures and Abstractions with Java 4/e
* by Carrano
*
********************************************************************/
public class SortArray {
/**************************************************************
* ITERATIVE SELECTION SORT
**************************************************************/
/** Sorts the first n objects in an array into ascending order.
* @param a An array of Comparable objects.
* @param n An integer > 0.
*/
public static <T extends Comparable<? super T>>
void selectionSort(T[] a, int n) {
for (int index = 0; index < n - 1; index++) {
int indexOfNextSmallest = getIndexOfSmallest(a, index, n - 1);
swap(a, index, indexOfNextSmallest);
// Assertion: a[0] <= a[1] <= . . . <= a[index] <= all other a[unsorted]
} // end for
} // end selectionSort
/** Finds the index of the smallest value in an array a.
* @param a An array of Comparable objects.
* @param first An integer >= 0 and < a.length that is the index of the first
* array entry to consider.
* @param last An integer >= 0 and < a.length that is the index of the last
* array entry to consider.
* @return The index of the smallest value among
* a[first], a[first+1], . . . , a[last].
*/
public static <T extends Comparable<? super T>>
int getIndexOfSmallest(T[] a, int first, int last) {
T min = a[first];
int indexOfMin = first;
for (int index = first + 1; index <= last; index++) {
if (a[index].compareTo(min) < 0) {
min = a[index];
indexOfMin = index;
} // end if
// Assertion: min is the smallest of a[first] through a[index].
} // end for
return indexOfMin;
} // end getIndexOfSmallest
/** Swaps the array entries a[i] and a[j].
* @param a An array of objects.
* @param i An integer >= 0 and < a.length.
* @param j An integer >= 0 and < a.length.
*
* Modified from Carrano to use generics.
*/
private static <T>
void swap(T[] a, int i, int j) {
T temp = a[i];
a[i] = a[j];
a[j] = temp;
} // end swap
/**************************************************************
* RECURSIVE INSERTION SORT WITH A RECURSIVE INSERT
**************************************************************/
/** Sorts the first n objects in an array into ascending order.
* @param a An array of Comparable objects.
* @param n An integer > 0.
*/
public static <T extends Comparable<? super T>>
void insertionSort(T[] a, int n)
{
insertionSort(a, 0, n-1);
} // end insertionSort
/** Recursively sorts the objects in a range of locations in an array into ascending order.
* @param a An array of Comparable objects.
* @param first An integer > 0 and < a.length.
* @param last An integer > first and < a.length.
*/
private static <T extends Comparable<? super T>>
void insertionSort(T[] a, int first, int last)
{
if (first < last)
{
// Sort all but the last entry
insertionSort(a, first, last-1);
// Insert the last entry in sorted order
insertInOrder(a[last], a, first, last-1);
} // end if
} // end insertionSort
/** Recursively insert a value into its correct location
* @param entry The item to insert.
* @param a An array of Comparable objects.
* @param begin An integer >= 0 that is the index of the first
* array entry to consider.
* @param end An integer >= 0 that is the index of the last
* array entry to consider.
*/
public static <T extends Comparable<? super T>>
void insertInOrder(T anEntry, T[] a, int begin, int end)
{
// Inserts entry into the sorted array entrys a[first] through a[last].
if (anEntry.compareTo(a[end]) >= 0)
a[end+1] = anEntry;
else if (begin < end)
{
a[end+1] = a[end];
insertInOrder(anEntry, a, begin, end-1);
}
else // begin == end and enEntry < a[end]
{
a[end+1] = a[end];
a[end] = anEntry;
}
} // end insertInOrder
/**************************************************************
* ITERATIVE INSERTION SORT (PROVIDED FOR REFERNCE)
**************************************************************/
/** Sorts the first n objects in an array into ascending order.
* @param a An array of Comparable objects.
* @param n An integer > 0.
*/
/* Provided for reference. Modify the recursive insertion sort
* for the lab.
*
public static <T extends Comparable<? super T>>
void insertionSort(T[] a, int n) {
insertionSort(a, 0, n - 1);
} // end insertionSort
*/
/** Iterative insertion sort of the objects in a range of locations in an array into ascending order.
* @param a An array of Comparable objects.
* @param first An integer >= 0 and < a.length.
* @param last An integer > first and < a.length.
*/
/* Provided for reference. Modify the recursive insertion sort
* for the lab.
*
public static <T extends Comparable<? super T>>
void insertionSort(T[] a, int first, int last) {
T nextToInsert;
boolean foundLocation;
int loc;
for (int unsorted = first + 1; unsorted <= last; unsorted++) {
nextToInsert = a[unsorted];
insertInOrder(nextToInsert, a, first, unsorted - 1);
} // end for
} // end insertionSort
*/
/** Inserts anEntry into the sorted entries a[begin] through a[end].
* @param anEntry The entry to be inserted into the sorted portion of the array.
* @param a An array of Comparable objects.
* @param begin An integer >= 0 and < a.length.
* @param end An integer > first and < a.length.
*/
/* Provided for reference. Modify the recursive insertion sort
* for the lab.
*
public static <T extends Comparable<? super T>>
void insertInOrder(T anEntry, T[] a, int begin, int end) {
int index = end; // index of last entry in the sorted portion
// Make room, if needed, in sorted portion for another entry
while ((index >= begin) && (anEntry.compareTo(a[index])) < 1) {
a[index + 1] = a[index]; // make room
index--;
} // end while
// Assertion: a[index + 1] is available.
a[index + 1] = anEntry; // insert
} // end insertionSort
*/
/**************************************************************
* ITERATIVE SHELL SORT
**************************************************************/
/** Sorts the first n objects in an array into ascending order.
* @param a An array of Comparable objects.
* @param n An integer > 0.
*/
public static <T extends Comparable<? super T>>
void shellSort(T[] a, int n) {
shellSort(a, 0, n - 1);
} // end shellSort
/** Use incremental insertion sort with different increments to
* sort a range of values in the array.
* @param a An array of Comparable objects.
* @param first An integer >= 0.
* @param last An integer > first and < a.length.
*/
public static <T extends Comparable<? super T>>
void shellSort(T[] a, int first, int last) {
int n = last - first + 1; // number of array entries
int space = n/2;
while (space > 0) {
for (int begin = first; begin < first + space; begin++) {
incrementalInsertionSort(a, begin, last, space);
}
space = space/2;
} // end while
} // end shellSort
/** Sorts equally spaced entries of an array into ascending order.
@param a An array of Comparable objects.
@param first The integer index of the first array entry to
consider; first >= 0 and < a.length.
@param last The integer index of the last array entry to
consider; last >= first and < a.length.
@param space the difference between the indices of the
entries to sort.
*/
public static <T extends Comparable<? super T>>
void incrementalInsertionSort(T[] a, int first, int last, int space) {
int unsorted, index;
for (unsorted = first + space; unsorted <= last;
unsorted = unsorted + space)
{
T nextToInsert = a[unsorted];
index = unsorted - space;
while ((index >= first) && (nextToInsert.compareTo(a[index]) < 0)){
a[index + space] = a[index];
index = index - space;
} // end while
a[index + space] = nextToInsert;
} // end for
} // end incrementalInsertionSort
}// end SortArray
SortArrayInstrumented.java
/********************************************************************
* Class for sorting an array of Comparable objects from smallest to
* largest.
*
* This code is from Chapter 8 of
* Data Structures and Abstractions with Java 4/e
* by Carrano
*
********************************************************************/
public class SortArrayInstrumented {
private long comparisons;
private long totalComparisons;
private long minComparisons;
private long maxComparisons;
public SortArrayInstrumented() {
comparisons = 0;
totalComparisons = 0;
minComparisons = Long.MAX_VALUE;
maxComparisons = 0;
}
public long getComparisons() {
return comparisons;
}
public long getTotalComparisons() {
return totalComparisons;
}
public long getMinComparisons() {
return minComparisons;
}
public long getMaxComparisons() {
return maxComparisons;
}
private void startStatistics() {
comparisons = 0;
}
private void endStatistics() {
totalComparisons += comparisons;
if (comparisons < minComparisons) {
minComparisons = comparisons;
}
if (comparisons > maxComparisons) {
maxComparisons = comparisons;
}
}
/**************************************************************
* ITERATIVE SELECTION SORT
**************************************************************/
/** Sorts the first n objects in an array into ascending order.
* @param a An array of Comparable objects.
* @param n An integer > 0.
*/
public <T extends Comparable<? super T>>
void selectionSort(T[] a, int n) {
startStatistics();
for (int index = 0; index < n - 1; index++) {
int indexOfNextSmallest = getIndexOfSmallest(a, index, n - 1);
swap(a, index, indexOfNextSmallest);
// Assertion: a[0] <= a[1] <= . . . <= a[index] <= all other a[unsorted]
} // end for
endStatistics();
} // end selectionSort
/** Finds the index of the smallest value in an array a.
* @param a An array of Comparable objects.
* @param first An integer >= 0 and < a.length that is the index of the first
* array entry to consider.
* @param last An integer >= 0 and < a.length that is the index of the last
* array entry to consider.
* @return The index of the smallest value among
* a[first], a[first+1], . . . , a[last].
*/
public <T extends Comparable<? super T>>
int getIndexOfSmallest(T[] a, int first, int last) {
T min = a[first];
int indexOfMin = first;
for (int index = first + 1; index <= last; index++) {
comparisons++;
if (a[index].compareTo(min) < 0) {
min = a[index];
indexOfMin = index;
} // end if
// Assertion: min is the smallest of a[first] through a[index].
} // end for
return indexOfMin;
} // end getIndexOfSmallest
/** Swaps the array entries a[i] and a[j].
* @param a An array of objects.
* @param i An integer >= 0 and < a.length.
* @param j An integer >= 0 and < a.length.
*
* Modified from Carrano to use generics.
*/
private <T>
void swap(T[] a, int i, int j) {
T temp = a[i];
a[i] = a[j];
a[j] = temp;
} // end swap
/**************************************************************
* RECURSIVE INSERTION SORT WITH A RECURSIVE INSERT
**************************************************************/
/** Sorts the first n objects in an array into ascending order.
* @param a An array of Comparable objects.
* @param n An integer > 0.
*/
public <T extends Comparable<? super T>>
void insertionSort(T[] a, int n)
{
startStatistics();
insertionSort(a, 0, n-1);
endStatistics();
} // end insertionSort
/** Recursively sorts the objects in a range of locations in an array into ascending order.
* @param a An array of Comparable objects.
* @param first An integer > 0 and < a.length.
* @param last An integer > first and < a.length.
*/
private <T extends Comparable<? super T>>
void insertionSort(T[] a, int first, int last)
{
if (first < last)
{
// Sort all but the last entry
insertionSort(a, first, last-1);
// Insert the last entry in sorted order
insertInOrder(a[last], a, first, last-1);
} // end if
} // end insertionSort
/** Recursively insert a value into its correct location
* @param entry The item to insert.
* @param a An array of Comparable objects.
* @param begin An integer >= 0 that is the index of the first
* array entry to consider.
* @param end An integer >= 0 that is the index of the last
* array entry to consider.
*/
public <T extends Comparable<? super T>>
void insertInOrder(T anEntry, T[] a, int begin, int end)
{
// Inserts entry into the sorted array entrys a[first] through a[last].
if (anEntry.compareTo(a[end]) >= 0) {
comparisons++;
a[end+1] = anEntry;
} else if (begin < end) {
comparisons++;
a[end+1] = a[end];
insertInOrder(anEntry, a, begin, end-1);
} else { // begin == end and enEntry < a[end]
a[end+1] = a[end];
a[end] = anEntry;
}
} // end insertInOrder
/**************************************************************
* ITERATIVE INSERTION SORT (PROVIDED FOR REFERNCE)
**************************************************************/
/** Sorts the first n objects in an array into ascending order.
* @param a An array of Comparable objects.
* @param n An integer > 0.
*/
/* Provided for reference. Modify the recursive insertion sort
* for the lab.
*
public <T extends Comparable<? super T>>
void insertionSort(T[] a, int n) {
insertionSort(a, 0, n - 1);
} // end insertionSort
*/
/** Iterative insertion sort of the objects in a range of locations in an array into ascending order.
* @param a An array of Comparable objects.
* @param first An integer >= 0 and < a.length.
* @param last An integer > first and < a.length.
*/
/* Provided for reference. Modify the recursive insertion sort
* for the lab.
*
public <T extends Comparable<? super T>>
void insertionSort(T[] a, int first, int last) {
T nextToInsert;
boolean foundLocation;
int loc;
for (int unsorted = first + 1; unsorted <= last; unsorted++) {
nextToInsert = a[unsorted];
insertInOrder(nextToInsert, a, first, unsorted - 1);
} // end for
} // end insertionSort
*/
/** Inserts anEntry into the sorted entries a[begin] through a[end].
* @param anEntry The entry to be inserted into the sorted portion of the array.
* @param a An array of Comparable objects.
* @param begin An integer >= 0 and < a.length.
* @param end An integer > first and < a.length.
*/
/* Provided for reference. Modify the recursive insertion sort
* for the lab.
*
public <T extends Comparable<? super T>>
void insertInOrder(T anEntry, T[] a, int begin, int end) {
int index = end; // index of last entry in the sorted portion
// Make room, if needed, in sorted portion for another entry
while ((index >= begin) && (anEntry.compareTo(a[index])) < 1) {
a[index + 1] = a[index]; // make room
index--;
} // end while
// Assertion: a[index + 1] is available.
a[index + 1] = anEntry; // insert
} // end insertionSort
*/
/**************************************************************
* ITERATIVE SHELL SORT
**************************************************************/
/** Sorts the first n objects in an array into ascending order.
* @param a An array of Comparable objects.
* @param n An integer > 0.
*/
public <T extends Comparable<? super T>>
void shellSort(T[] a, int n) {
startStatistics();
shellSort(a, 0, n - 1);
endStatistics();
} // end shellSort
/** Use incremental insertion sort with different increments to
* sort a range of values in the array.
* @param a An array of Comparable objects.
* @param first An integer >= 0.
* @param last An integer > first and < a.length.
*/
public <T extends Comparable<? super T>>
void shellSort(T[] a, int first, int last) {
int n = last - first + 1; // number of array entries
int space = n/2;
while (space > 0) {
for (int begin = first; begin < first + space; begin++) {
incrementalInsertionSort(a, begin, last, space);
}
space = space/2;
} // end while
} // end shellSort
/** Sorts equally spaced entries of an array into ascending order.
@param a An array of Comparable objects.
@param first The integer index of the first array entry to
consider; first >= 0 and < a.length.
@param last The integer index of the last array entry to
consider; last >= first and < a.length.
@param space the difference between the indices of the
entries to sort.
*/
public <T extends Comparable<? super T>>
void incrementalInsertionSort(T[] a, int first, int last, int space) {
int unsorted, index;
for (unsorted = first + space; unsorted <= last;
unsorted = unsorted + space)
{
T nextToInsert = a[unsorted];
index = unsorted - space;
while ((index >= first) && (nextToInsert.compareTo(a[index]) < 0)){
comparisons++;
a[index + space] = a[index];
index = index - space;
} // end while
if (index >= first) {
comparisons++;
}
a[index + space] = nextToInsert;
} // end for
} // end incrementalInsertionSort
}// end SortArray
sample output
What size arrays should be used?
It should be an integer value greater than or equal to 1.
5
How many trials?
3
The array is: [ 1 2 2 2 0 ]
The sorted array is: [ 0 1 2 2 2 ]
The array is: [ 3 4 0 2 2 ]
The sorted array is: [ 0 2 2 3 4 ]
The array is: [ 3 4 2 0 0 ]
The sorted array is: [ 0 0 2 3 4 ]
Comparison made: 9
Total: 27
Min: 9
Avg: 9
Max: 9
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.