java - これはクイックソートの正しい実装ですか?

Question

これが QuickSort の正しい実装であるかどうかを確認したいのですが、仕事をしているようですが、何か見逃していますか?

public class QuickSort implements Sorter {

public void sort(Comparable[] items) {
    QuickSort(items, 0, items.length - 1);
}

static void QuickSort(Comparable[] items, int a, int b) {
    int lo = a;
    int hi = b;
    if (lo >= hi) {
        return;
    }
    Comparable mid = items[(lo + hi) / 2];
    Comparable T;

    while (lo < hi) {
        while (items[lo].compareTo(mid)<0) {
            lo++;
        }
        while (mid.compareTo(items[hi])<0) {
            hi--;
        }
        if (lo < hi) {
            T = items[lo];
            items[lo] = items[hi];
            items[hi] = T;
        }
    }

    QuickSort(items, a, lo);
    QuickSort(items, lo == a ? lo + 1 : lo, b);

}

}

修繕：

private static void quickSort(Comparable[] items, int a, int b) {
    int i = a;
    int j = b;

    Comparable x = items[(a+ b) / 2];
    Comparable h;

    do {
        while (items[i].compareTo(x) < 0) {
            i++;
        }
        while (items[j].compareTo(x) > 0) {
            j--;
        }
        if (i <= j) {
            h = items[i];
            items[i] = items[j];
            items[j] = h;
            i++;
            j--;
        }
    } while (i <= j);

    if (a < j) {
        quickSort(items, a, j);
    }
    if (i < b) {
        quickSort(items, i, b);
    }
}

Answer 1

1 つの小さな点 - ここで int オーバーフローの可能性があります。

(ロー + ハイ) / 2

Answer 2

この機会に単体テストの書き方を学びましょう。（たとえば、「junit」でGoogle）。大きな配列を生成し、それらが適切に並べ替えられていることを確認します。たとえば、乱数で埋められた配列、0、1、Integer.MAX_INT で埋められた配列などです。整数オーバーフローやその他の奇妙なコーナーケースなどを誘発してみてください。

Answer 3

EDIT：Javaタグが欠けていて申し訳ありません...以下はC＃の一般的なクイックソートです...とにかく.netリーダーのためにここに残します...

一見良さそうに見えますが、こちらの汎用品はいかがでしょうか？

public class QuickSort<T> where T : IComparable<T>
{
    #region private variable to sort inplace
    readonly private IList<T> itms;
    #endregion private variable to sort inplace

    #region ctor
    private QuickSort() { } // Hide parameterless constructor
    /// <summary>
    /// Constructor requires IList<T> T must implement CompareTo() method.../>
    /// </summary>
    /// <param name="Lst">List<T> of elements to sort</param>
    public QuickSort(IList<T> Lst):this)() { itms = Lst; }
    #endregion ctor

    #region public sort method
    public void Sort() { Sort(0, itms.Count - 1); }
    /// <summary>
    /// Executes QuickSort algorithm
    /// </summary>
    /// <param name="L">Index of left-hand boundary of partition to sort</param>
    /// <param name="R">Index of right-hand boundary of partition to sort</param>
    private void Sort(long L, long R)
    {
        // Calls iSort (insertion-sort) for partitions smaller than 5 elements
        if (R - L < 4) iSort(L, R); 
        else
        {
            long i = (L + R) / 2, j = R - 1;
            // Next three lines to set upper and lower bounds
            if (itms[L].CompareTo(itms[i]) > 0) Swap(L, i);
            if (itms[L].CompareTo(itms[R]) > 0) Swap(L, R);
            if (itms[i].CompareTo(itms[R]) > 0) Swap(i, R);
            Swap(i, j);
            // --------------------------------
            T p = itms[j]; // p = itms[j] is pivot element
            i = L;
            while (true)
            {
                while (itms[++i].CompareTo(p) < 0) {}
                while (itms[--j].CompareTo(p) > 0) {}
                if (j < i) break;
                Swap(i, j);
            }
            Swap(i, R - 1);
            Sort(L, i);     // Sort  Left partition --  HERE WAS TYPO BUG
            Sort(i + 1, R); // Sort Right partition
        }
    }
    #endregion public sort method

    #region private Helper methods
    private void Swap(long L, long R)
    {
        T t = itms[L];
        itms[L] = itms[R];
        itms[R] = t;
    }
    private void iSort(long L, long R)
    {
        for (long i = L; i <= R; i++)
        {
            T t = itms[i];
            long j = i;
            while ((j > L) && (itms[j - 1].CompareTo(t) > 0))
            {
                itms[j] = itms[j - 1];
                j--;
            }
            itms[j] = t;
        }
    }
    #endregion private Helper methods
}