雑草SEの備忘録

[旧:東大卒SEの備忘録]東大を卒業し、SEとして働くことになった。備忘録的に作業を綴る。

クイックソートのソース(Java)

クイックソートアルゴリズムJavaで実現したときのソースです。
クイックソートってどんなものかっていうのは、他のサイトをあたってください。
軸の取り方はもう少し工夫しても良いかもしれません。平均の値をとるとか。

// クイックソートのメソッド
public static int[] quickSort(int[] input) {
	return quick(input, 0, input.length - 1);
}

private static int[] quick(int[] input, int left, int right) {
	int[] array = input;
	int currentLeft = left;
	int currentRight = right;

	// 要素数が1以下のときは、何もせず返却する
	if (array.length < 2)
		return array;

	// クイックソートの場合、軸の選び方は色々あるが、このメソッドでは
	// 軸は、currentLeftとcurrentRightの真ん中にある要素とする。
	int pivot = array[(currentLeft + currentRight) / 2];

	do {
		while (array[currentLeft] < pivot) {
			currentLeft++;
		}

		while (array[currentRight] > pivot) {
			currentRight--;
		}
		if (currentLeft <= currentRight) {
			int index1 = currentLeft++;
			int index2 = currentRight--;
			int temp = array[index1];
			array[index1] = array[index2];
			array[index2] = temp;
		}
	} while (currentLeft <= currentRight);

	if (left < currentRight)
		quick(array, left, currentRight);

	if (currentLeft < right)
		quick(array, currentLeft, right);
	return array;
}