فرز سريع التفوق على الكومة

Question

كومة لديه نوع أسوأ الأحوال تعقيد O(nlogn) في حين فرز سريع له O(n^2).ولكن emperical أدلة القول فرز سريع متفوقة.لماذا هذا ؟

Answer 1

أحد العوامل الرئيسية هو أن QuickSort لديه أفضل محلة المرجعية - الشيء التالي الذي سيتم الوصول إليه عادة عادة قريبا في الذاكرة إلى الشيء الذي نظرت إليه فقط. على النقيض من ذلك، يقفز Heapsort حول أكثر بكثير. نظرا لأن الأمور التي تكون قريبة من ذلك، فمن المحتمل أن يتم تخزين مؤقتا معا، ويميل QuickSort إلى أن تكون أسرع.

ومع ذلك، QuickSort's الحالة الأسوأ الأداء أسوأ بكثير مما هو عليه. نظرا لأن بعض التطبيقات الهامة تتطلب ضمانات لأداء السرعة، فإن HeApSort هو الطريقة الصحيحة للذهاب لهذه الحالات.

Answer 2

Heapsort O(N log N) ضمان الخدمة, ما هو أفضل بكثير من أسوأ الأحوال في فرز سريع.Heapsort لا تحتاج إلى المزيد من الذاكرة على مجموعة أخرى إلى وضع البيانات المطلوبة كما هو مطلوب من قبل Mergesort.فلماذا لا توازي التطبيقات العصا مع فرز سريع?ما فرز سريع له ذلك خاصة على الآخرين تطبيقات?

لقد اختبرت خوارزميات نفسي و رأيت أن فرز سريع لديه شيء خاص حقا.فإنه يعمل بسرعة أسرع بكثير من كومة ودمج الخوارزميات.

سر فرز سريع هو:تقريبا لا لزوم لها عنصر مقايضة.السواب هو مضيعة للوقت.

مع Heapsort, حتى لو كان جميع البيانات الخاصة بك هو بالفعل أمر, أنت ذاهب إلى مبادلة 100% من العناصر من أجل المصفوفة.

مع Mergesort ، هو أسوأ من ذلك.كنت أريد أن أكتب 100% من عناصر آخر مجموعة والكتابة مرة أخرى في نسخة أصلية واحدة ، حتى إذا كانت البيانات أمرت بالفعل.

مع فرز سريع لا مبادلة ما أمرت بالفعل.إذا كانت البيانات الخاصة بك هو أمر تماما, يمكنك مبادلة أي شيء تقريبا!على الرغم من أن هناك الكثير من الاسئلة عن أسوأ الأحوال ، تحسن قليلا على اختيار محور آخر من الحصول على أول أو آخر عنصر من الصفيف ، يمكن تجنب ذلك.إذا كنت تحصل على محور من المتوسطة عنصر بين الأولى والأخيرة الأوسط العنصر هو suficient لتجنب أسوأ الأحوال.

ما هي متفوقة في فرز سريع ليس أسوأ الأحوال, ولكن أفضل الأحوال!في حال كنت تفعل نفس العدد من المقارنات, ok, ولكن يمكنك مبادلة أي شيء تقريبا.في متوسط حالة مبادلة جزء من العناصر, ولكن ليس كل العناصر ، كما في Heapsort و Mergesort.هذا هو ما يعطي فرز سريع أفضل وقت.أقل مبادلة أكثر سرعة.

تنفيذ أدناه في C# على جهاز الكمبيوتر يعمل على الإصدار وضع يدق مجموعة.نوعا من 3 ثوان مع الوسط المحوري ، 2 ثوان مع تحسين المحورية (نعم ، هناك النفقات العامة إلى المحورية).

static void Main(string[] args)
{
    int[] arrToSort = new int[100000000];
    var r = new Random();
    for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);

    Console.WriteLine("Press q to quick sort, s to Array.Sort");
    while (true)
    {
        var k = Console.ReadKey(true);
        if (k.KeyChar == 'q')
        {
            // quick sort
            Console.WriteLine("Beg quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            QuickSort(arrToSort, 0, arrToSort.Length - 1);
            Console.WriteLine("End quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
        else if (k.KeyChar == 's')
        {
            Console.WriteLine("Beg Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            Array.Sort(arrToSort);
            Console.WriteLine("End Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
    }
}

static public void QuickSort(int[] arr, int left, int right)
{
    int begin = left
        , end = right
        , pivot
        // get middle element pivot
        //= arr[(left + right) / 2]
        ;

    //improved pivot
    int middle = (left + right) / 2;
    int
        LM = arr[left].CompareTo(arr[middle])
        , MR = arr[middle].CompareTo(arr[right])
        , LR = arr[left].CompareTo(arr[right])
        ;
    if (-1 * LM == LR)
        pivot = arr[left];
    else
        if (MR == -1 * LR)
            pivot = arr[right];
        else
            pivot = arr[middle];
    do
    {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;

        if(left <= right)
        {
            int temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;

            left++;
            right--;
        }
    } while (left <= right);

    if (left < end) QuickSort(arr, left, end);
    if (begin < right) QuickSort(arr, begin, right);
}

Answer 3

هنا بضعة تفسيرات:

http://www.cs.auckland.ac.nz/software/AlgAnim/qsort3.html

http://users.aims.ac.za/~mackay/sorting/sorting.html

أساسا ، على الرغم أسوأ الأحوال سريعة النوع O(n^2) على متوسط أداء أفضل.:-)

Answer 4

تعني التدوين Big-o أن الوقت اللازم لفرز العناصر N يحدها الوظيفة c*n*log(n), ، أين c هو بعض العامل الثابت غير محدد. لا يوجد سبب لماذا ثابت c يجب أن تكون هي نفسها quicksort و heapsort. وبعد وبالتالي فإن السؤال الحقيقي هو: لماذا تتوقع أن تكون سريعة بنفس القدر؟

Quicksort كان دائما أسرع إلى حد ما من heapsort في الممارسة العملية، ولكن أصبح الفرق أكبر مؤخرا منذ ذلك الحين، كما ذكر من قبل، أصبحت محلية وصول الذاكرة مهمة للغاية لسرعة التنفيذ.

Answer 5

تعقيد الحالة المتوسط، وحقيقة أنه يمكنك اتخاذ خطوات بسيطة لتقليل خطر التعقيد الأسوأ في QuickSort (على سبيل المثال حدد المحور كمتوسطة من ثلاثة عناصر بدلا من موضع واحد محدد).