لماذا فرز سريع أفضل من mergesort?

https://stackoverflow.com/questions/70402

09-06-2019
|

سؤال

كنت سألت هذا السؤال من خلال مقابلة.كلاهما O(nlogn) ومع ذلك فإن معظم الناس استخدام فرز سريع بدلا من Mergesort.لماذا هذا ؟

المحلول

فرز سريع وقد O(n²) أسوأ وقت O(nسجلn) متوسط الحال وقت التشغيل.ومع ذلك, انها متفوقة على دمج النوع في العديد من السيناريوهات بسبب العديد من العوامل تؤثر على خوارزمية وقت التشغيل ، ، عندما أخذ كل منهم معا ، فرز سريع يفوز بها.

ولا سيما في كثير من الأحيان-نقلت وقت التشغيل من خوارزميات الفرز يشير إلى عدد من المقارنات أو عدد من مقايضة اللازمة لأداء لفرز البيانات.هذا هو في الواقع جيدة لقياس الأداء, خصوصا انها مستقلة عن الأجهزة الأساسية في التصميم.ولكن أشياء أخرى – مثل محلة المرجعية (أيهل نقرأ الكثير من العناصر التي هي على الأرجح في ذاكرة التخزين المؤقت؟) – أيضا أن تلعب دورا هاما على الأجهزة الحالية.فرز سريع على وجه الخصوص يتطلب القليل من مساحة إضافية والمعارض جيدة ذاكرة التخزين المؤقت المحلية ، وهذا يجعلها أسرع من دمج النوع في كثير من الحالات.

بالإضافة إلى ذلك, فإنه من السهل جدا تجنب فرز سريع أسوأ حالة تشغيل الوقت O(n²) بالكامل تقريبا باستخدام خيارا مناسبا من محور مثل قبض عليه عشوائيا (هذه استراتيجية ممتازة).

في الممارسة الحديثة العديد من التطبيقات فرز سريع (على وجه الخصوص libstdc++'s std::sort) هي في الواقع introsort, الذي النظرية أسوأ O(nسجلn) ، مثل دمج النوع.فإنه يحقق هذا عن طريق الحد من العودية عمق التحول إلى خوارزمية مختلفة (heapsort) بمجرد أن يتجاوز سجلn.

نصائح أخرى

العديد من الناس قد لاحظ متوسط الحال أداء فرز سريع أسرع من mergesort. ولكن هذا صحيح فقط إذا كنت على افتراض وقت ثابت الوصول إلى أي قطعة من الذاكرة على الطلب.

في ذاكرة الوصول العشوائي هذا الافتراض هو عموما ليست سيئة جدا (ليس دائما صحيح لأن من مخابئ ، ولكنها ليست سيئة للغاية).ومع ذلك إذا كان بنية البيانات الخاصة بك كبيرة بما يكفي للعيش على القرص ، ثم فرز سريع يحصل قتل من حقيقة أن متوسط القرص لا شيء مثل 200 عشوائية يسعى في الثانية.ولكن في نفس القرص لا يوجد لديه صعوبة في القراءة أو الكتابة ميغا بايت من البيانات في الثانية على التوالي.وهو بالضبط ما mergesort لا.

ولذلك إذا كانت البيانات قد يتم فرز على القرص, كنت حقا ترغب في استخدام بعض الاختلاف على mergesort.(عموما يمكنك فرز سريع sublists ، ثم تبدأ دمجها معا فوق بعض حجم العتبة.)

وعلاوة على ذلك إذا كان عليك أن تفعل أي شيء مع مجموعات البيانات من هذا الحجم ، فكر مليا في كيفية تجنب يسعى إلى القرص.فعلى سبيل المثال هذا هو السبب في أنه هو المعيار النصائح التي يمكنك إسقاط الفهارس قبل القيام كميات كبيرة من البيانات في قواعد البيانات ثم إعادة إنشاء الفهرس في وقت لاحق.الحفاظ على المؤشر خلال الحمل يعني تسعى باستمرار إلى القرص.وعلى النقيض من ذلك إذا قمت بإسقاط الفهارس ، ثم قاعدة البيانات يمكن إعادة إنشاء الفهرس أولا فرز المعلومات إلى التعامل مع (باستخدام mergesort بالطبع!) ومن ثم تحميله إلى BTREE datastructure للمؤشر.(بطرس هي بطبيعة الحال تبقى في النظام, حتى تتمكن من تحميل واحد من فرز البيانات مع قليل من يسعى إلى القرص.)

كان هناك عدد من المناسبات حيث فهم كيفية تجنب القرص يسعى واسمحوا لي أن معالجة البيانات وظائف يستغرق ساعات بدلا من أيام أو أسابيع.

في الواقع, فرز سريع O(n²).لها متوسط الحال تشغيل الوقت O(nlog(ن)), ولكن أسوأ O(n²) ، والذي يحدث عند تشغيله على قائمة تحتوي على عدة عناصر فريدة من نوعها.العشوائي يأخذ O(n).بالطبع, هذا لا يغير في أسوأ حال ، فقط يمنع المتطفلين من جعل نوعا ما يستغرق وقتا طويلا.

فرز سريع هو أكثر شعبية لأنها:

هو في مكان (MergeSort يتطلب ذاكرة إضافية الخطية إلى عدد من العناصر التي يتم فرزها).
وقد صغيرة مخفية المستمر.

"ومع ذلك فإن معظم الناس استخدام فرز سريع بدلا من Mergesort.لماذا هذا؟"

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

نعم فرز سريع مع الثلاثي partioning هو على الارجح واحدة من أفضل الغرض العام نوع الخوارزميات, ولكن لا يوجد الحصول على أكثر من حقيقة أن "سريعة" فرز الأصوات أقوى بكثير من "دمج" نوعا ما.

كما ذكر آخرون ، أسوأ حالة فرز سريع O(n^2) ، بينما mergesort و heapsort بالإقامة في O(nlogn).على متوسط الحال ، ومع ذلك ، كل ثلاثة هي O(nlogn);حتى انهم الغالبية العظمى من الحالات المماثلة.

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

أود أن أضيف أن من ثلاثة algoritms المذكورة حتى الآن (mergesort, فرز سريع و الكومة) فقط mergesort مستقرة.أي أن النظام لا تغيير تلك القيم التي لها نفس المفتاح.في بعض الحالات وهذا هو المرغوب فيه.

ولكن الحقيقة يجب أن تقال في المواقف العملية معظم الناس بحاجة فقط جيد متوسط الأداء و فرز سريع هو...سريع =)

