部分クイックソート
久しぶりに勉強。配列の一部だけをソートする部分ソート(partial sort)。
参考にしたのは、ぐぐって見つけた論文と、ロゼッタコードのページ。たぶんこれでいいと思うけど。
sortRecursively(array, 0, array.length - 1, lowerBound, upperBound); private static <T extends Compatible<T>> sortRecursively(T[] array, int leftEnd, int rightEnd, int lowerBound, int upperBound) { int pivotIdx = selectPivot(array, leftEnd, rightEnd); int[] lrIdx = splitArrayIntoLandU(array, leftEnd, rightEnd, pivotIdx); if (lowerBound < lrIdx[0]) { sortRecursively(array, leftEnd, lrIdx[0], lowerBound, upperBound); } if (lrIdx[1] < upperBound) { sortRecursively(array, lrIdx[1], rightEnd, lowerBound, upperBound); } } private static <T extends Comparable<T>> int[] splitArrayIntoLandU(T[] array, int leftEnd, int rightEnd, int pivotIndex) { T pivot = array[pivotIndex]; while(leftEnd<= rightEnd) { while (array[leftEnd].compareTo(pivot) < 0) { ++leftEnd; } while (pivot.compareTo(array[rightEnd]) < 0) { --rightEnd; } if (leftEnd <= rightEnd) { swap(array, leftEnd, rightEnd); ++leftEnd; --rightEnd; } } return new int[] {rightEnd, leftEnd}; }
これで lowerBound ~ upperBound の間だけがソートされる。メソッド selectPivot は leftEnd と rightEnd の間からピボットを取るようにする。