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

Question

في امتحان ترميز، طلبت ذات مرة هذا السؤال:

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

الخيارات كانت:

• lsd radix فرز
• دمج فرز
• فرز سريع

أعتقد أنه يمكن إجراء حجة بين LSD راديكس فرز و QuickSort .

راديكس فرز سيعمل في $ o (kn) $ و QuickSort سيعمل في $ O (n \ log n) $ وأسوأ الحالات، $ O (n ^ 2) $

اخترت راديكس فرز كإجابة، لكنني فضولي حول ما كان عليه الآخر أن يقول.

Answer 1

هذا يعتمد ... إذا كان عدد أرقام الإدخال $ n $ ، على افتراض نموذج Word-RAM للحساب، وحجم كلمة $ \ theta (\ log n) $ بت، وأسوأ الحالات المدخلات:

سيتطلب فرز

• radix $ O (n \ log n) $ الوقت و $ O (n) $ المساحة المساعدة.

• quicksort مع التحديد المحوري الثابت أو العشوائي سيتطلب $ O (n ^ 2) $ وقت الأحوال الأسوأ و $ o (\ log n) $ المساحة المساعدة.

• mergesort يتطلب $ O (n \ log n) $ الوقت و $ o (n) / تمتد> المساحة المساعدة.

راديكس فرز ودمج الفرز ثم ما يعادلها في هذا الإعداد.

لاحظ أن استخدام QuickSort مع اختيار تحديد Pivoit عشوائي في وقت التعقيد من $ O (n \ log n) $ مع احتمال كبير. اختيار المحور المحدد في الطريقة التي تقسم العناصر على مجموعتين في مجموعتين تمنحها كعامل ثابت بصرف النظر عن خوارزمية مع أسوأ حالة التعقيد $ O (n \ log n) $ و $ o (\ log n) $ المساحة الإضافية.