ArrayListを使ったクイックソートのプログラムが作りたい

Question

前提・実現したいこと

お世話になります。

ArrayListに格納した数値をクイックソートで昇順にソートしたいです。
List内の一番左の数値をピボットとして数値を比較し、それを再起的に繰り返す事でソートしようとしたのですがエラーが出てしまいます。

発生している問題・エラーメッセージ

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
	at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)
	at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)
	at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248)
	at java.base/java.util.Objects.checkIndex(Objects.java:373)
	at java.base/java.util.ArrayList.get(ArrayList.java:426)
	at Quick.Quick(Quick.java:24)
	at Quick.Quick(Quick.java:35)

該当のソースコード

public class QuickSort {

	ArrayList<Integer> array = new ArrayList<Integer>();

	//クイックソート
	void Quick(ArrayList<Integer> array) {
		int size = array.size();

		//listの大きさが1なら再帰終了
		if (size == 1) return;

		ArrayList<Integer> L = new ArrayList<>(), R = new ArrayList<>();

		//一番左の値をピボットとして分割処理
		int P = array.get(0);
		for (int i=1; i<size; i++) {
			if (P > array.get(i)) {
				L.add(array.get(i));
			}else {
				R.add(array.get(i));
			}
		}

		//再帰
		Quick(L);
		Quick(R);

		array.clear();

        //分割した値を統合
		for (int i=0; i<L.size(); i++) {
			array.add(L.get(i));
		}

		array.add(P);

		for (int i=0; i<R.size(); i++) {
			array.add(R.get(i));
		}
	}
}

Comments

[LouiS0616]

『Quick』と『Quick1』が混在しているように見えますが、これは意図的ですか？

[ozwk]

array1 は何者でしょうか? 宣言もなしにいきなりコード上に現れます。

[nikaho]

すみません。こちらのミスです。

[退会済みユーザー]

クラス名と同じ名前のメソッド名は・・・・

[nikaho]

質問用に実際の名前と変更して書いています。困惑させてしまい申し訳ないです。修正しました。

[LouiS0616]

質問用に変数名を変更する意図が分かりません。

[nikaho]

クラス名に私的な名称が入っていたのでその部分を省きました。

[LouiS0616]

なるほど。確かにそれならば変更した方が良いでしょうね。
質問を投稿する際は、投稿するコードが元のコードと同じように振る舞うかどうか確認しておくとスムーズかも思います。

[nikaho]

元のコードと同じような振る舞いをするのは重要ですね。以後投稿の際に気をつけます。

Answer 1

再帰呼び出しする際はピボットを除去して下さい。
Lの要素が [ピボット, ピボット以下の数値, ...] になると同じパラメータで無限再帰します。

具体的には、次の手順を踏んで下さい。
0. L及びRには、ピボット以外の要素を加えるようにします。(0番目を飛ばせば良い)
0. LとRを統合する際に、ピボットも忘れずくっつけてやります。

---

なお『分割した値を統合』している部分についてはもっと簡単に書けます。

// Lの全要素をarrayに追加
for(...) { array.add(...); }   // List#forEachでも良い。
// ピボットを追加
array.add(P);
// Rの全要素をarrayに追加
...

List#addAllを利用しても良いでしょう。

Comments

[nikaho]

ピボットの除去は盲点でした！教えて下さりありがとうございます。
しかし、コードの方を修正したのですがまだエラーが出てしまうようで...

[LouiS0616]

分割した結果、長さ0のリストをソートしようとする場合があります。
ピボットの取得に失敗しArrayIndexOutOfBoundsException(範囲外アクセス)を引き起こしますね。

再帰の基底条件を見直す必要があります。

[LouiS0616]

なおLに値を追加する条件は P > array.get(i) ではなく P >= array.get(i) のままが良いです。
ここを > で比較してしまうとソートに失敗するケースがあります。どのような場合かはちょっと考えてみて下さい。

[追記]
...と思ったんですけど、どちらでも大丈夫でした。失礼しました。
同じ値が複数含まれるリストのソートに失敗する（同じ値が無視される）と思ったのですが、よく考えるとL.appendに取りこぼされる分がR.appendに移るだけなので問題無いですね。

[anndonut]

自分もArrayListでクイックソート書きました。staticメソッドですね。最初の要素をpivotするのであれば、ArrayListのIteratorを作ってpivotにnext()を食わせてからwhileで回せばスマートなのかと。あとはaddとaddAllが後ろにしか要素を追加できないのでleft, pivot, rightの順でかませてやればソート完了ですね。

Answer 2

-        if (size == 1) return;
+        if (size <= 1) return;

Answer 3

6年前に書いた突っ込みどころ満載のソース

import java.util.ArrayList;
import java.util.List;

public class QuickSort {

	public static <T extends Comparable<T>> List<T> sort(List<T> list) {
		List<T> retList = new ArrayList<>(list);
		return sort(retList, 0, retList.size() - 1);
	}

	public static <T extends Comparable<T>> List<T> sort(List<T> list, int left, int right) {

		if (left < right) {
			int i = left;
			int j = right;
			T pivot = med3(list.get(i), list.get(i + (j - i) / 2), list.get(j));
			while (true) {
				while (list.get(i).compareTo(pivot) < 0)
					i++;
				while (pivot.compareTo(list.get(j)) < 0)
					j--;
				if (i >= j)
					break;
				T a = list.get(i);
				T b = list.get(j);

				list.set(i, b);
				list.set(j, a);

				i++;
				j--;
			}
			sort(list, left, i - 1);
			sort(list, j + 1, right);
		}

		return list;
	}

	private static <T extends Comparable<T>> T med3(T x, T y, T z) {
		if (x.compareTo(y) < 0)
			if (y.compareTo(z) < 0)
				return y;
			else if (z.compareTo(x) < 0)
				return x;
			else
				return z;
		else if (z.compareTo(y) < 0)
			return y;
		else if (x.compareTo(z) < 0)
			return x;
		else
			return z;
	}

}

Comments

[退会済みユーザー]

おそらく「https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88」　のコードを java 化しただけだと思う・ｑ・

Answer 4

おーっと、ソート中にArrayListオブジェクトを作るとメモリ確保の時間がかかってクイックソートじゃなくなっちゃいますよ。配列もArrayListも大した変わらない（配列のほうが高速と思われ）ので、下記リンクのやり方でうまくいくと思います。

【Java】クイックソートのアルゴリズムのテスト

Comments

[LouiS0616]

後学のためお聞きしたいことがあります。
『メモリ確保の時間がかかってクイックソートじゃなくなっちゃいます』というのは、

・定義上、クイックソートでは無いということでしょうか？
あるいは、
・オーバーヘッドがかかって最早クイックでは無いよ、ということでしょうか？

[anndonut]

後者ですね。

[LouiS0616]

なるほど。
返信ありがとうございます。

[nikaho]

配列を使用した方が上手くいくことはわかっています。ネットに上がっているもののほとんどが配列を使用していますし...
リンク先のプログラムも拝見しています。

その上で個人的なこだわりというか、ArrayListを使ってみたいんです。
なので早さもあまり気にしていません。構造がわかればいいんです。

そういった意味で「クイックソートを作りたい」ではなく「ArrayListを使った...」とタイトルに書いています。

[anndonut]

そういうことだったんですね。すみませんでした。