كل نوع من خوارزميات لها صعودا وهبوطا.انظر مقالة ويكيبيديا عن خوارزميات الفرز للحصول على لمحة عامة جيدة.

من ويكيبيديا على فرز سريع:

فرز سريع أيضا تتنافس مع mergesort, العودية آخر نوع خوارزمية ولكن مع الاستفادة من أسوأ Θ(nlogn) وقت التشغيل.Mergesort مستقرة نوعا ، على عكس فرز سريع و heapsort ، ويمكن تتكيف بسهولة مع العمل على ربط قوائم قوائم كبيرة جدا المخزنة على بطيئة إلى الوصول إلى وسائل الإعلام مثل القرص التخزين أو شبكة المرفقة التخزين.على الرغم من فرز سريع يمكن أن تكون مكتوبة تعمل على القوائم المرتبطة ، تعاني من ضعف المحور الخيارات دون الوصول العشوائي.العيب الرئيسي من mergesort هو أنه عند التشغيل على المصفوفات ، فإنه يتطلب Θ(ن) مساعد الفضاء في أفضل حالة ، بينما البديل من فرز سريع في مكان التقسيم و الذيل العودية يستخدم فقط Θ(logn) الفضائية.(لاحظ أنه عندما تعمل على القوائم المتصلة ، mergesort فقط يتطلب صغيرة المستمر المبلغ من التخزين المساعدة.)

مو! فرز سريع ليس أفضل بل هو أيضا مناسبة ل نوع مختلف من التطبيق ، من mergesort.

Mergesort يستحق النظر إذا كانت السرعة هي جوهر سيئة أسوأ أداء لا يمكن السكوت عليها ، مساحة إضافية متوفرة.1

أنت ذكرت أنها "انهم على حد سواء O(nlogn) [...]".هذا هو الخطأ."فرز سريع يستخدم حوالي n^2/2 مقارنات في أسوأ الأحوال."1.

لكن الخاصية الأكثر أهمية حسب تجربتي هي سهلة التنفيذ من الوصول المتسلسل يمكنك استخدام حين الفرز عند استخدام لغات البرمجة مع ضرورة النموذج.

1 Sedgewick ، الخوارزميات

فرز سريع هو أسرع من خوارزمية الفرز في الممارسة ولكن لديها عدد من الحالات المرضية التي يمكن أن تجعل من أداء بسوء O(n2).

Heapsort مضمونة لتشغيل في O(n*ln(n)) و يتطلب فقط محدود تخزين إضافية.ولكن هناك العديد من الاستشهادات من العالم الحقيقي الاختبارات التي تبين أن heapsort هو ملحوظ أبطأ من فرز سريع في المتوسط.

تفسير ويكيبيديا هو:

عادة فرز سريع أسرع بشكل كبير في الممارسة العملية من غيرها من Θ(nlogn) الخوارزميات ، لأن الحلقة الداخلية يمكن أن تنفذ على نحو فعال على معظم أبنية ، وفي معظم البيانات في العالم الحقيقي فمن الممكن لجعل خيارات التصميم التي تقلل من احتمال اشتراط الدرجة الثانية من الوقت.

