Chalen Chalen - 17 days ago 7
Java Question

Java error on sort programme. Any assistance appreciated

Getting an error that I can't seem to track down or solve. This is my very first post, so if I've made mistakes in my post format, please forgive me! I'm learning still!

/**
* Problem 23.13
* ExcutionTimeForSorting class obtains the execution time
* of selection sort, bubble sort, merge sort, quick sort, heap sort,
* and radiz sort for input size 5,000, 10,000, 15,000, 20,000,
* 25,000, and 30,000.
*/

import java.util.ArrayList;
import java.util.*;


public class ExecutionTimeForSorting
{
//start of main method
public static void main (String [] args)
{
//creating a two-dimensional array for selection sort
int [] [] selectionArray = new int [6] [];
selectionArray[0] = new int [50000];
selectionArray[1] = new int [100000];
selectionArray[2] = new int [150000];
selectionArray[3] = new int [200000];
selectionArray[4] = new int [250000];
selectionArray[5] = new int [300000];

//creating a two-dimensional array for bubble sort
int [] [] bubbleArray = new int [6] [];
bubbleArray[0] = new int [50000];
bubbleArray[1] = new int [100000];
bubbleArray[2] = new int [150000];
bubbleArray[3] = new int [200000];
bubbleArray[4] = new int [250000];
bubbleArray[5] = new int [300000];

//creating a two-dimensional array for merge sort
int [] [] mergeArray = new int [6] [];
mergeArray[0] = new int [50000];
mergeArray[1] = new int [100000];
mergeArray[2] = new int [150000];
mergeArray[3] = new int [200000];
mergeArray[4] = new int [250000];
mergeArray[5] = new int [300000];

//creating a two-dimensional array for quick sort
int [] [] quickArray = new int [6] [];
quickArray[0] = new int [50000];
quickArray[1] = new int [100000];
quickArray[2] = new int [150000];
quickArray[3] = new int [200000];
quickArray[4] = new int [250000];
quickArray[5] = new int [300000];

//creating a two-dimensional array for heap sort
int [] [] heapArray = new int [6] [];
heapArray[0] = new int [50000];
heapArray[1] = new int [100000];
heapArray[2] = new int [150000];
heapArray[3] = new int [200000];
heapArray[4] = new int [250000];
heapArray[5] = new int [300000];

//creating a two-dimensional array for radix sort
int [] [] radixArray = new int [6] [];
radixArray[0] = new int [50000];
radixArray[1] = new int [100000];
radixArray[2] = new int [150000];
radixArray[3] = new int [200000];
radixArray[4] = new int [250000];
radixArray[5] = new int [300000];

//declaring two variables to find elapsed time
long startTime = 0, endTime = 0;

//creating one-dimensional array to store elapsed times
long [] selectionExecutionTime = new long [6];
long [] bubbleExecutionTime = new long [6];
long [] mergeExecutionTime = new long [6];
long [] quickExecutionTime = new long [6];
long [] heapExecutionTime = new long [6];
long [] radixExecutionTime = new long [6];

//storing the same integers randomly in all two-dimensional arrays
for (int i = 0; i < selectionArray.length; i++)
{
for (int j = 0; j < selectionArray[i].length; j++)
{
int number = (int) (Math.random() * 1000);
selectionArray[i][j] = number;
bubbleArray[i][j] = number;
mergeArray[i][j] = number;
quickArray[i][j] = number;
heapArray[i][j] = number;
radixArray[i][j] = number;
}
}

//finding the elapsed time for selection sort
for (int i = 0; i < selectionArray.length; i++)
{
startTime = System.currentTimeMillis();
//call to selectionSort method
SelectionSort.selectionSort(selectionArray[i]);
endTime = System.currentTimeMillis();

selectionExecutionTime[i] = endTime - startTime;
startTime = 0;
endTime = 0;
}

//finding the elapsed time for bubble sort
for (int i = 0; i < bubbleArray.length; i++)
{
startTime = System.currentTimeMillis();
//call to BubbleSort method
BubbleSort.bubbleSort(selectionArray[i]);
endTime = System.currentTimeMillis();

bubbleExecutionTime[i] = endTime - startTime;
startTime = 0;
endTime = 0;
}

//finding the elapsed time for merge sort
for (int i = 0; i < mergeArray.length; i++)
{
startTime = System.currentTimeMillis();
//call to mergeSort method
MergeSort.mergeSort(selectionArray[i]);
endTime = System.currentTimeMillis();

mergeExecutionTime[i] = endTime - startTime;
startTime = 0;
endTime = 0;
}

//finding the elapsed time for quick sort
for (int i = 0; i < quickArray.length; i++)
{
startTime = System.currentTimeMillis();
//call to quickSort method
QuickSortNonRecursive.quickSort(selectionArray[i]);
endTime = System.currentTimeMillis();

quickExecutionTime[i] = endTime - startTime;
startTime = 0;
endTime = 0;
}

//finding the elapsed time for heap sort
for (int i = 0; i < heapArray.length; i++)
{
startTime = System.currentTimeMillis();
//call to heapSort method
HeapSort.heapSort(selectionArray[i]);
endTime = System.currentTimeMillis();

heapExecutionTime[i] = endTime - startTime;
startTime = 0;
endTime = 0;
}

//finding the elapsed time for radix sort
for (int i = 0; i < radixArray.length; i++)
{
startTime = System.currentTimeMillis();
//call to radixSort method
RadixSort.radixSort(selectionArray[i]);
endTime = System.currentTimeMillis();

radixExecutionTime[i] = endTime - startTime;
startTime = 0;
endTime = 0;
}

/*displaying all elapsed times of all sorting techniques
in a table format */
System.out.printf("%10s%2s%15s%13s%13s%13s%13s%13\n",
"Array size", "|", "Selection Sort", "Bubble Sort",
"Merge Sort", "Quick Sort", "Heap Sort", "Radix Sort");

System.out.println("-----------|-----------------" +
"-------------------------------------------" +
"---------------------");

for (int i = 0; i < selectionArray.length; i++)
{
System.out.printf("%7s%5s%13s%14s%13s%13s%13s%13s\n",
selectionArray[i].length, "|",
selectionExecutionTime[i],
bubbleExecutionTime[i],
mergeExecutionTime[i],
quickExecutionTime[i],
heapExecutionTime[i],
radixExecutionTime[i]);
}
}//end of main method


}//end of ExecutionTimeForSorting class

