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

Question

يقوم كل من الفرز السريع وheapsort بالفرز في المكان.ايهما افضل؟ما هي التطبيقات والحالات التي يفضل فيها أي منهما؟

Answer 1

هذه الورقة لديه بعض التحليل.

أيضا ، من ويكيبيديا:

المنافس الأكثر مباشرة في Quicksort هو Heapsort. عادةً ما تكون Heapsort أبطأ إلى حد ما من Quicksort ، ولكن أسوأ وقت تشغيل هو θ (Nlogn). عادةً ما تكون Quicksort أسرع ، على الرغم من أن هناك فرصة لأسوأ أداء للحالة إلا في متغير introsort ، والذي يتحول إلى أكواد عند اكتشاف حالة سيئة. إذا كان من المعروف مقدمًا أن يكون Heapsort ضروريًا ، فسيكون استخدامه بشكل مباشر أسرع من انتظار التبديل إليه.

Answer 2

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

لقد اختبرت الخوارزميات بنفسي ورأيت أن Quicksort لديه شيء مميز بالفعل.إنه يعمل بسرعة، أسرع بكثير من خوارزميات Heap وMerge.

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

باستخدام Heapsort، حتى لو كانت جميع بياناتك مرتبة بالفعل، فسوف تقوم بتبديل 100% من العناصر لترتيب المصفوفة.

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

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

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

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

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

بالنسبة لمعظم المواقف ، فإن وجود سريع مقابل أسرع قليلاً أمر غير ذي صلة ... أنت ببساطة لا تريد أبدًا أن تحصل على بطيئة في بعض الأحيان. على الرغم من أنه يمكنك تعديل Quicksort لتجنب الطريقة البطيئة ، إلا أنك تفقد أناقة Quicksort الأساسية. لذلك ، بالنسبة لمعظم الأشياء ، أفضّل فعليًا Heapsort ... يمكنك تنفيذه في أناقته البسيطة الكاملة ، وعدم الحصول على نوع بطيء أبدًا.

بالنسبة للمواقف التي تريدها في معظم الحالات ، قد يفضل Quicksort على Heapsort ، ولكن قد لا يكون أي من الإجابة الصحيحة. بالنسبة للمواقف الحرجة للسرعة ، يجدر فحص تفاصيل الوضع عن كثب. على سبيل المثال ، في بعض الشفرة الحرجة للسرعة ، من الشائع جدًا أن يتم فرز البيانات بالفعل أو قربها (وهي تفهرس حقول متعددة ذات صلة غالبًا ما تتحرك لأعلى ولأسفل معًا أو تتحرك لأعلى ولأسفل مقابل بعضها البعض ، لذلك بمجرد الفرز تلو الآخر ، يتم فرز الآخرين أو إما عكسيين أو إغلاق ... أي منهما يمكن أن يقتلوا Quicksort). في هذه الحالة ، قمت بتطبيقها لا ... بدلاً من ذلك ، قمت بتطبيق Smoothsors من Dijkstra ... وهو متغير Hepsort الذي يكون O (n) عندما يتم فرزه بالفعل أو قريب ... إنه ليس أنيقًا للغاية ، وليس من السهل فهمه ، لكن بسرعة ... اقرأ http://www.cs.utexas.edu/users/ewd/ewd07xx/ewd796a.pdf إذا كنت تريد شيئًا أكثر صعوبة في الترميز.

Answer 4

تعد Hybrids Quicksort-Heapsort Hybrids مثيرة للاهتمام أيضًا ، لأن معظمها يحتاج فقط إلى مقارنات n*log n في أسوأ الحالات (فهي مثالية فيما يتعلق بالفصل الأول من التقارب ، لذلك يتجنبون سيناريوهات أسوأ حالة من Quicksort) ، O (log n) مساحة إضافية ويحافظون على الأقل على "نصف" من السلوك الجيد لـ Quicksort فيما يتعلق بمجموعة من البيانات المرتبة بالفعل. يتم تقديم خوارزمية مثيرة للاهتمام للغاية بواسطة Dikert و Weiss In http://arxiv.org/pdf/1209.4214v1.pdf:

