アルゴリズム手記(7)クイックソート

ついに経典の速い列に着いて、20世紀の科学と工程の分野の10大アルゴリズムの1つとして、60年代の発明以来、ずっといくつかの技師と科学者を引きつけてその改善に対して、今日私達は速い列のアルゴリズムとそのいくつかの改善案を分析します.
クイックソート
概要:高速ソートアルゴリズムも分治思想に基づくスキームであり、集計ソートとは異なり、その場ソートであり、長さNの配列ソートに要する時間とNlognを比例させることができ、私たちが学んだアルゴリズムはこの2つの利点を結びつけることができない.
高速ソートが流行しているのは、さまざまな入力データに適用され、一般的なアプリケーションでは他のアルゴリズムよりもずっと速いため、最も広範なアルゴリズムを使用している可能性があります.
分析:
速い列は分治の並べ替えアルゴリズムである.1つの配列を2つのサブ配列に分け、2つの部分を独立に並べ替え、2つのサブ配列が秩序化されると、配列全体が自然に秩序化されます.クイックソートでは、分割(Partition)の位置は配列の内容に依存し、このアルゴリズムの鍵は分割にあり、このプロセスは3つの条件を満たす必要があります.
1.あるjについて、a[j]はすでにスケジュールされている.
2.a[lo]からa[j-1]までのすべての要素はa[j]より大きくない.
3.a[j+1]からa[hi]までのすべての要素はa[j]より小さくない.
帰納法によれば、彼が正確に配列を並べ替えることができることを証明するのは難しくない.左サブ配列と右サブ配列が秩序化されている場合、左サブ配列、分割要素、右サブ配列からなる結果配列も秩序化されているに違いない.ソート前に順序が乱されるため、ランダム化アルゴリズムであり、アルゴリズムの性能特性を予測することが望ましい.
ここで切り分けの一般的な戦略は,まずa[lo]を切り分け要素として勝手に取り,次にそれ以上の要素が見つかるまで左から右へスキャンし,それ以下の要素が見つかるまで右から左へスキャンし,この2つの要素の位置を交換することである.このように続けると、ポインタiの要素が分割要素より大きくなく、右ポインタjの要素が分割要素より小さくなく、最後にiとjが出会ったときにa[lo]とa[j]を交換し、jに戻ることが保証される.
実装:

public class Quick

    {

        public static void sort(IComparable[] a)

        {

              RandomShuffle.shuffle(a);

            sort(a, 0, a.Length - 1);

        }

        private static void sort(IComparable[] a, int lo, int hi)

        {

            if (hi <= lo) return;

            int j = partition(a, lo, hi);

            sort(a, lo, j - 1);

            sort(a, j + 1, hi);

        }



        private static int partition(IComparable[] a, int lo, int hi)

        {

            int i = lo, j = hi + 1;

            IComparable v = a[lo];

            while (true)

            {

                while (less(a[++i], v)) if (i == hi) break;

                while (less(v, a[--j])) if (i == lo) break;

                if (i >= j) break;

                exch(a, i, j);

            }

            exch(a, lo, j);

            return j;

        }

        private static bool less(IComparable i, IComparable j)

        {

            return i.CompareTo(j) < 0;

        }

        private static void exch(IComparable[] a,int i, int j)

        {

            var temp=a[i];

            a[i] = a[j];

            a[j] = temp;

        }

        public static void test(int size)

        {

            var stopWatch = new Stopwatch(DateTime.Now);

            Data[] data = new Data[size];

            Random rd = new Random();

            for (int i = 0; i < size; i++)

            {

                data[i] = new Data { value = rd.Next(10000000) };

                Console.WriteLine(data[i]);

            }

            Console.WriteLine("After sort:");



            Quick.sort(data);

            for (int i = 0; i < size; i++)

            {

                Console.WriteLine(data[i]);

            }

            stopWatch.elapsedTime();

           

        }

        public static void Main(string[] args)

        {

            test(100);

        }

    }

注意点:
1.その場で切り分ける
補助配列を使用すると、分割は簡単に実現できますが、分割後の配列をコピーするコストは耐えられない可能性があります.これにより、アルゴリズムのソート速度が大幅に低下します.
2.境界を越えるな
分割要素が配列の中で最小または最大の要素である場合、走査配列が境界から飛び出しないことを確保する必要があり、このような状況を防止するために明確な検出を実現する必要がある.
3.ランダム性を保つ
配列要素の順序は乱され、そのすべてのサブ配列もランダムにソートされ、これは予測アルゴリズムの実行時間に重要であり、最悪の発生確率を低減することができる.
4.ループの終了
経験のあるプログラマーは、ループを終了するには特に注意が必要であることを知っています.迅速にソートされた分割ループも例外ではありません.一般的なエラーは、配列に分割要素の値と同じ値を含む可能性がある他の要素を考慮していないことです.
5.処理分割値が重複している場合
ここでの実装アルゴリズムでは,左側スキャンは分割値以上に遭遇した場合に停止することが望ましく,右側スキャンは分割値以下に遭遇した場合に停止する.これにより、いくつかの等値の要素が交換される可能性がありますが、いくつかの典型的なアプリケーションでは、アルゴリズムの実行時間が平方レベルになることを回避できます.
6.再帰終了
経験のあるプログラマーは、再帰がいつも終わることを保証するのにも気をつけなければならない.クイックソートの一般的なエラーの1つは、分割要素を正しい位置に配置することを保証できないことであり、プログラムが分割要素がちょうど最大または最小値である場合に無限の再帰に陥ることになります.
 
まとめ:
数学的には高速ソートについて詳しく分析されているので,その性能を正確に説明することができる.高速ソート分割法の内側ループは、配列要素と一定値をインクリメンタルインデックスで比較し、ソートアルゴリズムにこれよりも短い内側ループがあるとは考えにくい.
高速ソートのもう一つの利点は、その比較回数が少ないことであり、高速ソートが最良の場合は、毎回配列を半分にすることができ、この場合、分治再帰のCn=2 Cn/2+N式、すなわちCn~Nlognを満たすことができる.
迅速なソートには多くの利点がありますが、その基本的な実装には潜在的な欠点があります.バランスがとれていない場合、極めて非効率になります.我々が速い列の前に配列をランダムに乱すのは,このような状況を防止するためであり,これにより悪い分割状況の可能性を最小限に抑えることができる.