فرز سريع

Mergesort

أعتقد أن هناك أيضا قضايا مع كمية التخزين اللازمة Mergesort (وهو Ω(ن)) أن فرز سريع التنفيذ لا يكون.في أسوأ الأحوال ، فهي نفس المبلغ من حسابي الوقت ، ولكن mergesort يتطلب المزيد من التخزين.

فرز سريع ليس أفضل من mergesort.مع O(n^2) (أسوأ الأحوال التي نادرا ما يحدث) ، فرز سريع يحتمل أن تكون أبطأ بكثير O(nlogn) من دمج النوع.فرز سريع أقل النفقات العامة ، وذلك مع الصغيرة ن و أجهزة الكمبيوتر بطيء ، هو أفضل.ولكن أجهزة الكمبيوتر سريع جدا اليوم أن النفقات الإضافية من mergesort لا يكاد يذكر ، وخطر جدا بطيئة فرز سريع تفوق ضئيلة النفقات العامة من mergesort في معظم الحالات.

بالإضافة إلى ذلك ، mergesort يترك البنود مع مفاتيح متطابقة في ترتيبها الأصلي ، سمة مفيدة.

أود أن أضيف إلى القائمة كبيرة إجابات بعض الرياضيات حول كيفية فرز سريع ينفذ عندما متباينة عن أفضل حال و كيف يحتمل هذا الذي آمل أن تساعد الناس على فهم أفضل قليلا لماذا O(n^2) القضية ليست من قلق حقيقي في تطبيقات أكثر تطورا من فرز سريع.

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

1) عدد قليل من المفاتيح الموجودة في البيانات.Dataset من كل نفس القيمة نوع في ن^2 على الفانيليا 2-قسم فرز سريع لأن كل القيم ما عدا المحور موقع توضع على جانب واحد في كل مرة.الحديثة تطبيقات معالجة ذلك من خلال طرق مثل استخدام 3-قسم نوعا ما.هذه أساليب تنفيذها على مجموعة بيانات من كل نفس القيمة في O(n) مرة.وذلك باستخدام مثل هذه التنفيذ يعني أن المدخلات مع عدد قليل من المفاتيح في الواقع يحسن الأداء الوقت لم يعد مصدر قلق.

2) سيئة للغاية محور الاختيار يمكن أن يسبب أسوأ الأحوال الأداء.في حالة مثالية ، المحورية دائما سوف يكون مثل هذا أن 50% من البيانات أقل و 50% من البيانات أكبر ، بحيث الإدخال سيتم تقسيم في نصف خلال كل التكرار.هذا يعطينا ن مقارنات مقايضة مرات تسجيل الدخول-2(ن) recursions O(n*logn) مرة.

وكم غير مثالية محور الاختيار يؤثر على التنفيذ الوقت ؟

دعونا النظر في الحالة التي يكون فيها محور باستمرار اختياره مثل أن 75% من البيانات على جانب واحد من محور.انها لا تزال O(n*logn) ولكن الآن قاعدة السجل قد تغير إلى 1/0.75 أو 1.33.العلاقة في الأداء عند تغيير قاعدة دائما ثابت ممثلة سجل(2)/log(newBase).في هذه الحالة, أن الثابت هو 2.4.حتى هذه النوعية من محور الاختيار يأخذ 2.4 مرة أكثر من مثالية.

كيف بسرعة هل هذا أسوأ من ذلك ؟

ليست سريعة جدا حتى محور الاختيار يحصل (باستمرار) سيئة جدا:

50% على جانب واحد:(الحالة المثالية)
75% على جانب واحد:2.4 مرات طالما
90% على جانب واحد:6.6 مرات طالما
95% على جانب واحد:13.5 مرات طالما
99% على جانب واحد:69 مرات طالما

ونحن نقترب 100% على جانب واحد سجل جزء من تنفيذ النهج ن و تنفيذ كامل مقارب النهج O(n^2).

في السذاجة تنفيذ فرز سريع, حالات مثل مجموعة فرزها (1 العنصر المحوري) أو عكس مجموعة مرتبة (على آخر عنصر محوري) سوف تنتج أسوأ O(n^2) وقت التنفيذ.بالإضافة إلى ذلك, تطبيقات مع التنبؤ بها محور الاختيار يمكن أن تتعرض إلى هجوم حجب الخدمة عن طريق البيانات التي تم تصميمها لإنتاج أسوأ الأحوال التنفيذ.الحديثة تطبيقات تجنب هذا عن طريق مجموعة متنوعة من الأساليب مثل العشوائي البيانات قبل فرز واختيار متوسط 3 اختيارها عشوائيا إلخ.مع هذه العشوائية في المزيج ، لدينا 2 الحالات:

