In my java assignment, I have to count the number of comparisons that occur, and also the total execution time for selection sort, insertion sort, bubble sort, quick sort and merge sort algorithms. The following code below is a driver program to test the code that runs the algorithms while counting their execution times and comparisons. In the code, I initialized the list with values and ran it through them. The only output I get is "Sorted Lists..." which is just the first line. The rest of it isn't running and I'm lost. Please help.
public class SortingTest {
//create 3 constant values
static final int SIZE = 1000;//number of values in the lists
static final int SORTED_ORDER = 0;//for sorted lists
static final int RANDOM_ORDER = 1;//for unsorted lists
//create the lists for each sorting algorithm
static Integer[] selArr = new Integer[SIZE];
static Integer[] insArr = new Integer[SIZE];
static Integer[] bubArr = new Integer[SIZE];
static Integer[] quiArr = new Integer[SIZE];
static Integer[] merArr = new Integer[SIZE];
public static void main(String[] args) {
//perform the sorting on sorted lists
performSorting(SORTED_ORDER);
//perform the sorting on unsorted lists
performSorting(RANDOM_ORDER);
//perform the sorting on unsorted lists
performSorting(RANDOM_ORDER);
}
private static void performSorting(int order) {
if(order == SORTED_ORDER)//display if the lists are in sorted order or not
System.out.println("Sorted Lists...");
else
System.out.println("Unsorted Lists...");
//initialize the lists in sorted order
initLists(order);
//initialize the number of comparisons and total execution time
initComparisonsAndExecutionTime();
//sort the lists
sortLists();
//display the number of comparisons and total execution time
printComparisonsAndExecutionTime();
}
//initializes the lists with the same values
private static void initLists(int order) {
int number;
for(int i=0;i<SIZE;i++) {
if(order == SORTED_ORDER)
number = new Integer(i);
else
number = new Integer((int)(Math.random()*SIZE));
selArr[i] = number;
insArr[i] = number;
bubArr[i] = number;
quiArr[i] = number;
merArr[i] = number;
}
}
/*initializes the number
of comparisons and total execution time for each algorithm*/
private static void initComparisonsAndExecutionTime() {
Sorting.selectionSortComparisons = 0;
Sorting.insertionSortComparisons = 0;
Sorting.bubbleSortComparisons = 0;
Sorting.quickSortComparisons = 0;
Sorting.mergeSortComparisons = 0;
Sorting.selectionSortExecutionTime = 0L;
Sorting.insertionSortExecutionTime = 0L;
Sorting.bubbleSortExecutionTime = 0L;
Sorting.quickSortExecutionTime = 0L;
Sorting.mergeSortExecutionTime = 0L;
}
/*calls each sorting algorithm with the
corresponding lists to sort the values*/
private static void sortLists() {
Sorting.selectionSort(selArr);
Sorting.insertionSort(insArr);
Sorting.bubbleSort(bubArr);
Sorting.quickSort(quiArr);
Sorting.mergeSort(merArr);
}
/*displays the number of comparisons and total execution time
for each algorithm*/
private static void printComparisonsAndExecutionTime() {
System.out.println("----------------------");
System.out.printf("%-15s%15s%15s\n", "SORTING METHOD",
"COMPARISONS", "EXEC.TIME(ns)");
System.out.println("----------------------");
System.out.printf("%-15s%15d%15d\n", "Selection sort",
Sorting.selectionSortComparisons,
Sorting.selectionSortExecutionTime);
System.out.printf("%-15s%15d%15d\n", "Insertion sort",
Sorting.insertionSortComparisons,
Sorting.insertionSortExecutionTime);
System.out.printf("%-15s%15d%15d\n", "Bubble sort",
Sorting.bubbleSortComparisons,
Sorting.bubbleSortExecutionTime);
System.out.printf("%-15s%15d%15d\n", "Quick sort",
Sorting.quickSortComparisons,
Sorting.quickSortExecutionTime);
System.out.printf("%-15s%15d%15d\n", "Merge sort",
Sorting.mergeSortComparisons,
Sorting.mergeSortExecutionTime);
System.out.println("-----------------------\n\n");
}
}
Here's the implementation for all the algorithms
public class Sorting
{
public static int selectionSortComparisons = 0;
public static int insertionSortComparisons = 0;
public static int bubbleSortComparisons = 0;
public static int quickSortComparisons = 0;
public static int mergeSortComparisons = 0;
public static long selectionSortExecutionTime = 0L;
public static long insertionSortExecutionTime = 0L;
public static long bubbleSortExecutionTime = 0L;
public static long quickSortExecutionTime = 0L;
public static long mergeSortExecutionTime = 0L;
/**
* Sorts the specified array of integers using the selection
* sort algorithm.
*
* @param data the array to be sorted
*/
public static <T extends Comparable<T>>
void selectionSort(T[] data)
{
long startTime = System.nanoTime();//stores the beginning time of
selection sort algorithm
int min;
T temp;
for (int index = 0; index < data.length-1; index++)
{
min = index;
for (int scan = index+1; scan < data.length; scan++) {
selectionSortComparisons++;//counts the number of
comparisons in selection sort
if (data[scan].compareTo(data[min])<0)
min = scan;
}
swap(data, min, index);
}
long endTime = System.nanoTime();//stores the ending time of
selection sort
selectionSortExecutionTime = endTime - startTime;//computes total
execution time of selection sort
}
/**
* Swaps to elements in an array. Used by various sorting algorithms.
*
* @param data the array in which the elements are swapped
* @param index1 the index of the first element to be swapped
* @param index2 the index of the second element to be swapped
*/
private static <T extends Comparable<T>>
void swap(T[] data, int index1, int index2)
{
T temp = data[index1];
data[index1] = data[index2];
data[index2] = temp;
}
/**
* Sorts the specified array of objects using an insertion
* sort algorithm.
*
* @param data the array to be sorted
*/
public static <T extends Comparable<T>>
void insertionSort(T[] data)
{
long startTime = System.nanoTime();//stores beginning time of
insertion sort
for (int index = 1; index < data.length; index++)
{
T key = data[index];
int position = index;
// shift larger values to the right
while (position > 0 && data[position-1].compareTo(key) > 0)
{
insertionSortComparisons++;//counts the number of
comparisons in insertion sort
data[position] = data[position-1];
position--;
}
if (position > 0)
insertionSortComparisons++;//counts the number of comparisons in insertion sort
data[position] = key;
}
long endTime = System.nanoTime();//stores ending time of insertion
sort
selectionSortExecutionTime = endTime - startTime;//computes total execution time of selection sort
}
/**
* Sorts the specified array of objects using a bubble sort
* algorithm.
*
* @param data the array to be sorted
*/
public static <T extends Comparable<T>>
void bubbleSort(T[] data)
{
long startTime = System.nanoTime();//stores the beginning of bubble sort
int position, scan;
T temp;
for (position = data.length - 1; position >= 0; position--)
{
for (scan = 0; scan <= position - 1; scan++)
{
bubbleSortComparisons++;//counts the number of comparisons in bubble sort
if (data[scan].compareTo(data[scan+1]) > 0)
swap(data, scan, scan + 1);
}
}
long endTime = System.nanoTime();//stores end of bubble sort
selectionSortExecutionTime = endTime - startTime;//computes total execution time of bubble sort
}
/**
* Sorts the specified array of objects using the merge sort
* algorithm.
*
* @param data the array to be sorted
*/
public static <T extends Comparable<T>>
void mergeSort(T[] data)
{
long startTime = System.nanoTime();//stores beginning of merge sort
mergeSort(data, 0, data.length - 1);
long endTime = System.nanoTime();//stores end of merge sort
selectionSortExecutionTime = endTime - startTime;//computes total execution time of merge sort
}
/**
* Recursively sorts a range of objects in the specified array using the
* merge sort algorithm.
*
* @param data the array to be sorted
* @param min the index of the first element
* @param max the index of the last element
*/
private static <T extends Comparable<T>>
void mergeSort(T[] data, int min, int max)
{
if (min < max)
{
int mid = (min + max) / 2;
mergeSort(data, min, mid);
mergeSort(data, mid+1, max);
merge(data, min, mid, max);
}
}
/**
* Merges two sorted subarrays of the specified array.
*
* @param data the array to be sorted
* @param first the beginning index of the first subarray
* @param mid the ending index fo the first subarray
* @param last the ending index of the second subarray
*/
@SuppressWarnings("unchecked")
private static <T extends Comparable<T>>
void merge(T[] data, int first, int mid, int last)
{
T[] temp = (T[])(new Comparable[data.length]);
int first1 = first, last1 = mid; // endpoints of first subarray
int first2 = mid+1, last2 = last; // endpoints of second subarray
int index = first1; // next index open in temp array
// Copy smaller item from each subarray into temp until one
// of the subarrays is exhausted
while (first1 <= last1 && first2 <= last2)
{
mergeSortComparisons++;//count the number of comparisons in merge sort
if (data[first1].compareTo(data[first2]) < 0)
{
temp[index] = data[first1];
first1++;
}
else
{
temp[index] = data[first2];
first2++;
}
index++;
}
// Copy remaining elements from first subarray, if any
while (first1 <= last1)
{
temp[index] = data[first1];
first1++;
index++;
}
// Copy remaining elements from second subarray, if any
while (first2 <= last2)
{
temp[index] = data[first2];
first2++;
index++;
}
// Copy merged data into original array
for (index = first; index <= last; index++)
data[index] = temp[index];
}
/**
* Sorts the specified array of objects using the quick sort algorithm.
*
* @param data the array to be sorted
*/
public static <T extends Comparable<T>>
void quickSort(T[] data)
{
long startTime = System.nanoTime();//stores beginning of quick sort
quickSort(data, 0, data.length - 1);
long endTime = System.nanoTime();//stores end of quick sort
selectionSortExecutionTime = endTime - startTime;//computes total execution time of quick sort
}
/**
* Recursively sorts a range of objects in the specified array using the
* quick sort algorithm.
*
* @param data the array to be sorted
* @param min the minimum index in the range to be sorted
* @param max the maximum index in the range to be sorted
*/
private static <T extends Comparable<T>>
void quickSort(T[] data, int min, int max)
{
if (min < max)
{
// create partitions
int indexofpartition = partition(data, min, max);
// sort the left partition (lower values)
quickSort(data, min, indexofpartition - 1);
// sort the right partition (higher values)
quickSort(data, indexofpartition + 1, max);
}
}
/**
* Used by the quick sort algorithm to find the partition.
*
* @param data the array to be sorted
* @param min the minimum index in the range to be sorted
* @param max the maximum index in the range to be sorted
*/
private static <T extends Comparable<T>>
int partition(T[] data, int min, int max)
{
T partitionelement;
int left, right;
int middle = (min + max) / 2;
// use the middle data value as the partition element
partitionelement = data[middle];
// move it out of the way for now
swap(data, middle, min);
left = min;
right = max;
while (left < right)
{
// search for an element that is > the partition element
while (left < right && data[left].compareTo(partitionelement) <= 0)
quickSortComparisons++;//counts the number of comparisons in quick sort
left++;
// search for an element that is < the partition element
while (data[right].compareTo(partitionelement) > 0)
quickSortComparisons++;//counts the number of comparisons in quick sort
right--;
quickSortComparisons++;//counts the number of comparisons in quick sort
// swap the elements
if (left < right)
quickSortComparisons++;//counts the number of comparisons in quick sort
swap(data, left, right);
}
// move the partition element into place
swap(data, min, right);
return right;
}
}
I tried adding some prints to help debug your code. I found out that your quick sort method runs into an infinite loop.
The output was:
Sorted Lists...
Lists Initialized!
Comparisons and Exec time initialized!
Selection done!
Insertion done!
Bubble done!
When I commented this line Sorting.quickSort(quiArr);, I got the following output:
----------------------
SORTING METHOD COMPARISONS EXEC.TIME(ns)
----------------------
Selection sort 499500 2726141
Insertion sort 243586 0
Bubble sort 499500 0
Quick sort 0 0
Merge sort 8697 0
-----------------------
Which made me check your code to set the execution time for each sorting method. Looks like all methods set Sorting.selectionSortExecutionTime, as you can see on the following snippet from mergeSort:
public static <T extends Comparable<T>> void mergeSort(T[] data) {
long startTime = System.nanoTime();// stores
// beginning
// of
// merge
// sort
mergeSort(data, 0, data.length - 1);
long endTime = System.nanoTime();// stores
// end
// of
// merge
// sort
/* Wrong variable */
selectionSortExecutionTime = endTime - startTime;// computes
// total
// execution
// time
// of
// merge
// sort
}
I did some debugging in the quick sort method and found the following:
The while loops inside the while(left<right) didn't have curly braces, so the left++ and right-- where left out, only the quickSortComparisons++ was inside them. Here's the fixed code with comments pointing out what I described:
private static <T extends Comparable<T>> int partition(T[] data,
int min,
int max) {
T partitionelement;
int left, right;
int middle = (min + max) / 2;
// use the middle data value as the
// partition element
partitionelement = data[middle];
// move it out of the way for now
swap(data, middle, min);
left = min;
right = max;
while (left < right) {
// search for an element that is >
// the partition element
while (left < right
&& data[left].compareTo(partitionelement) <= 0){
// counts the number of comparisons in quick sort
quickSortComparisons++;
left++; // <--- this was not in the while loop
}
quickSortComparisons++; // <--- I believe you should have this one too
// search for an element that is <
// the partition element
while (data[right].compareTo(partitionelement) > 0){
// counts the number of comparisons in quick sort
quickSortComparisons++;
right--; // <--- this wasn't in the while loop neither
}
// counts the number of comparisons in quick sort
quickSortComparisons++;
// swap the elements
if (left < right)
quickSortComparisons++;// counts the number of comparisons in quick sort
swap(data, left, right);
}
// move the partition element into place
swap(data, min, right);
return right;
}
Hope I helped!