دمج الفرز: الخوارزمية والمزايا والميزات

2024 مؤلف: Angel Austin | [email protected]. آخر تعديل: 2024-02-02 14:38

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

مبدأ واستخدام الخوارزمية

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

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

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

يمكن استخدام الطريقة لطلب أي نوع بيانات قابل للمقارنة ، مثل الأرقام أو السلاسل.

دمج مرتبةالمؤامرات

لفهم الخوارزمية ، لنبدأ تحليلها من النهاية - من آلية دمج الكتل المصنفة.

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

مثال أولي: تتكون كلتا المصفوفتين من عنصر واحد لكل منهما.

int arr1={31} ؛ int arr2={18} ؛

لدمجهم ، يجب أن تأخذ عنصر الصفر من المصفوفة الأولى (لا تنس أن الترقيم يبدأ من الصفر) والعنصر الصفري من المصفوفة الثانية. هذان ، على التوالي ، 31 و 18. وفقًا لشرط الفرز ، يجب أن يأتي الرقم 18 أولاً ، لأنه أقل. فقط ضع الأرقام بالترتيب الصحيح:


int النتيجة={18، 31}؛

لنلقي نظرة على مثال أكثر تعقيدًا ، حيث تتكون كل مصفوفة من عدة عناصر:


int arr1={2، 17، 19، 45} ؛ int arr2={5، 6، 21، 30} ؛

ستتألف خوارزمية الدمج من المقارنة التسلسلية للعناصر الأصغر ووضعها في المصفوفة الناتجة بالترتيب الصحيح. لتتبع المؤشرات الحالية ، دعنا نقدم متغيرين - index1 و index2. في البداية ، قمنا بتعيينهم على الصفر ، حيث يتم فرز المصفوفات ، وتكون العناصر الأصغر في البداية.


int index1=0 ؛ int index2=0 ؛

لنكتب عملية الدمج بأكملها خطوة بخطوة:

خذ العنصر مع index1 من المصفوفة arr1 ، والعنصر مع index2 من المصفوفة arr2.
قارن ، حدد أصغرها ثم أدخلهاالمصفوفة الناتجة.
زيادة الفهرس الحالي للعنصر الأصغر بمقدار 1.
تابع من الخطوة الأولى.






في المدار الأول ، سيبدو الوضع على النحو التالي:


index1=0 ؛ الفهرس 2=0 ؛ arr1 [0]=2 ؛ arr2 [0]=5 ؛ arr1 [0] < arr2 [0] ؛ فهرس 1 ++ ؛ النتيجة [0]=arr1 [0] ، // النتيجة=[2]

في المنعطف الثاني:


index1=1 ؛ الفهرس 2=0 ؛ arr1 [1]=17 ؛ arr2 [0]=5 ؛ arr1 [1] > arr2 [0] ؛ فهرس 2 ++ ؛ النتيجة [1]=arr2 [0] ، // النتيجة=[2، 5]

الثالث:


index1=1 ؛ الفهرس 2=1 ؛ arr1 [1]=17 ؛ arr2 [1]=6 ؛ arr1 [1] > arr2 [1] ؛ فهرس 2 ++ ؛ النتيجة [2]=arr2 [1] ؛ // النتيجة=[2، 5، 6]

وهكذا ، حتى تصبح النتيجة مصفوفة مرتبة بالكامل: {2 ، 5 ، 6 ، 17 ، 21 ، 19 ، 30 ، 45}.
يمكن أن تنشأ صعوبات معينة إذا تم دمج المصفوفات ذات الأطوال المختلفة. ماذا لو وصل أحد الفهارس الحالية إلى العنصر الأخير ولا يزال هناك أعضاء في المصفوفة الثانية؟


int arr1={1، 4} ؛ int arr2={2، 5، 6، 7، 9} ؛ // 1 خطوة index1=0 ، index2=0 ؛ 1 2 نتيجة={1، 2} ؛ // 3 خطوات index1=1 ، index2=1 ؛ 4 < 5 نتيجة={1، 2، 4} ؛ // 4 خطوات index1=2، index2=1 ؟؟

وصل متغير index1 إلى القيمة 2 ، لكن مصفوفة arr1 لا تحتوي على عنصر بهذا الفهرس. كل شيء بسيط هنا: ما عليك سوى نقل العناصر المتبقية من المصفوفة الثانية إلى المجموعة الناتجة ، مع الحفاظ على ترتيبها.


نتيجة={1، 2، 4، 5، 6، 7، 9} ؛