• حدد محور P كوسط عينة عشوائية من عناصر SQRT (N) (يمكن القيام بذلك في أكثر من 24 SQRT (N) من خلال خوارزمية Tarjan & Co ، أو 5 SQRT (N) من خلال العنكبوت الأكثر تفصيلا بكثير خوارزمية بعنوان Schonhage) ؛
• تقسيم صفيفك في جزأين كما في الخطوة الأولى من Quicksort ؛
• أكواد الجزء الأصغر واستخدم البتات الإضافية o (log n) لترميز كومة يكون فيها كل طفل يسار قيمة أكبر من شقيقه ؛
• استخرج بشكل متكرر جذر الكومة ، قم بتدوير أسفل الجذر الذي تركه الجذر حتى يصل إلى ورقة من الكومة ، ثم املأ lacune بعنصر مناسب أخذ من الجزء الآخر من الصفيف ؛
• تكرر على الجزء غير المتبقي من المصفوفة (إذا تم اختيار P كوسيط دقيق ، فلا يوجد عودة على الإطلاق).

Answer 5

شركات.بين quick sort و merge sort نظرًا لأن كلاهما نوع من الفرز الموضعي، فهناك فرق بين وقت تشغيل الحالة الأسوأ ووقت تشغيل الحالة الأسوأ للفرز السريع هو O(n^2) ولفرز الكومة لا يزال O(n*log(n)) وبالنسبة لكمية متوسطة من البيانات، سيكون الفرز السريع أكثر فائدة.نظرًا لأنها خوارزمية عشوائية، فمن المحتمل الحصول على الإجابات الصحيحة.في وقت أقل سيعتمد على موضع العنصر المحوري الذي تختاره.

لذلك أ

دعوة جيدة: أحجام L وG أقل من 3s/4

اتصال رديء: حجم واحد من L وG أكبر من 3s/4

بالنسبة للكميات الصغيرة، يمكننا استخدام نوع الإدراج، وبالنسبة لكميات كبيرة جدًا من البيانات، يمكننا استخدام نوع الكومة.

Answer 6

حسنًا ، إذا ذهبت إلى مستوى الهندسة المعمارية ... نستخدم بنية بيانات قائمة الانتظار في ذاكرة ذاكرة التخزين المؤقت. لذا ، فسيتم فرز ما هو متاح في قائمة الانتظار. فرز (باستخدام Array) قد يحدث حتى لا يكون الوالد موجودًا في الصفيف الفرعي المتاح في ذاكرة التخزين المؤقت ومن ثم يتعين عليه إحضارها في ذاكرة ذاكرة التخزين المؤقت ... والتي تستغرق وقتًا طويلاً. هذا هو الأفضل! 😀

Answer 7

نوع كومة يبني كومة ثم يستخرج بشكل متكرر العنصر الأقصى. أسوأ حالاتها هي O (n log n).

ولكن إذا كنت ترى أسوأ حالات نوع سريع, ، وهو O (N2) ، كنت تدرك أن النوع السريع سيكون خيارًا غير جيد للبيانات الكبيرة.

وهذا يجعل الفرز شيء مثير للاهتمام. أعتقد أن السبب في أن العديد من خوارزميات الفرز تعيش اليوم هو أن جميعها "الأفضل" في أفضل أماكنها. على سبيل المثال ، يمكن لفرز Bubble إجراء الفرز السريع إذا تم فرز البيانات. أو إذا عرفنا شيئًا عن العناصر المراد فرزها ، فربما يمكننا أن نفعل ما هو أفضل.

قد لا يجيب هذا على سؤالك مباشرة ، فكرت في إضافة سنتان.

Answer 8

Heapport لديه فائدة من وجود أسوأ حالة تشغيل o (n*log (n)) لذلك في الحالات التي من المحتمل أن تؤدي فيها Quicksort بشكل سيء (مجموعات البيانات التي يتم فرزها بشكل عام بشكل عام) ، يُفضل أن يكون الكثافة مفضلة كثيرًا.

Answer 9

يعد نوع الكومة رهانًا آمنًا عند التعامل مع مدخلات كبيرة جدًا. يكشف التحليل المقارب عن ترتيب نمو الكثافة في أسوأ الحالات Big-O(n logn), ، وهو أفضل من Quicksort Big-O(n^2) كأسوأ حالة. لكن، نوع كومة هو أبطأ إلى حد ما في الممارسة العملية على معظم الآلات من النوع السريع الذي تم تنفيذه. Heapsort هي أيضا ليست خوارزمية فرز مستقرة.