الصغيرة مجموعة البيانات.أسوأ الحالات هي في حدود المعقول ولكن O(n^2) ليست كارثية بسبب n هي صغيرة بما يكفي أن ن^2 هو أيضا صغيرة.
مجموعة كبيرة من البيانات.أسوأ حالة ممكنة من الناحية النظرية ولكن ليس في الممارسة العملية.

كيف يحتمل نحن نرى رهيب الأداء ؟

وهناك احتمالات بزوال صغيرة.دعونا النظر في نوع من 5000 القيم:

افتراضية لدينا تنفيذ اختيار محور باستخدام متوسط 3 اختيارها عشوائيا الفهارس.ونحن سوف تنظر في محاور في 25%-75% مجموعة أن تكون "جيدة" والمحاور التي هي في 0%-25% أو 75%-100% مجموعة أن تكون "سيئة".إذا كنت تبحث في احتمال التوزيع باستخدام متوسط 3 عشوائية فهارس كل العودية لديه 11/16 فرصة تنتهي مع المحور.دعونا نجعل 2 المحافظ (كاذبة) الافتراضات إلى تبسيط الرياضيات:

جيد محاور هي دائما بالضبط في 25%/75% تقسيم العمل في 2.4*الحالة المثالية.ونحن لم تحصل على مثالية تقسيم أو أي تقسيم أفضل من 25/75.
سيئة محاور هي دائما أسوأ الأحوال أساسا تساهم شيء إلى الحل.

لدينا فرز سريع التنفيذ سوف تتوقف عند n=10 و التبديل إلى نوع الإدراج ، لذلك نحن بحاجة 22 25%/75% المحورية أقسام إلى كسر 5000 قيمة الإدخال أسفل ذلك بكثير.(10*1.333333^22 > 5000) أو نطلب 4990 أسوأ الأحوال محاور.نضع في اعتبارنا أنه إذا تتراكم علينا 22 جيدة محاور في أي نقطة ثم نوع ستكمل حتى أسوأ الأحوال أو أي شيء بالقرب منه يتطلب للغاية سوء الحظ.إذا أخذنا 88 recursions فعلا تحقيق 22 جيدة محاور اللازمة لفرز وصولا إلى n=10, التي من شأنها أن تكون 4*2.4*الحالة المثالية أو حوالي 10 مرات وقت تنفيذ حالة مثالية.كيف المرجح هو أننا لا تحقيق مطلوب 22 جيدة محاور بعد 88 recursions?

ثنائية التوزيعات الاحتمالية يمكن الإجابة على هذا الجواب عن 10^-18.(ن 88 ، ك 21, p 0.6875) المستخدم الخاص بك هو حوالي ألف مرات أكثر من المحتمل أن يكون ضرب من قبل البرق في 1 ثانية فإنه يأخذ فوق [نوع] من هم أن نرى أن 5,000 البند نوع تشغيل أي أسوأ من ذلك من 10*الحالة المثالية.هذه فرصة يحصل أصغر كما dataset يحصل على أكبر.وهنا بعض مجموعة أحجام وما يقابلها من فرص لتشغيل أكثر من 10*مثالية:

مجموعة من 640 البنود:10^-13 (يتطلب 15 pivot نقطة من أصل 60 يحاول)
مجموعة من 5 ، 000 البنود:10^-18 (يتطلب 22 جيدة محاور من أصل 88 يحاول)
مجموعة من 40 ، 000 البنود:10^-23 (يتطلب 29 جيدة محاور من أصل 116)

تذكر أن هذا هو مع 2 افتراضات متحفظة التي هي أسوأ من الواقع.لذا الأداء الفعلي هو أفضل من ذلك ، والتوازن المتبقية احتمال أقرب إلى المثالية من لا.

أخيرا, كما ذكر آخرون حتى هذه بعبثية المرجح الحالات يمكن القضاء عليها عن طريق التحول إلى كومة النوع إذا كان العودية كومة يذهب عميقا جدا.حتى TLDR هو أن جيد تطبيقات فرز سريع, أسوأ الأحوال لا وجود له في الواقع لأنه تم تصميم و تنفيذ يكمل في O(n*logn) مرة.

الجواب يميل قليلا نحو فرز سريع ث.r.t التغييرات التي أدت مع DualPivotQuickSort عن القيم البدائية .يتم استخدامه في جافا 7 إلى نوع في java.util.المصفوفات

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.

يمكنك العثور على JAVA7 implmentation هنا - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

زيادة رهيبة القراءة على DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

في نوع دمج العامة الخوارزمية:

النوع اليسار الفرعية مجموعة
نوع حق الفرعية مجموعة
دمج 2 فرز الفرعية المصفوفات

في المستوى العلوي, دمج 2 فرز sub-المصفوفات ينطوي على التعامل مع عناصر N.

مستوى واحد دون ذلك ، كل تكرار الخطوة 3 ينطوي على التعامل مع N/2 من العناصر, ولكن عليك أن تكرر هذه العملية مرتين.إذا كنت لا تزال تتعامل مع 2 * N/2 == N العناصر.

