ما هو القطعية فرز سريع?

Question

لقد قرأت عن فرز سريع وجدت أن في بعض الأحيان أنها' s يشار إلى "حتمية فرز سريع".

هذا هو نسخة بديلة من الطبيعي فرز سريع ?ما هو الفرق بين العادي فرز سريع و القطعية فرز سريع ?

Answer 1

يمكن أن يكون للرسائل السريعة العادية ("الحتمية") سلوكًا سيئًا للغاية على مجموعات بيانات معينة (كمثال ، وهو تطبيق يختار العنصر الأول غير المصنف له تعقيد زمني O (n^2) على البيانات التي يتم توصيلها بالفعل).

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

Answer 2

فرز سريع يعمل في O(n log n) ومن المتوقع/متوسط الوقت ، ولكن O(n^2) أسوأ الأحوال.يحدث هذا إذا كان المحور الذي تم اختياره هو دائما إما أن الحد الأدنى أو الحد الأقصى.

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

الأسلوب الأخير يجعل فرز سريع غير حتمى بسبب العشوائية الكامنة محور عملية الاختيار.

Answer 3

في عام ، خوارزمية الفرز هو "حتمية" إذا كان باستمرار أنواع العناصر في نفس الأمر في كل مرة.بالنظر إلى مجموعة من السجلات الفرز على الهوية (asc):

  1 Censu
  11 Marju
  4  Cikku
  11 Lonzu

ثم خوارزمية الفرز يمكن أن تعود كل Censu, Cikk, Marju, Lonzu ، أو Censu, Cikku, Lonzu, Marju الصحيحة sortings.القطعية نوع واحد هو الذي يعود دائما نفس الطلب.وهذا لا يلزم أن يكون الحال دائما.في حالة فرز سريع ، يمكن الحصول على نحو أسرع من متوسط الأداء إذا محاور يتم اختيارها عشوائيا (من الأفضل لك أن تختار الوسيط, ولكن هذا يمكن أن يكون مكلفا).غير أن هذا يأتي في التكلفة:البحث الخاص بك لم يعد محددا.

Answer 4

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

Answer 5

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

هنا محاضرة مما يضعها عبر.

اتمني ان يكون مفيدا

في صحتك

Answer 6

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

القطعية

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

array = [1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1]

العشوائية

Randomizated quicksorts يمكن أن مجرد اختيار عشوائي المحورية أو استخدام متوسط عدد بعض من تم اختيارهم عشوائيا محاور.لا يزال هناك إمكانية O(N^2) التعقيد الوقت ، ولكن احتمال أصغر بكثير و يصبح أصغر مع زيادة حجم البيانات.

Answer 7

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

أعتقد أنه يجب ألا تستخدم Quickorting غير المحددة عندما يكون لديك مفاتيح غير متوفرة.