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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

1回答

435閲覧

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

Kana517

総合スコア7

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

0クリップ

投稿2018/03/22 01:26

編集2018/03/22 01:56

前提・実現したいこと

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

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

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Kana517

2018/03/22 01:38

申し訳ありません。丸投げになってしまっているということでしょうか?問題点がはっきりしていないということでしょうか?
defghi1977

2018/03/22 01:45

質問のコツなんですが, 「大学の課題」というキーワードがあるだけで質問の閲覧を避けられるケースがあります. また, 題名が名詞の羅列では内容を推し量ることが出来ません. すくなくともこういったパブリックな場で質問をする場合は, 質問があなただけのものではなく皆で共有されるという認識をもって下さい.
Kana517

2018/03/22 02:03 編集

ありがとうございます。訂正してみます。海外で英語で学んでいるため日本語だとどのような表現を使ったらいいかわからず説明不足となってしまいました。オンラインでの質問は初めてなのでこのようなマナーがわかりませんでした。ご不快な思いをさせてしまい申し訳ありません。
KSwordOfHaste

2018/03/22 01:58 編集

ここはプログラマーのQ&Aなのですが、プログラマーは普通「自分でソースを理解し、自分でデバッグする」という基本行動をとるということを知っておくとよいです。例え学校の課題であっても「自分でここまで調べたがこの点がわからない」というような具体的な質問ならアドバイスがつくこともあります。しかしソースだけ書いて自分でどうデバッグしたか、何がわからないのかを書いてない質問は「丸投げ」と見做され避けられます。なぜかというと回答する側は「質問者さんの課題をピンポイントで把握し、短いアドバイスをする」という意識でいるからです。時は金なりなのでいくら善意のある回答者でも、100行も200行もあるコードを10分20分かけて読んでデバッグしようとはおもわないわけです。質問の際には「ほとんど問題の核心にせまるまでは質問者さん自身で努力し」「どうしても突破できない点のみを尋ねる」のがよい質問のコツなのです。
Kana517

2018/03/22 02:12

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

2018/03/22 02:18 編集

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

2018/03/22 02:27

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

回答1

0

ベストアンサー

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

Java

1 private static void quickSort(int[] list, int first, int last) { 2 if (last > first) { 3 int pivotIndex = partition(list, first, last); 4 quickSort(list, first, pivotIndex - 1); 5 quickSort(list, pivotIndex + 1, last); 6 } 7 }

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

Java

1 for(int n = 10000; n < 1000000; n += 10000){ 2 3 ////////////////////////////////////////////////////////////// 4 for(int count = 0; count < numOfTimes; count++ ) {//2 5 //int n = 10000000; 6 //make a random array of size n 7 int array[] = new int[n]; 8

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

投稿2018/03/22 01:51

y_waiwai

総合スコア87719

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Kana517

2018/03/22 02:01

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問