إن كلا من تقنيات الفرز ، الفرز السريع والفرز المدمج مبنيان على طريقة الانقسام والانتصار التي يتم فيها تجميع مجموعة العناصر ثم دمجها بعد إعادة الترتيب. عادةً ما يتطلب التصنيف السريع مقارنات أكثر من دمج الفرز لفرز مجموعة كبيرة من العناصر.
رسم بياني للمقارنة
| أساس للمقارنة | فرز سريع | دمج الفرز |
|---|---|---|
| تقسيم العناصر في المصفوفة | لا ينقسم تقسيم قائمة العناصر بالضرورة إلى نصفين. | يتم تقسيم المصفوفة دائما إلى نصف (ن / 2). |
| أسوأ تعقيد الحالة | على 2) | O (n log n) |
| يعمل بشكل جيد على | مجموعة أصغر | تعمل بشكل جيد في أي نوع من الصفيف. |
| سرعة | أسرع من غيرها من خوارزميات الفرز لمجموعة البيانات الصغيرة. | سرعة متسقة في جميع أنواع مجموعات البيانات. |
| متطلبات مساحة تخزين إضافية | أقل | أكثر من |
| نجاعة | غير فعالة لمصفوفات أكبر. | أكثر فعالية. |
| طريقة الفرز | داخلي | خارجي |
تعريف التصنيف السريع
يستخدم التصنيف السريع خوارزمية الفرز لأنه سريع للمصفوفات القصيرة. تنقسم مجموعة العناصر إلى أجزاء متكررة حتى لا يمكن تقسيمها بشكل أكبر. يُعرف التصنيف السريع أيضًا بفرز تبادل القسم . ويستخدم عنصرًا رئيسيًا (يعرف بالمحور) لتقسيم العناصر. يحتوي قسم واحد على العناصر التي تكون أصغر من العنصر الأساسي. يحتوي قسم آخر على العناصر التي تكون أكبر من العنصر الأساسي. يتم فرز العناصر بشكل متكرر.
افترض أن A عبارة عن مصفوفة A [1] و A [2] و A [3] و ........ و A [n] من n number والتي يجب فرزها. تتألف خوارزمية الفرز السريع من الخطوات التالية.
- العنصر الأول أو أي عنصر عشوائي يتم تحديده كمفتاح ، يفترض المفتاح = A (1).
- يوضع المؤشر "المنخفض" عند الثاني ويتم وضع المؤشر "لأعلى" عند آخر عنصر في الصفيف ، أي منخفض = 2 وأعلى = n ؛
- باستمرار ، قم بزيادة المؤشر "المنخفض" من موضع واحد حتى (A [low]> key).
- باستمرار ، قم بإنقاص مؤشر "up" بواسطة موضع واحد حتى (A [up] <= key).
- إذا كان أعلى من التقاطع منخفض A [منخفض] مع A [أعلى].
- كرر الخطوة 3 ، 4 و 5 حتى يفشل الشرط في الخطوة 5 (أي أعلى <= منخفض) ثم قم بتبديل A [up] مع المفتاح.
- إذا كانت العناصر المتبقية من المفتاح أصغر من المفتاح وكانت عناصر المفتاح الأيمن أكبر من المفتاح ، يتم تقسيم الصفيف إلى صفيفين فرعيين.
- يتم تطبيق الإجراء أعلاه بشكل متكرر على subarrays حتى يتم فرز الصفيف بأكمله.
المميزات والعيوب
انها تمتلك جيد متوسط السلوك القضية. يعتبر تعقيد وقت التشغيل للفرز السريع جيدًا ، فهو أسرع من الخوارزميات مثل فرز الفقاعة ، وفرز الإدراج ، وفرز الاختيار. ومع ذلك ، فهي معقدة ومتكررة للغاية ، وهذا هو السبب في أنها ليست مناسبة لمصفوفات كبيرة.
تعريف تصنيف الدمج
دمج الفرز عبارة عن خوارزمية خارجية تستند أيضًا إلى إستراتيجية الفجوة وقهر. يتم تقسيم العناصر إلى صفائف فرعية (n / 2) مرارًا وتكرارًا حتى يتم ترك عنصر واحد فقط ، مما يقلل وقت الفرز بشكل ملحوظ. ويستخدم تخزين إضافي لتخزين مجموعة المساعدة. يستخدم فرز الفرز ثلاثة صفائف حيث يتم استخدام اثنين لتخزين كل نصف ، ويستخدم الثالث لتخزين القائمة النهائية المصنفة. ثم يتم فرز كل صفيف بشكل متكرر. في النهاية ، يتم دمج subarrays لجعله n حجم عنصر الصفيف. قائمة دائما تنقسم إلى نصف (n / 2) متباينة إلى فرز سريع.
دع A يكون مصفوفة عدد n من العناصر المراد فرزها A [1]، A [2]، ………، A [n]. يتبع الفرز دمج الخطوات المعطاة.
- تقسيم المصفوفة A إلى صفيف فرعي n / 2 مصنف تقريبًا بمقدار 2 ، مما يعني أن العناصر الموجودة في (A [1] ، A [2]) ، (A [3] ، A [4]) ، (A [ k] ، A [k + 1]) ، يجب أن تكون الصفائف الفرعية [n-1] ، A [n] في ترتيب مفروز.
- الجمع بين كل زوج من الأزواج للحصول على قائمة من subarrays مفروزة من حجم 4 ؛ تكون العناصر الموجودة في subarrays مرتبة مرتبة أيضًا ، (A [1] ، A [2] ، A [3] ، A [4]) ، …… ، (A [k-1] ، A [k] ، A [k + 1]، A [k + 2])، …….، (A [n-3]، A [n-2]، A [n-1]، A [n]).
- يتم تنفيذ الخطوة 2 بشكل متكرر حتى يكون هناك صف واحد تم فرزه من حجم n.
المميزات والعيوب
خوارزمية الفرز دمج ينفذ بنفس الطريقة الدقيقة والدقيقة بغض النظر عن عدد العناصر المشاركة في الفرز. يعمل بشكل جيد حتى مع مجموعة البيانات الكبيرة. ومع ذلك ، فإنه يستهلك جزء أكبر من الذاكرة.
الاختلافات الرئيسية بين فرز سريع وفرز دمج
- في فرز الدمج ، يجب أن يتم تقسيم الصفيف إلى نصفين فقط (أي n / 2). وفي مقابل ذلك ، ليس هناك إكراه في تقسيم القائمة إلى عناصر متساوية.
- أسوأ تعقيد حالة من النوع السريع هو O (n2) لأنه يأخذ الكثير من المقارنات في أسوأ حالة. في المقابل ، يكون لدمج المزيج نفس أسوأ الحالات ومتوسط حالة التعقيدات ، أي O (n log n).
- يمكن لفرز الدمج أن يعمل بشكل جيد على أي نوع من مجموعات البيانات سواء كانت كبيرة أو صغيرة. على العكس ، لا يمكن أن يعمل النوع السريع بشكل جيد مع مجموعات البيانات الكبيرة.
- الفرز السريع أسرع من نوع الدمج في بعض الحالات مثل مجموعات البيانات الصغيرة.
- يتطلب فرز الفرز مساحة ذاكرة إضافية لتخزين المصفوفات المساعدة. من ناحية أخرى ، لا يتطلب الفرز السريع مساحة كبيرة للتخزين الإضافي.
- دمج التصنيف أكثر كفاءة من الفرز السريع.
- الفرز السريع هو أسلوب الفرز الداخلي حيث يتم ضبط البيانات المطلوب فرزها في وقت في الذاكرة الرئيسية. وعلى العكس ، فإن نوع الدمج هو أسلوب الفرز الخارجي الذي لا يمكن استيعاب البيانات التي يتم فرزها في الذاكرة في نفس الوقت ، ويجب الاحتفاظ بالبعض في الذاكرة المساعدة.
استنتاج
الفرز السريع هو حالات أسرع ولكنه غير فعال في بعض المواقف ويقوم أيضًا بإجراء الكثير من المقارنات مقارنة بفرز الدمج. على الرغم من أن فرز الدمج يتطلب مقارنة أقل ، إلا أنه يحتاج إلى مساحة ذاكرة إضافية تبلغ 0 (n) لتخزين الصفيف الإضافي بينما يحتاج الفرز السريع إلى مساحة O (log n).
