المحتوى

• رسم بياني للمقارنة
• تعريف الترتيب السريع
• تعريف دمج الفرز
• استنتاج

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

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

1. 1. رسم بياني للمقارنة
   2. فريف
   3. الاختلافات الرئيسية
   4. استنتاج

رسم بياني للمقارنة

أساس للمقارنة	فرز سريع	دمج الفرز
تقسيم العناصر في الصفيف	تقسيم قائمة العناصر لا ينقسم بالضرورة إلى نصفين.	يتم تقسيم الصفيف دائمًا إلى نصف (n / 2).
أسوأ حالة التعقيد	على2)	يا (ن سجل ن)
يعمل بشكل جيد على	مجموعة أصغر	يعمل بشكل جيد في أي نوع من مجموعة.
سرعة	أسرع من خوارزميات الفرز الأخرى لمجموعة البيانات الصغيرة.	سرعة ثابتة في جميع أنواع مجموعات البيانات.
متطلبات مساحة التخزين الإضافية	أقل	أكثر من
نجاعة	غير فعالة للصفائف أكبر.	أكثر فعالية.
طريقة الفرز	داخلي	خارجي

تعريف الترتيب السريع

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

افترض أن A عبارة عن صفيف A ، A ، A ، ......... ، A من عدد n والتي يجب فرزها. خوارزمية الفرز السريع تتألف من الخطوات التالية.

1. العنصر الأول أو أي عنصر عشوائي محدد كمفتاح ، افترض المفتاح = A (1).
2. يتم وضع المؤشر "المنخفض" في الثانية ويتم وضع المؤشر "للأعلى" في العنصر الأخير من المصفوفة ، أي low = 2 و up = n؛
3. باستمرار ، قم بزيادة المؤشر "المنخفض" بموضع واحد حتى (A> مفتاح).
4. باستمرار ، قم بتقليل مؤشر "أعلى" بموضع واحد حتى (A <= مفتاح).
5. إذا كان up أكبر من التقاطع المنخفض A مع A.
6. كرر الخطوة 3،4 ، و 5 حتى فشل الشرط في الخطوة 5 (أي أعلى <= منخفض) ثم تبادل A مع المفتاح.
7. إذا كانت عناصر يسار المفتاح أصغر من المفتاح وكانت عناصر يمين المفتاح أكبر من المفتاح ، فسيتم تقسيم الصفيف إلى صفيفين فرعيين.
8. يتم تطبيق الإجراء أعلاه بشكل متكرر على المصفوفات الفرعية حتى يتم فرز المصفوفة بأكملها.

   

   
   

المميزات والعيوب

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

تعريف دمج الفرز

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

اجعل A عبارة عن صفيف عدد العناصر المراد فرزها A ، A ، ......... ، A. يتبع ترتيب الدمج الخطوات المحددة.

1. قسِّم الصفيف A إلى صفيف فرعي n / 2 تقريبًا تقريبًا ب 2 ، مما يعني أن العناصر في المصفوفات الفرعية (A ، A) ، (A ، A) ، (A ، A) ، (A ، A) يجب يكون في ترتيب فرزها.
2. اجمع كل زوج من الأزواج للحصول على قائمة بالصفائف الفرعية المصنفة بحجم 4 ؛ العناصر الموجودة في المصفوفات الفرعية مرتبة أيضًا ، (A ، A ، A ، A) ، ... ، (A ، A ، A ، A) ، ... ، (A ، A ، A ، A).
3. يتم تنفيذ الخطوة 2 مرارا وتكرارا حتى لا يوجد سوى مجموعة واحدة من الفرز حجم ن.

   

المميزات والعيوب

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

1. في فرز الدمج ، يجب فصل المصفوفة إلى نصفين فقط (أي n / 2). في مقابل ، في فرز سريع ، لا يوجد إكراه على تقسيم القائمة إلى عناصر متساوية.
2. أسوأ حالة تعقيد من نوع سريع هو O (ن²) لأنه يأخذ الكثير من المقارنات في أسوأ حالة. على النقيض من ذلك ، فإن دمج الفرز يكون له نفس الحالة وتعقيدات الحالة المتوسطة ، وهو O (n log n).
3. دمج الفرز يمكن أن يعمل بشكل جيد على أي نوع من مجموعات البيانات سواء كانت كبيرة أو صغيرة. على العكس من ذلك ، لا يمكن أن يعمل النوع السريع بشكل جيد مع مجموعات البيانات الكبيرة.
4. الفرز السريع أسرع من دمج الفرز في بعض الحالات ، مثل مجموعات البيانات الصغيرة.
5. يتطلب دمج الفرز مساحة ذاكرة إضافية لتخزين المصفوفات المساعدة. من ناحية أخرى ، لا يتطلب التصنيف السريع مساحة كبيرة للتخزين الإضافي.
6. دمج الفرز أكثر فعالية من الفرز السريع.
7. الفرز السريع هو طريقة الفرز الداخلي حيث يتم ضبط البيانات المراد فرزها في وقت في الذاكرة الرئيسية. وعلى العكس من ذلك ، فإن نوع الدمج عبارة عن طريقة فرز خارجية لا يمكن فيها استيعاب البيانات المراد فرزها في الذاكرة في نفس الوقت ويجب حفظ بعضها في الذاكرة المساعدة.

استنتاج

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