واحد مستوى أقل من ذلك أنت دمج 4 * N/4 == N العناصر ، وهلم جرا.كل عمق في العودية كومة ينطوي على دمج نفس العدد من العناصر في جميع يدعو إلى هذا العمق.

تعتبر سريعة نوعا ما خوارزمية بدلا من ذلك:

اختيار النقطة المحورية
مكان النقطة المحورية في المكان الصحيح في مجموعة ، مع كل عناصر أصغر إلى اليسار, و أكبر العناصر إلى اليمين
النوع اليسار-المصفوفة الفرعية
نوع الحق-المصفوفة الفرعية

في المستوى العلوي, كنت تتعامل مع مجموعة من حجم N.ثم اختيار واحد النقطة المحورية ، ووضعها في موقعها الصحيح ، ومن ثم يمكن تجاهله تماما عن بقية الخوارزمية.

واحد مستوى أقل من أن كنت تتعامل مع 2 sub-المصفوفات التي لها مجتمعة حجم N-1 (أي طرح في وقت سابق النقطة المحورية).يمكنك اختيار النقطة المحورية لكل الفرعية مجموعة مما يأتي ما يصل إلى 2 إضافية النقاط المحورية.

واحد مستوى أقل من أن كنت تتعامل مع 4 sub-المصفوفات جنبا إلى جنب مع حجم N-3, لنفس الأسباب المذكورة أعلاه.

ثم N-7...ثم N-15...ثم N-32...

عمق العودية كومة لا يزال نفسه تقريبا (logN).مع نوع دمج أنت دائما التعامل مع N-عنصر دمج جميع أنحاء كل مستوى من العودية المكدس.مع سريعة نوعا ما على الرغم من عدد من العناصر التي تتعامل مع ينتقص كما تذهب إلى أسفل المكدس.على سبيل المثال ، إذا كنت ننظر في عمق منتصف الطريق من خلال العودية كومة عدد من عناصر أنت تتعامل مع N - 2^((logN)/2)) == N - الجذر التربيعي(ن).

تنويه:على نوع دمج لأنك تقسيم مجموعة في 2 تساوي بالضبط قطع في كل مرة ، العودية العمق هو بالضبط logN.على السريع نوعا ما, لأن النقطة المحورية من غير المرجح أن تكون بالضبط في منتصف مجموعة وعمق العودية المكدس قد يكون أكبر قليلا من logN.أنا لم تفعل الرياضيات أن دور هذا العامل والعامل هو موضح أعلاه, في الواقع تلعب في الخوارزمية التعقيد.

على عكس دمج النوع سريعة النوع لا يستخدم auxilary الفضاء.في حين أن دمج النوع يستخدم auxilary الفضاء O(n).ولكن دمج النوع أسوأ حالة التعقيد وقت O(nlogn) في حين أن أسوأ الأحوال تعقيد من نوع سريع O(n^2) والذي يحدث عندما المصفوفة هو بالفعل يتم فرز.

في حين انهم على حد سواء في نفس الطبقة تعقيد, هذا لا يعني كلاهما لديهم نفس وقت التشغيل.فرز سريع عادة ما تكون أسرع من mergesort فقط لأنه من الأسهل إلى رمز ضيق تنفيذ عمليات فإنه لا يمكن أن تذهب بشكل أسرع.لأن ذلك فرز سريع عموما أسرع الناس استخدامه بدلا من mergesort.

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

فرز سريع لديه أفضل متوسط الحال التعقيد لكن في بعض التطبيقات هو خيار خاطئ.فرز سريع عرضة هجمات الحرمان من الخدمة.إذا كان مهاجم يمكن اختيار المدخلات إلى فرز ، وانه يمكن بسهولة إنشاء مجموعة أن يأخذ أسوأ الأحوال الوقت تعقيد o(n^2).

Mergesort متوسط حالة التعقيد أسوأ الأحوال التعقيد هي نفسها ، وعلى هذا النحو لا يعانون من نفس المشكلة.هذه المنشأة السياحية من نوع دمج أيضا يجعلها الاختيار الأمثل أنظمة الوقت الحقيقي - على وجه التحديد لأنه لا يوجد الحالات المرضية التي تتسبب في تشغيل الكثير أبطأ بكثير.

أنا مروحة أكبر من Mergesort من أنا من فرز سريع لهذه الأسباب.

لماذا فرز سريع هو جيد ؟