هذا الوضع يشير لنا الحاجةتطابق فهرس الفحص الحالي مع طول المصفوفة المندمجة.
مخطط الدمج للتسلسلات المرتبة (A و B) بأطوال مختلفة:

إذا كان طول كلا التسلسل أكبر من 0 ، قارن A [0] و B [0] وانقل التسلسل الأصغر إلى المخزن المؤقت.
إذا كان طول أحد التسلسلات هو 0 ، خذ العناصر المتبقية من التسلسل الثاني ، وبدون تغيير ترتيبها ، انتقل إلى نهاية المخزن المؤقت.


تنفيذ المرحلة الثانية
مثال على الانضمام إلى صفيفتين تم فرزهما في Java موضح أدناه.


int a1=new int {21، 23، 24، 40، 75، 76، 78، 77، 900، 2100، 2200، 2300، 2400، 2500} ؛ int a2=new int {10، 11، 41، 50، 65، 86، 98، 101، 190، 1100، 1200، 3000، 5000} ؛ int a3=new int [a1.length + a2.length] ؛ int أنا=0 ، ي=0 ؛ لـ (int k=0 ؛ k a1.length-1) {int a=a2 [j] ؛ a3 [ك]=أ ؛ ي ++ ؛ } else if (j > a2.length-1) {int a=a1 ؛ a3 [ك]=أ ؛ أنا ++ ؛ } else if (a1 < a2 [j]) {int a=a1 ؛ a3 [ك]=أ ؛ أنا ++ ؛ } else {int b=a2 [j] ؛ a3 [ك]=ب ؛ ي ++ ؛ }}

هنا:

a1 و a2 هي المصفوفات المصنفة الأصلية المراد دمجها ؛
a3 - الصفيف النهائي ؛
i و j فهارس للعناصر الحالية للمصفوفات a1 و a2.

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






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


// المصفوفة الأصلية {34، 95، 10، 2، 102، 70} ؛ // أول تقسيم {34 ، 95 ، 10} و {2 ، 102 ، 70} ؛ // second split {34} and {95، 10} and {2} and {102، 70}

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






تنفيذ المرحلة الاولى
يظهر التقسيم المتكرر لصفيف أدناه.


void mergeSort (T a ، long start، long finish) {long split؛ لو(ابدأ < النهاية) {انقسام=(البداية + النهاية) / 2 ؛ mergeSort (أ ، ابدأ ، انقسام) ؛ mergeSort (a، split + 1، finish) ؛ دمج (أ ، بدء ، تقسيم ، إنهاء) ؛ }}

ماذا يحدث في هذا الرمز:



تحصل الدالة mergeSort على المصفوفة الأولية

a

ويتم فرز الحدود اليمنى واليسرى للمنطقة (تبدأ المؤشرات و

finish)



إذا كان طول هذا القسم أكبر من واحد (

ابدأ < إنهاء

) ، ثم يتم تقسيمه إلى قسمين (حسب الفهرس

انقسام) ، ويتم فرز كل واحد بشكل متكرر.



في استدعاء الوظيفة العودية للجانب الأيسر ، يتم تمرير فهرس البداية للمخطط والفهرس

split

. بالنسبة للجزء الصحيح ، على التوالي ، ستكون البداية

(انقسام + 1)، وستكون النهاية هي الفهرس الأخير للقسم الأصلي.



الوظيفة

merge

تحصل على تسلسلين مرتبين (

a [بدء] … [انقسام]

و

a [انقسام +1] … [إنهاء]) ودمجها في ترتيب الفرز.


تمت مناقشة آليات وظيفة الدمج أعلاه.

مخطط عام للخوارزمية
تتكون طريقة مصفوفة دمج الفرز من خطوتين كبيرتين:

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

يتم تقسيم المهمة الكبيرة والمعقدة إلى العديد من المهام البسيطة ، والتي يتم حلها بالتتابع ، مما يؤدي إلى النتيجة المرجوة.






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

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


