please solve each parts When evaluating sorting algorithms, there many factors t
ID: 3595677 • Letter: P
Question
please solve each parts
When evaluating sorting algorithms, there many factors that might affect how fast an algorithm will run when it is programmed for a real machine: CPU speed, language used, type of data being sorted, type of operating system, and the number of concurrent processes running at the same time. For this reason, comparing actual running times of an algorithm is ineffectual for making judgments about how good the algorithm might be.
To effectively make a judgment that is free of real world constraints, computer scientists, when comparing sorting algorithms, often simply count the number of comparisons an algorithm makes.
Create a new NetBeans project named CPS151_Lab12
DO NOT delete the auto-generated main class (CPS151_Lab12.java)
Download and import the source files IntegerSorter.java and ArrayUtil.java into your CPS151_Lab12 NetBeans project.
If needed, refer to the online instructions on how to import a Java source file into a NetBeans project.
IntegerSorter.java:
ArrayUtil.java:
In the comment block near the top of the source file CPS151_Lab12.java, enter your name after the @author tag.
Lab 12.1
Add a counter to the IntegerSorter class to help us measure the number of comparisons of array elements being made while the routine is completing the sort.
The behavior we want to monitor occurs in this section of code, in the while loop of the insertInOrder method:
while ((index >= begin))
{
if (entryToInsert < a[index]) {
a[index + 1] = a[index]; // make room
index--;
} else {
break; // found place for entry; stop
} // end if/else
} // end while
It is in the above section that we compare array elements and decide where the entryToInsert should be placed.
By counting the number of comparisons here, we obtain a measurement that helps us gauge the speed of the algorithm.
Add code that will count each comparison, maintaining the result in an integer counter:
Add a static int counter data field (i.e., instance variable).
Add a static method getCounter to retrieve the counter.
Add a second static method called resetCounter to set the counter to 0.
Add code in the above while loop to update the counter every time two elements are compared.
Lab 12.2
Add the highlighted test code to the main method (below) so you can test sorting arrays with sizes 10000, 20000, …,90000.
/*
This program demonstrates the insertion sort algorithm by
sorting an array that is filled with random numbers.
*/
public static void main(String[] args)
{
final int FIRST_SIZE = 10000;
final int LAST_SIZE = 90000;
System.out.println("Array Size Number of Comparisons");
for (int size = FIRST_SIZE; size <= LAST_SIZE; size+=10000) {
int[] a = ArrayUtil.randomIntArray(size, size);
IntegerSorter.resetCounter();
IntegerSorter.sort(a);
if (ArrayUtil.isSorted(a)) {
System.out.println(size + " " + IntegerSorter.getCounter());
}
} // end for loop
} // end main method
Explanation / Answer
Please find my implementation.
/** A class of static methods for sorting an array of integers
from smallest to largest.
@author Frank M. Carrano
*/
public class IntegerSorter
{
private static int counter = 0;
public static int getCounter() {
return counter;
}
public static void resetCounter(){
counter = 0;
}
public static void sort(int[] a)
{
insertionSort(a, 0, a.length - 1);
} // end insertionSort
public static void insertionSort(int[] a, int first, int last)
{
for (int unsorted = first + 1; unsorted <= last; unsorted++)
{
// Assertion: a[first] <= a[first + 1] <= ... <= a[unsorted - 1]
int firstUnsorted = a[unsorted];
insertInOrder(firstUnsorted, a, first, unsorted - 1);
} // end for
} // end insertionSort
// Inserts a given entry into the sorted array
// segment extending from a[begin] to a[end].
private static void insertInOrder(int entryToInsert, int[] a,
int begin, int end)
{
int index = end;
while ((index >= begin))
{
counter++; // increasing number of comparisons
if (entryToInsert < a[index]) {
a[index + 1] = a[index]; // make room
index--;
} else {
break; // found place for entry; stop
} // end if/else
} // end while
// Assertion: a[index + 1] is available
a[index + 1] = entryToInsert; // insert
// Assertion: a[begin] <= a[begin + 1] <= ... <= a[end + 1]
} // end insertInOrder
} // end IntegerSorter
#########
public class CPS151_Lab12 {
/*
This program demonstrates the insertion sort algorithm by
sorting an array that is filled with random numbers.
*/
public static void main(String[] args)
{
final int FIRST_SIZE = 10000;
final int LAST_SIZE = 90000;
System.out.println("Array Size Number of Comparisons");
for (int size = FIRST_SIZE; size <= LAST_SIZE; size+=10000) {
int[] a = ArrayUtil.randomIntArray(size, size);
IntegerSorter.resetCounter();
IntegerSorter.sort(a);
if (ArrayUtil.isSorted(a)) {
System.out.println(size + " " + IntegerSorter.getCounter());
}
} // end for loop
} // end main method
}
/*
sample run:
Array Size Number of Comparisons
10000 25119804
20000 100234799
30000 224775148
40000 400124696
50000 626412903
60000 901523483
70000 1225054198
80000 1597540665
90000 2024497807
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.