فرز سريع يأخذ N^2 في أسوأ الأحوال و NlogN متوسط الحال.أسوأ حالة تحدث عندما يتم فرز البيانات.هذا يمكن تخفيفها عن طريق خلط عشوائي قبل الفرز بدأت.
فرز سريع لا يأخذ الذاكرة الإضافية التي تؤخذ عن طريق دمج النوع.
إذا كانت قاعدة بيانات كبيرة و هناك بنود مماثلة ، التعقيد من فرز سريع يقلل باستخدام 3 طريقة التقسيم.أكثر من أي من البنود متطابقة أفضل نوع.إذا كانت جميع العناصر متطابقة ، أنواع في الزمن الخطي.[هذا هو الافتراضي التنفيذ في معظم المكتبات]

هو فرز سريع دائما أفضل من Mergesort?

لا حقا.

Mergesort مستقرة ولكن فرز سريع لا.حتى إذا كنت بحاجة إلى الاستقرار في الإخراج ، يمكنك استخدام Mergesort.الاستقرار مطلوب في العديد من التطبيقات العملية.
ذاكرة رخيصة في الوقت الحاضر.حتى إذا اضافية الذاكرة المستخدمة من قبل Mergesort ليست حرجة إلى التطبيق الخاص بك, ليس هناك أي ضرر في استخدام Mergesort.

ملاحظة: في جافا ، المصفوفات.نوع() يستخدم وظيفة فرز سريع على أنواع البيانات البدائية و Mergesort لكائن أنواع البيانات.لأن الأشياء تستهلك الذاكرة العامة ، وذلك بإضافة القليل من النفقات العامة بالنسبة Mergesort قد لا يكون هناك أي مشكلة بالنسبة نظر الأداء.

المرجعية:مشاهدة فرز سريع أشرطة الفيديو من الأسبوع 3 ، برينستون خوارزميات الحال في كورسيرا

نوع سريع هو أسوأ الأحوال O(n^2) ، ومع ذلك ، فإن متوسط الحال باستمرار يؤدي دمج النوع.كل خوارزمية O(nlogn), ولكن عليك أن تتذكر أنه عندما نتحدث عن يا كبير نترك قبالة أقل تعقيد العوامل.نوع سريع وقد تحسينات كبيرة على دمج النوع عندما يتعلق الأمر إلى عوامل ثابتة.

دمج النوع يتطلب أيضا O(2n) الذاكرة ، في حين سريعة نوعا ما يمكن القيام به في مكان (لا تتطلب سوى O(n)).هذا هو سبب آخر سريعة النوع المفضل عموما على دمج النوع.

معلومات اضافية:

أسوأ حالة سريعة النوع يحدث عندما يكون محور هو سوء اختيار.النظر في المثال التالي:

[5, 4, 3, 2, 1]

إذا كان المحور هو اختيار أصغر أو أكبر عدد في المجموعة ثم نوع سريع في O(n^2).احتمال اختيار عنصر في أكبر أو أصغر من 25% من القائمة هو 0.5.أن يعطي خوارزمية 0.5 فرصة جيدة المحورية.إذا نحن توظيف نموذجية محور اختيار خوارزمية (ويقول اختيار عنصر عشوائي) لدينا 0.5 فرصة اختيار جيد المحورية لكل خيار من محور.على مجموعات كبيرة الحجم احتمال دائما اختيار الفقراء المحور هو 0.5 * ن.وبناء على هذا الاحتمال سريعة النوع هو الكفاءة المتوسطة (النموذجية) حالة.

وهذا هو قديمة جدا السؤال ، ولكن منذ تعاملت مع كل الآونة الأخيرة هنا هي بلدي 2c:

دمج النوع يحتاج في المتوسط ~ N log N المقارنات.بالفعل (تقريبا) فرز فرز المصفوفات هذا يحصل وصولا الى 1/2 N log N, منذ حين دمج نحن (تقريبا) دائما حدد "اليسار" جزء 1/2 N من المرات ثم نسخ صحيح 1/2 N العناصر.بالإضافة إلى ذلك لا يمكن التكهن بالفعل فرز الإدخال يجعل المعالج فرع توقع تألق ولكن التخمين تقريبا جميع الفروع بشكل صحيح, وبالتالي منع أنابيب الأكشاك.

نوع سريع في المتوسط يتطلب ~ 1.38 N log N المقارنات.فإنه لا تستفيد كثيرا من فرز بالفعل مجموعة في الشروط من المقارنات (ومع ذلك في شروط مقايضة وربما من حيث فرع التوقعات داخل وحدة المعالجة المركزية).

بلدي معايير حديثة نسبيا المعالج يظهر ما يلي:

عند المقارنة الوظيفة هي وظيفة رد الاتصال (مثل في qsort() libc التنفيذ) فرز سريع أبطأ من mergesort بنسبة 15% على مدخلات عشوائية و 30% بالنسبة بالفعل مجموعة مرتبة 64 بت الاعداد الصحيحه.

من ناحية أخرى إذا المقارنة ليست الاستدعاء ، تجربتي أن فرز سريع يتفوق mergesort بنسبة تصل إلى 25%.