السبب في أن Heapsort أبطأ في الممارسة العملية من Quicksort يرجع إلى موقع أفضل للمرجع ("https://en.wikipedia.org/wiki/locality_of_reference") في Quicksort ، حيث تكون عناصر البيانات ضمن مواقع التخزين القريبة نسبيًا. الأنظمة التي تظهر موقعًا قويًا للمرجع هي مرشحين رائعين لتحسين الأداء. ومع ذلك ، يتعامل نوع الكومة مع قفزات أكبر. وهذا يجعل Quicksort أكثر ملاءمة للمدخلات الأصغر.

Answer 10

بالنسبة لي ، هناك فرق أساسي للغاية بين Heapsort و Quicksort: يستخدم الأخير عودة. في الخوارزميات العودية ، ينمو الكومة مع عدد العوالم. هذا لا يهم إذا ن صغير ، لكنني الآن أقوم بفرز مصفوفين مع ن= 10^9 !!. يستغرق البرنامج ما يقرب من 10 غيغابايت من ذاكرة الوصول العشوائي وأي ذاكرة إضافية ستجعل جهاز الكمبيوتر الخاص بي يبدأ في التبديل إلى ذاكرة القرص الظاهري. القرص الخاص بي هو قرص ذاكرة الوصول العشوائي ، ولكن لا يزال تبديله فرق كبير في السرعة. لذلك في statpack مشفرة في C ++ والتي تتضمن مصفوفات الأبعاد القابلة للتعديل ، مع الحجم غير معروف مقدمًا للمبرمج ، ونوع إحصائي غير بارمتر من الفرز ، أفضل أن أفضّل التثبيت لتجنب التأخيرات مع مصفوفات البيانات الكبيرة جدًا.

Answer 11

للإجابة على السؤال الأصلي ومعالجة بعض التعليقات الأخرى هنا:

لقد قارنت للتو تطبيقات الاختيار ، والسرعة ، والاندماج ، والكومة لترى كيف تتكدس ضد بعضهم البعض. الجواب هو أن جميعهم لديهم سلبياتهم.

TL ؛ DR: Quick هو أفضل نوع للأغراض العامة (سريعًا ومستقرًا ومعظمًا في الغالب) أنا شخصياً أفضل فرز الكومة على الرغم من أنني ما لم أكن بحاجة إلى نوع مستقر.

الاختيار - n^2 - إنه جيد حقًا لأقل من 20 عنصرًا أو نحو ذلك ، ثم يتفوق. ما لم يتم فرز بياناتك بالفعل ، أو جدًا تقريبًا. n^2 يحصل بطيئة حقا بسرعة حقا.

سريع ، في تجربتي ، ليس في الواقع الذي - التي سريع طوال الوقت. المكافآت لاستخدام الفرز السريع كنوع عام على الرغم من أنه سريع بشكل معقول ومستقر. إنها أيضًا خوارزمية في مكانها ، ولكن مع تنفيذها بشكل عام بشكل متكرر ، فإنها ستستغرق مساحة إضافية. كما يقع في مكان ما بين O (n log n) و o (n^2). يبدو أن التوقيت على نوع ما يؤكد ذلك ، خاصة عندما تقع القيم ضمن نطاق ضيق. إنها أسرع من فرز الاختيار على 10،000،000 عنصر ، ولكنه أبطأ من الدمج أو الكومة.

يتم ضمان دمج نوع O (n log n) لأن فرزه لا يعتمد على البيانات. إنها تفعل ما تفعله فقط ، بغض النظر عن القيم التي قدمتها لها. إنه مستقر أيضًا ، لكن الأنواع الكبيرة جدًا يمكن أن تفجر مكدتك إذا لم تكن حريصًا على التنفيذ. هناك بعض تطبيقات الدمج المعقدة في مكانها ، ولكن عمومًا تحتاج إلى مجموعة أخرى في كل مستوى لدمج قيمك. إذا كانت هذه المصفوفات تعيش على المكدس ، فيمكنك مواجهة المشكلات.

نوع الكومة هو الحد الأقصى O (n log n) ، ولكن في كثير من الحالات يكون أسرع ، اعتمادًا على المدى الذي تضطر إليه لرفع قيمك لأعلى الكومة العميقة. يمكن بسهولة تنفيذ الكومة في مكانها في الصفيف الأصلي ، لذلك لا يحتاج إلى ذاكرة إضافية ، وهي تكرارية ، لذلك لا تقلق بشأن فائض المكدس أثناء التكرار. ال تسربت الجانب السلبي إلى نوع الكومة هو أنه ليس نوعًا مستقرًا ، مما يعني أنه صحيح إذا كنت بحاجة إلى ذلك.