bit

部分クイックソート

久しぶりに勉強。配列の一部だけをソートする部分ソート(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 の間からピボットを取るようにする。