ومع ذلك إذا كان الخاص بك (كبير) مجموعة لديها عدد قليل جدا من القيم الفريدة, دمج النوع يبدأ الحصول على فرز سريع في أي حال.

لذا ربما خلاصة القول هي:إن المقارنة غير مكلفة (مثلا ، وظيفة رد الاتصال ، مقارنة السلاسل ، مقارنة العديد من أجزاء الهيكل في الغالب الحصول على الثانية-الثالثة-وإيابا "إذا" لجعل الفرق) - هناك احتمالات بأن سوف يكون أفضل مع دمج النوع.أبسط المهام فرز سريع سوف يكون أسرع.

وقال أن كل ما سبق صحيح:- فرز سريع يمكن ن^2 ولكن Sedgewick يدعي أنه جيد العشوائية تنفيذ المزيد من فرص أداء جهاز الكمبيوتر فرز أن يكون ضرب من قبل البرق من الذهاب N^2 - Mergesort يتطلب مساحة إضافية

عندما جربت كل خوارزميات الفرز ، عن طريق حساب عدد من دعوات متكررة, فرز سريع باستمرار أقل دعوات متكررة من mergesort.لأنه فرز سريع وقد محاور ومحاور ليست مدرجة في القادم دعوات متكررة.أن طريقة فرز سريع يمكن أن تصل إلى العودية حالة قاعدة أكثر أسرع من mergesort.

كل شيء يجري على قدم المساواة ، أتوقع معظم الناس إلى استخدام كل ما هو الأكثر سهولة المتاحة ، والتي تميل إلى أن تكون qsort(3).بخلاف ذلك فرز سريع هو معروف أن تكون سريعة جدا على المصفوفات ، مثل mergesort هو الخيار المشترك على القوائم.

ما يحيرني هو السبب في أنه من النادر جدا أن نرى radix أو دلو النوع.إنهم O(n) على الأقل على القوائم المرتبطة وكل ما يتطلبه الأمر هو بعض طريقة تحويل المفتاح إلى عدد ترتيبي.(سلاسل يطفو تعمل على ما يرام.)

أنا أفكر في السبب لا علاقة له كيف علم الحاسوب تدريسها.حتى أن تثبت لي المحاضر في تحليل خوارزمية أنه كان في الواقع من الممكن النوع أسرع من O(n log(n)).(كان دليلا على أنه لا يمكن أن مقارنة النوع أسرع من O(n log(n)), وهو صحيح.)

في أخبار أخرى, يطفو يمكن فرزها حسب الاعداد الصحيحه ، ولكن لديك لتحويل الأرقام السالبة حول بعد ذلك.

تحرير:في الحقيقة هنا حتى أكثر شراسة طريقة لفرز يطفو كما الصحيحه: http://www.stereopsis.com/radix.html.علما بأن بت التقليب خدعة يمكن استخدامها بغض النظر عن خوارزمية الفرز يمكنك فعلا استخدام...

من الصعب أن أقول.أسوأ من MergeSort هو n(log2n)-n+1 دقيقة إذا كان n = 2^k(لقد ثبت بالفعل هذا).و أي ن ، فمن بين (ن إل جي n - n + 1) (n lg n + n + O(lg n)).ولكن من أجل فرز سريع,أفضل حالاتها هو nlog2n(أيضا ن = 2^k).إذا قمت بتقسيم Mergesort قبل فرز سريع ، فإنه يساوي واحد عندما يكون n هو لانهائي.حتى إنه كما لو كان أسوأ الأحوال من MergeSort هو أفضل من أفضل حالة فرز سريع,لماذا نستخدم فرز سريع?ولكن تذكر ، MergeSort ليست في مكانها ، تتطلب 2n memeroy الفضاء.و MergeSort تحتاج أيضا إلى القيام بالعديد من مجموعة النسخ التي لا تدرج في تحليل الخوارزمية.في كلمة واحدة ، MergeSort هو حقا faseter من فرز سريع في هناك نظرية ، ولكن في الواقع تحتاج إلى النظر في memeory الفضاء تكلفة مجموعة نسخ الاندماج هو أبطأ من نوع سريع.لقد صنعت التجربة حيث أعطيت 1000000 أرقام في جافا عشوائي من قبل فئة ، واستغرق 2610ms قبل mergesort,1370ms قبل فرز سريع.

إضافات صغيرة سريعة مقابل دمج أنواع.

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

على سبيل المثال , نحن فرز العناصر باستخدام بروتوكول شبكة الاتصال على ملقم بعيد.

أيضا في حاويات مخصصة مثل "قائمة مرتبطة" ، لا فائدة من نوع سريع.
1.دمج النوع على قائمة مرتبطة ، لا تحتاج إلى ذاكرة إضافية.2.الوصول إلى العناصر في نوع سريع ليست متتابعة (في الذاكرة)

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

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

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

