Ok, I made the changes to quickSort, but there is no output now?
/*
* Kyle Arthur Benzle
* Lab 3
* Oct. 30 9
* Tagore
*/
import java.io.*;
import java.util.Scanner;
//Lab3 Class
public class Lab3 {
public static void main(String[] args) throws IOException {
//getting the user input from scanner, calling it "input"
System.out.print("Name of file with array: ");
Scanner readIn = new Scanner(System.in);
String input = readIn.nextLine();
//testScan1(input);
}
private String filename;
//Calling this method testScan1 to read in the file info, taking in the filename as a parameter
//public static void testScan1(String filename) {
//Calling the file, file
File file = new File(filename);
Scanner scan;
//making an int array called array of course.
int[] array;{
//using try/catch block to read from file, (Incase file is not found)
try {
//Lab assignment never said anything about what our input would be, I assume there will be 6 intergers like in the example, I think this is a fair assumption as it was not defined that we had to have the array length variable.
array = new int[5];
//scan to get file info
scan = new Scanner(file);
//if, the file name was not found, give this error
} catch (java.io.FileNotFoundException e) {
System.out.println("couldn't open. file not found ");
}
int i =0;
//Now, finally, reading the file, while loop for as long as i is < file.length.
while (scan.hasNext()) {
//the below comment is for printing the array, Just a test.
//for (i = 0; i <= file.length(); ++i)
//setting each of the array element = to the next number in the file
array[i] = Integer.parseInt(scan.next());
//i++;
i++;}
//Calling the quicksort method with array, 0 for left and length-1 for right
quickSort(array, 0, array.length-1);
//calling partition method, with the same as the above
partition(array, 0, array.length-1);
//Just another test, trying to print array
//System.out.println(java.util.Arrays.toString(array));
//printing array
//for (int j = 0; j < array.length; ++j)
//System.out.println(array[i] + " ");
}
//partition method
static int partition(int[] arr, int left, int right) {
int i = left;
int j = right;
int tmp;
//making pivot = to the last element of array
int pivot = arr.length-1;
//3 while loops to move the left and right toward each other, until the can be swapped below.
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
return i;
}
//QuickSort Method, taking in arr, left and right
static void quickSort(int arr[], int left, int right) {
//Setting index = to the partition with parameters of array and left and right, when that method runs
if (left>=1) return;
int index = partition(arr, left, right); //ERROR this line is giving an exception when the program runs, a stack overflow.
//if (left < (index - 1)) ;
//Call quickSort recursively with the new right
quickSort(arr, left, index); //ERROR, this line is giving the overflow error I think you were talking about in class, that a lot of people were having trouble with.
//if (index < right) {
//or call quickSort recursively with the old #'s
quickSort(arr, index+1, 1);
}}
//Now, trying to print out the array.
//for (int j = 0; j < arr.length; ++j)
//System.out.println(arr[j] + " ");
// }
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101:





by: jb1devPosted on 2009-11-05 at 17:51:38ID: 25756055
Your quicksort function looks wrong. It's just calling itself endlessly.
static void quickSort(int[] arr, int left, int right) {
int index = partition(arr, left, right);
if (left < (index - 1)); {
}
quickSort(arr, left, index - 1); // <-- here
if (index < right) {
quickSort(arr, index, right);
}
}