前提・実現したいこと
Java学習中の初心者です。大学の課題です。random arrayとascending arrayでクイックソートを使ったときの時間を計っています。二つ問題があります。
発生している問題・エラーメッセージ
(問題1)
一つ目のrandom arrayは動きましたが、二つ目のascending arrayではquickSortのメソッドの quickSort(list, pivotIndex + 1, last);のラインでエラーメッセージException in thread "main" java.lang.StackOverflowErrorが出ました。
(問題2)
outputFileを使ったのですが実行後ファイルが作られていないようで見つかりません。
該当のソースコード
public static void quickSort(int[] list) { quickSort(list, 0, list.length - 1); } private static void quickSort(int[] list, int first, int last) { if (last > first) { int pivotIndex = partition(list, first, last); quickSort(list, first, pivotIndex - 1); quickSort(list, pivotIndex + 1, last); } } /** Partition the array list[first..last] */ private static int partition(int[] list, int first, int last) { int pivot = list[first]; // Choose the first element as the pivot 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; return high; } else { return first; } } public static void main(String[] args) { Random rand = new Random(); rand.setSeed(50); long average = 0;// long sum = 0; int numOfTimes = 5; PrintWriter outputFile = null; try {// outputFile = new PrintWriter("data.csv"); } catch (FileNotFoundException e) { System.out.println("error openeing the file data.csv"); e.printStackTrace(); System.exit(0); } //------------------------------------------------------------------------ for(int n = 10000; n < 1000000; n += 10000) { ////////////////////////////////////////////////////////////// for(int count = 0; count < numOfTimes; count++ ) {//2 //int n = 10000000; //make a random array of size n int array[] = new int[n]; ////////////////////////////////////////////////////// for(int i = 0; i < n; i++) {//3 array[i] = rand.nextInt(n); //System.out.println(array[i]); }//end 3 //////////////////////////////////////////////////////// long startTime = System.nanoTime(); quickSort(array); long endTime = System.nanoTime(); //outputFile.println((endTime - startTime)); //System.out.println("Time it took for " + n + " items is " + (endTime - startTime)); sum += (endTime - startTime); }//end for 2 //////////////////////////////////////////////////////////// average = sum / numOfTimes; System.out.println(n + " " + average); outputFile.println(n + "," + average); //System.out.println("done" + n); System.out.println(); average = 0;//reset the average sum = 0; }//end 4 //---------------------------------------------------------------------------------- outputFile.println();//inserts a blankline in the file System.out.println("end quick sort for random items"); System.out.println(); System.out.println("Start quick sort for ascending items"); for(int n = 10000; n < 1000000; n += 10000){ ////////////////////////////////////////////////////////////// for(int count = 0; count < numOfTimes; count++ ) {//2 //int n = 10000000; //make a random array of size n int array[] = new int[n]; ////////////////////////////////////////////////////// for(int i = 0; i < n; i++) {// array[i] = i; //System.out.println(array[i]); }//end 3 //////////////////////////////////////////////////////// long startTime = System.nanoTime(); quickSort(array); long endTime = System.nanoTime(); //outputFile.println((endTime - startTime)); //System.out.println("Time it took for " + n + " items is " + (endTime - startTime)); sum += (endTime - startTime); }//end for 2 //////////////////////////////////////////////////////////// average = sum / numOfTimes; System.out.println(n + " " + average); outputFile.println(n + "," + average); //System.out.println("done" + n); System.out.println(); average = 0;//reset the average sum = 0; }//end 4 //---------------------------------------------------------------------------------- outputFile.println();//inserts a blankline in the file System.out.println("end (ascending. quick sort)"); System.out.println(); outputFile.close(); }end main
オンラインでの質問は初めてなので説明に不足がありましたら追記します。よろしくお願い致します。
回答1件
あなたの回答
tips
プレビュー