على الرغم من أن كلا خوارزميات الفرز متوسط التعقيد O(NlogN) ، وعادة الناس العاديين المهام يستخدم صفيف التخزين ، ولهذا السبب سريعة النوع يجب أن تكون الخوارزمية الاختيار.

تحرير:أنا فقط وجدت أن دمج النوع الأسوأ/أفضل/avg الحالة هو دائما nlogn ، ولكن نوع سريع يمكن أن تختلف من n2(أسوأ الأحوال عندما عناصر فرز بالفعل) إلى nlogn(متوسط/أفضل حال عندما محور دائما يقسم مجموعة نصفين).

النظر في الزمان والمكان التعقيد على حد سواء.من أجل دمج النوع :الوقت التعقيد :O(nlogn) , مساحة التعقيد :O(nlogn)

سريعة النوع :الوقت التعقيد :O(n^2) , مساحة التعقيد :O(n)

الآن كلاهما الفوز في واحدة scenerio لكل منهما.ولكن باستخدام عشوائية محور يمكنك دائما تقريبا تقليل تعقيد وقت سريع نوعا O(nlogn).

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

في c/c++ الأرض عندما لا تستخدم حاويات stl, أنا أميل إلى استخدام فرز سريع, لأنها بنيت في وقت التشغيل ، في حين mergesort لا.

لذلك أعتقد أنه في كثير من الحالات ، هو ببساطة الطريق الأقل مقاومة.

وبالإضافة إلى ذلك الأداء يمكن أن يكون أعلى من ذلك بكثير مع نوع سريع, على الحالات التي يكون فيها كامل بيانات لا تنسجم مع مجموعة العمل.

واحدة من السبب هو أكثر فلسفية.فرز سريع هو أعلى->أسفل الفلسفة.مع ن عناصر نوعا ما ، وهناك n!الاحتمالات.مع 2 أقسام من m & n-m والتي هي حصرية عدد من الاحتمالات النزول في عدة أوامر من حجم.m!* (n-m)!هو أصغر من عدة أوامر من n!وحده.تخيل 5!مقابل 3!*2!.5!10 مرات أكثر الاحتمالات من أقسام 2 من 2 و 3 لكل منهما .واستقراء إلى 1 مليون مضروب مقابل 900K!*100K!مقابلوذلك بدلا من القلق حول وضع أي أمر ضمن مجموعة أو قسم فقط فرض النظام على مستوى أوسع في أقسام والحد من إمكانيات داخل القسم.أي النظام الذي أنشئ في وقت سابق ضمن مجموعة سوف تكون منزعجة في وقت لاحق إذا كان الأقسام أنفسهم لا يستبعد بعضها بعضا.

أي من أسفل إلى أعلى من أجل نهج مثل دمج النوع أو الكومة مثل العمال أو الموظفين نهج واحد حيث يبدأ مقارنة على المستوى المجهري في وقت مبكر.لكن هذا الأمر لا بد أن يكون المفقودة في أقرب وقت عنصر بينهما وجدت في وقت لاحق.هذه المناهج هي مستقرة جدا & للغاية يمكن التنبؤ بها ولكن قدر معين من العمل الإضافي.

نوع سريع مثل إدارية النهج حيث هو واحد لا تهتم في البداية عن أي أمر إلا عن اجتماع واسع معيار هذا النظام.ثم أقسام ضاقت حتى تحصل على فرز مجموعة.التحدي الحقيقي في فرز سريع في إيجاد قسم أو المعيار في الظلام عندما كنت تعرف شيئا عن عناصر نوعا ما.وهذا هو السبب في أننا إما تحتاج إلى قضاء بعض الجهد للعثور على متوسط القيمة أو اختيار 1 عشوائيا أو بعض التعسفي "الإدارية" النهج .العثور على الكمال متوسط يمكن أن يستغرق قدرا كبيرا من الجهد يؤدي إلى الغباء نهج تصاعدي مرة أخرى.حتى فرز سريع يقول مجرد اختيار عشوائي محور ونأمل أن يكون في مكان ما في الوسط أو القيام ببعض العمل على إيجاد متوسط من 3 ، 5 أو شيء أكثر أن تجد أفضل متوسط ولكن لا تخطط لتكون مثالية و لا نضيع الوقت في البداية الطلب.ويبدو أن تفعل جيدا إذا كنت محظوظا أو في بعض الأحيان يحط أن ن^2 عندما كنت لا تحصل على متوسط ولكن فقط تأخذ فرصة.أي طريقة بيانات عشوائية.صحيح.لذلك أنا أتفق مع أعلى ->أسفل النهج المنطقي من فرز سريع & اتضح أن فرصة يستغرق حوالي محور الاختيار & مقارنات أن يحفظ في وقت سابق يبدو للعمل بشكل أفضل مرات أكثر من أي دقيق & دقيق مستقرة أسفل -- >نهج مثل دمج النوع.ولكن

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow