شرح خوارزميات الفرز

خوارزميات الفرز هي مجموعة من التعليمات التي تأخذ مصفوفة أو قائمة كمدخلات وترتب العناصر في ترتيب معين.

تكون الأنواع الأكثر شيوعًا في الترتيب العددي أو الأبجدي (يسمى معجمي) ، ويمكن أن تكون بترتيب تصاعدي (AZ ، 0-9) أو تنازليًا (ZA ، 9-0).

لماذا الفرز الخوارزميات مهمة

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

بعض خوارزميات الفرز الشائعة

بعض خوارزميات الفرز الأكثر شيوعًا هي:

• اختيار نوع
• فقاعة الفرز
• ترتيب بالإدراج
• دمج الفرز
• فرز سريع
• نوع كومة
• فرز الفرز
• فرز الجذر
• فرز دلو

تصنيف خوارزمية الفرز

يمكن تصنيف خوارزميات الفرز بناءً على المعلمات التالية:

1. استنادًا إلى عدد المقايضات أو الانعكاس هذا هو عدد المرات التي تتبادل فيها الخوارزمية العناصر لفرز المدخلات. Selection Sortيتطلب الحد الأدنى من عدد المقايضات.
2. استنادًا إلى عدد المقارنات هذا هو عدد المرات التي تقارن فيها الخوارزمية العناصر لفرز المدخلات. باستخدام تدوين Big-O ، تتطلب أمثلة خوارزمية الفرز المذكورة أعلاه O(nlogn)مقارنات على الأقل في أفضل حالة O(n^2)ومقارنات في أسوأ الحالات لمعظم المخرجات.
3. على أساس العودية أو غير العودية بعض خوارزميات الفرز ، مثل Quick Sort، استخدام التقنيات العودية لفرز المدخلات. خوارزميات الفرز الأخرى ، مثل Selection Sortأو Insertion Sort، تستخدم تقنيات غير تكرارية. أخيرًا ، تستخدم بعض خوارزمية الفرز ، مثل Merge Sort، تقنيات متكررة وغير متكررة لفرز المدخلات.
4. استنادًا إلى خوارزميات فرز الاستقرار ، يُقال stableإن الخوارزمية تحافظ على الترتيب النسبي للعناصر ذات المفاتيح المتساوية. بعبارة أخرى ، يظل عنصران مكافئان بنفس الترتيب في الإخراج الفرز كما كانا في الإدخال.
5. Insertion sort، Merge Sortو Bubble Sortمستقرة
6. Heap Sortو Quick Sortليست مستقرة
7. استنادًا إلى خوارزميات الفرز لمتطلبات المساحة الإضافية ، يُقال in placeإن كانت تتطلب O(1)مساحة إضافية ثابتة للفرز.
8. Insertion sortو Quick-sortهي in placeنوع ونحن نتحرك العناصر حول محور ولا فعلا استخدام مجموعة منفصلة وليس هذا هو الحال في النوع دمج حيث يجب تخصيص حجم المدخلات مسبقا لتخزين الانتاج خلال هذا القبيل.
9. Merge Sortهو مثال على out placeنوع ما لأنه يتطلب مساحة ذاكرة إضافية لعملياته.

أفضل تعقيد زمني ممكن لأي فرز قائم على المقارنة

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