Procedure MergeSort (name: string؛ var f: text) ؛ Var a1، a2، s، i، j، kol، tmp: عدد صحيح ؛ f1 ، f2: نص ؛ ب: منطقي Begincol:=0 ؛ تعيين (و ، الاسم) ؛ إعادة تعيين (و) ؛ بينما لا تبدأ EOF (f) بالقراءة (f ، a1) ؛ المؤتمر الوطني العراقي (عمود) ؛ نهاية؛ قريب (و) ؛ تعيين (f1، '{name of 1st auxiliary file}')؛ تعيين (f2، '{name of 2nd auxiliary file}')؛ ق:=1 ؛ بينما (s<kol) تبدأ إعادة التعيين (f) ؛ إعادة كتابة (f1) ؛ إعادة كتابة (f2) ؛ بالنسبة إلى i:=1 إلى kol div 2 ، ابدأ القراءة (f ، a1) ؛ اكتب (f1، a1، '') ؛ نهاية؛ إذا كان (kol div 2) mod s0 ، فابدأ tmp:=kol div 2 ؛ بينما تبدأ tmp mod s0 بالقراءة (f ، a1) ؛ اكتب (f1، a1، '') ؛ المؤتمر الوطني العراقي (تمب) ؛ نهاية؛ نهاية؛ بينما لا تبدأ EOF (f) في القراءة (f ، a2) ؛ اكتب (f2، a2، '') ؛ نهاية؛ قريب (و) ؛ قريب (f1) ؛ قريب (f2) ؛ إعادة كتابة (و) ؛ إعادة تعيين (f1) ؛ إعادة تعيين (f2) ؛ قراءة (f1، a1)؛ قراءة (f2، a2)؛ بينما (ليس EOF (f1)) و (ليس EOF (f2)) تبدأ i:=0 ؛ ي:=0 ؛ ب:=صحيح ؛ بينما (ب) و (ليس EOF (f1)) و (ليس EOF (f2)) ابدأ إذا (a1<a2) ثم ابدأاكتب (f ، a1 ، '') ؛ قراءة (f1، a1)؛ المؤتمر الوطني العراقي (ط) ؛ نهاية أخرى تبدأ الكتابة (f ، a2 ، '') ؛ قراءة (f2، a2)؛ المؤتمر الوطني العراقي (ي) ؛ نهاية؛ إذا (i=s) أو (j=s) فإن b:=false ؛ نهاية؛ إذا لم يكن b ، فابدأ أثناء (i<s) و (وليس EOF (f1)) ابدأ الكتابة (f ، a1 ، '') ؛ قراءة (f1، a1)؛ المؤتمر الوطني العراقي (ط) ؛ نهاية؛ بينما (j<s) و (وليس EOF (f2)) تبدأ الكتابة (f ، a2 ، '') ؛ قراءة (f2، a2)؛ المؤتمر الوطني العراقي (ي) ؛ نهاية؛ نهاية؛ نهاية؛ أثناء عدم وجود EOF (f1) ، ابدأ tmp:=a1 ؛ قراءة (f1، a1)؛ إذا لم يكن EOF (f1) ، فاكتب (f، tmp، '') وإلا اكتب (f، tmp)؛ نهاية؛ أثناء عدم وجود EOF (f2) ، ابدأ tmp:=a2 ؛ قراءة (f2، a2)؛ إذا لم يكن EOF (f2) ، فاكتب (f، tmp، '') وإلا اكتب (f، tmp)؛ نهاية؛ قريب (و) ؛ قريب (f1) ؛ قريب (f2) ؛ s:=s2 ؛ نهاية؛ محو (f1) ؛ محو (f2) ؛ النهاية ؛

بصريًا ، يبدو تشغيل الخوارزمية على هذا النحو (أعلى - تسلسل غير مرتب ، أسفل - مرتبة).






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






دمج بسيط
مع دمج بسيط ، يتم إصلاح طول السلسلة
وهكذا ، في الملف الأصلي غير الفرز ، تتكون كل السلاسل من عنصر واحد. بعد الخطوة الأولى ، يزداد الحجم إلى اثنين. التالي - 4 و 8 و 16 وما إلى ذلك.
يعمل على النحو التالي:

الملف المصدر (f) مقسم إلى قسمين مساعدين - f1، f2.
يتم دمجها مرة أخرى في ملف واحد (f) ، ولكن في نفس الوقت تتم مقارنة جميع العناصر في أزواج وأزواج من النماذج. يصبح حجم المسلسل في هذه الخطوة اثنين.
الخطوة 1 مكرر
يتم تكرار الخطوة 2 ، ولكن تم دمج 2s المرتبة بالفعل لتشكيل 4s مرتبة.
تستمر الحلقة بزيادة التسلسل في كل تكرار حتى يتم فرز الملف بالكامل.

كيف تعرف أن الفرز الخارجي بدمج بسيط قد اكتمل؟

طول سلسلة جديد (بعد الدمج) لا يقل عن العدد الإجمالي للعناصر ؛
بقي حلقة واحدة فقط ؛
الملف الإضافي f2 ترك فارغا

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

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

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

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

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





يوضح الفيديو بوضوح تشغيل خوارزمية فرز الدمج.