質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.12%

Javaクイックソートによる時間計測テストでのエラー

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 641

Kana517

score 5

 前提・実現したいこと

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


オンラインでの質問は初めてなので説明に不足がありましたら追記します。よろしくお願い致します。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • Kana517

    2018/03/22 11:12

    勉強になりました。デバッグの仕方もよくわからず、英語力も低いため留学先で質問がうまくできず、確かに考えてみたら甘えでここに投稿してしまったと思います。一応3日間ほどわからないところを調べて周りの人に質問もしてこんなコードでもやっとの思いでここまでたどり着いたのですが、KSwordOfHasteさんにご指導いただき、まだまだ自分自身でできることは残っていると気づきました。大変勉強になりました。ありがとうございます。

    キャンセル

  • KSwordOfHaste

    2018/03/22 11:17 編集

    一点重要な点を補足します。せっかくデバッグしてても、それの詳細を質問文に明記しないと「閲覧している側にあなたがどこまで調べたか」が伝わらないという点に注意してください。

    キャンセル

  • Kana517

    2018/03/22 11:27

    了解しました!ご指摘本当に感謝致します。お恥ずかしい話ですが大きな勉強になりました。プログラマーのマナーも勉強します。

    キャンセル

回答 1

checkベストアンサー

0

詳しくは見てませんが、問題のありそうなところがいくつかあります。

      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);
        }
      }

ここで、自分自身を呼び出してますが、こういう場合、終了条件をよほど検討しないと、繰り返し実行しすぎて、エラーになって落ちます
おそらくここがエラーの原因ですね。

        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];


さらに、ここのループで膨大な array の領域を確保して、メモリ領域(ヒープ領域)を食いつぶしているものとみえますが、まあ、今どきのPCの場合ならこの程度はこなしてくれるでしょう

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/03/22 11:01

    冗長なコードを見ていただきありがとうございました。この部分を再考してみます!

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.12%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る