//SelectionSort Class demonstrates selectionSort method
class SelectionSort
{
//the method for sorting the numbers
public static void selectionSort (int[] list)
{
for (int i = 0; i < list.length -1; i++)
{
//finding the minimum in the list
int currentMin = list[i];
int currentMinIndex = i;

for (int j = i + 1; j < list.length; j++)
{
if (currentMin > list[j])
{
currentMin = list[j];
currentMinIndex = j;
}
}

//swapping list[i] with list [currentMinIndex] if necessary
if (currentMinIndex != i)
{
list[currentMinIndex] = list[i];
list[i] = currentMin;
}
}
}//end of selectionSort method
}//end of SelectionSort class

//BubbleSort class demonstrates the method bubbleSort
class BubbleSort
{
//bubble sort method
public static void bubbleSort(int[] list)
{
boolean needNextPass = true;

for (int k = 1; k < list.length && needNextPass; k++)
{
//array may be sorted and next pass not needed
needNextPass = false;
for (int i = 0; i < list.length - k; i++)
{
if (list[i] > list [i + 1])
{
//swap list[i] with list [i+1]
int temp = list[i];
list[i] = list[i + 1];
list[i + 1] = temp;
//Next pass still needed
needNextPass = true;
}
}
}
}//end of bubbleSort method
}//end of BubbleSort class


//MergeSort class demonstrates the methods mergeSort and merge
class MergeSort
{
//the method for sorting the numbers
public static void mergeSort (int[] list)
{
if (list.length > 1)
{
//merge sort the first half
int[] firstHalf = new int[list.length/2];
System.arraycopy(list, 0, firstHalf, 0, list.length/2);
mergeSort(firstHalf);

//merge sort the second half
int secondHalfLength = list.length - list.length/2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(list, list.length/2, secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);

//merge first half with second half into list
merge (firstHalf, secondHalf, list);
}
}//end of mergeSort method

//merge two sorted lists
public static void merge (int[] list1, int[] list2, int[] temp)
{
int current1 = 0;//current index in list1
int current2 = 0;//current index in list2
int current3 = 0;//current index in temp

while(current1 < list1.length && current2 < list2.length)
{
if (list1[current1] < list2[current2])
temp[current3++] = list1[current1++];
else
temp[current3++] = list2[current2++];
}

while (current1 < list1.length)
temp [current3++] = list1[current1++];

while (current2 < list2.length)
temp[current3++] = list2[current2++];
}//end of merge method
}//end of MergeSort class


/*QuickSortNonRecursice class demonstrates the mehods quickSort,
quickSort helper and partition*/
class QuickSortNonRecursive
{
//quickSort method
public static void quickSort(int[] list)
{
quickSort(list, 0, list.length - 1);
}//end of quickSort method

//quickSort helper method
public static void quickSort (int[] list, int first, int last)
{
//creating a stack of integers
Stack<Integer> stack = new Stack<Integer>();
stack.push(first);
stack.push(last);

while(!stack.empty())
{
last = (Integer)stack.pop();
first = (Integer)stack.pop();

if(last <= first)
continue;

//get the pivot point
int pivotIndex = partition(last, first, last);

if((pivotIndex - first) > (last - pivotIndex))
{
stack.push(first);
stack.push(pivotIndex - 1);
}

stack.push(pivotIndex + 1);
stack.push(last);

if ((last - pivotIndex) >= (pivotIndex - first))
{
stack.push(first);
stack.push(pivotIndex - 1);
}
}
}//end of quickSort helper method

//partition the array list[first...last]
private static int partition(int[] list, int first, int last)
{
//choose the first element as the pivot
int pivot = list[first];
int low = first +1;//index for forward search
int high = last;//index for backward search

while (high > low)
{
//search forward from left
while (low <= high && list[low] <= pivot)
low++;

//search backward from right
while( low <= high && list[high] > pivot)
high--;

//swap two elements in the list
if (high > low)
{
int temp = list[high];
list[high] = list[low];
list[low] = temp;
}
}

while(high > first && list[high] >= pivot)
high--;

//swap pivot with list[high]
if (pivot > list[high])
{
list[first] = list[high];
list[high] = pivot;
}
else
{
return first;
}
}//end of partition method
}//end of QuickSortNonRecursive class


//HeapSort class demonstrates the method heapSort
class HeapSort
{
//heap sort method
public static <E extends Comparable> void heapSort (E[] list)
{
//creating a heap of integers
Heap<E> heap = new Heap<E>();

//adding elements to the heap
for (int i = 0; i < list.length; i++)
heap.add(list[i]);

//remove elements from the heap
for (int i = list.length - 1; i >= 0; i--)
list[i] = heap.remove();

}//end of heapSort method
}//end of HeapSort class


/*RadixSort class demonsrates the methods radixSort, radixSort
helper, and getPosition*/
class RadixSort
{
//radixSort method
public static void radixSort (int[] list)
{
radixSort(list,5);
}//end of radixSort method

//radixSort helper method
public static void radixSort (int[] list, int mostDigits)
{
ArrayList<Integer>[] radix = new ArrayList[10];

for (int i = 0; i < radix.length; i++)
{
radix[i] = new ArrayList<Integer>();
}

for (int index = 0; index < list.length; index++)
{
for (int i = 0; i < radix.length; i++)
{
radix[i].clear();
}
for (int i = 0; i < list.length; i++)
{
int position = getPosition(list[i],
index);
radix[position].add(list[i]);
}

int k = 0; //index of list
for (int i = 0; i < radix.length; i++)
{
for (int j = 0; j< radix[i].size(); j++)
list[k++] = radix[i].get(j);
}
}
}//end of radixSort helper method

//getPosition method
public static int getPosition(int value, int index)
{
int result = 1;
for (int i = 0; i < index; i++)
result = result * 10;
return (value / result) % 10;
}//end of getPosition method
}//end of RadixSort class


The error I'm getting is attached...
enter image description here

1:

Answer

First error: I could be wrong, but it looks like your heapSort method only works with items that implement the Comparable interface, which means you need to use the Integer class rather than the int primitive type. https://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html

Second error: You're passing "last" as your first parameter to partition() instead of "list".

Third error: You're trying to declare an object of type Heap, but you never define a Heap class. I'm not aware of any native class called Heap in Java.