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

دمج الفرز هو خوارزمية فرز تعتمد على تقنية "فرق تسد". إنها واحدة من أكثر خوارزميات الفرز كفاءة.

في هذه المقالة ، ستتعرف على طريقة عمل خوارزمية فرز الدمج ، وخوارزمية نوع الدمج ، تعقيد الزمان والمكان ، وتنفيذه في لغات البرمجة المختلفة مثل C ++ و Python و جافا سكريبت.

كيف تعمل خوارزمية دمج الفرز؟

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

يمكن شرح هذا المفهوم بشكل أكثر كفاءة بمساعدة مثال. ضع في اعتبارك مصفوفة لم يتم فرزها تحتوي على العناصر التالية: {16 ، 12 ، 15 ، 13 ، 19 ، 17 ، 11 ، 18}.

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

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

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

MergeSort (arr [] ، leftIndex ، rightIndex)
إذا كان leftIndex> = rightIndex
إرجاع
آخر
ابحث عن الفهرس الأوسط الذي يقسم المصفوفة إلى نصفين: 
midIndex = leftIndex + (rightIndex-leftIndex) / 2





instagram viewer


استدعاء mergeSort () للنصف الأول: 
استدعاء mergeSort (arr ، leftIndex ، middleIndex)
استدعاء mergeSort () للنصف الثاني:
استدعاء mergeSort (arr، middleIndex + 1، rightIndex)
ادمج النصفين اللذين تم فرزهما في الخطوتين 2 و 3:
دمج المكالمات (arr، leftIndex، middleIndex، rightIndex)

متعلق ب: ما هي العودية وكيف تستخدمها؟

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

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

T (ن) = 2T (ن / 2) + O (ن)

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

أفضل تعقيد زمني لفرز الدمج: O (n تسجيل الدخول)

تعقيد وقت الحالة المتوسطة لفرز الدمج: O (n تسجيل الدخول)

التعقيد الزمني الأسوأ لنوع الدمج: O (n تسجيل الدخول)

متعلق ب: ما هو تدوين Big-O؟

تعقيد الفضاء المساعد من خوارزمية فرز الدمج هي على) مثل ن مطلوب مساحة إضافية في تنفيذ فرز الدمج.

C ++ تنفيذ خوارزمية دمج الفرز

فيما يلي تطبيق C ++ لخوارزمية فرز الدمج:

// C ++ تنفيذ
// دمج خوارزمية الفرز
#تضمن 
استخدام اسم للمحطة؛
// تدمج هذه الوظيفة مصفوفتين فرعيتين لـ arr []
// اليسار subarray: arr [leftIndex..middleIndex]
// Right subarray: arr [midIndex + 1..rightIndex]
دمج باطل (int arr []، int leftIndex، int middleIndex، int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1 ؛
int rightSubarraySize = rightIndex - middleIndex ؛
// إنشاء مصفوفات مؤقتة
int L [leftSubarraySize] ، R [rightSubarraySize] ،
// نسخ البيانات إلى المصفوفات المؤقتة L [] و R []
لـ (int i = 0 ؛ أنا L [i] = arr [leftIndex + i] ؛
لـ (int j = 0 ؛ j R [j] = arr [midIndex + 1 + j] ؛
// دمج المصفوفات المؤقتة مرة أخرى في arr [leftIndex..rightIndex]
// الفهرس الأولي للمصفوفة اليسرى
كثافة العمليات أنا = 0 ؛
// الفهرس الأولي للمصفوفة اليمنى
int j = 0 ؛
// الفهرس الأولي للمصفوفة الفرعية المدمجة
int k = leftIndex ؛
بينما (i ​​{
إذا (L [i] <= R [j])
{
arr [k] = L [i] ؛
أنا ++ ؛
}
آخر
{
arr [k] = R [j] ؛
ي ++ ؛
}
ك ++ ؛
}
// إذا كانت هناك بعض العناصر المتبقية في L []
// نسخ إلى arr []
بينما (i ​​{
arr [k] = L [i] ؛
أنا ++ ؛
ك ++ ؛
}
// إذا كانت هناك بعض العناصر المتبقية في R []
// نسخ إلى arr []
بينما (j {
arr [k] = R [j] ؛
ي ++ ؛
ك ++ ؛
}
}
mergeSort باطل (int arr [] ، int leftIndex ، int rightIndex)
{
إذا (leftIndex> = rightIndex)
{
إرجاع؛
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2 ؛
mergeSort (arr، leftIndex، middleIndex) ؛
mergeSort (arr، middleIndex + 1، rightIndex) ؛
دمج (arr، leftIndex، middleIndex، rightIndex) ؛
}
// وظيفة لطباعة العناصر
// من المصفوفة
صفيف طباعة باطلة (int arr [] ، حجم int)
{
لـ (int i = 0 ؛ أنا {
cout << arr [i] << ""؛
}
cout << endl؛
}
// كود السائق
انت مين()
{
int arr [] = {16، 12، 15، 13، 19، 17، 11، 18} ؛
حجم int = sizeof (arr) / sizeof (arr [0]) ؛
cout << "صفيف غير مفرز:" << endl؛
printArray (حجم ، حجم) ؛
mergeSort (arr ، 0 ، الحجم - 1) ؛
cout << "مصفوفة مرتبة:" << endl؛
printArray (حجم ، حجم) ؛
العودة 0 ؛
}

انتاج:

مجموعة غير مرتبة:
16 12 15 13 19 17 11 18 
مجموعة مرتبة:
11 12 13 15 16 17 18 19

تنفيذ JavaScript لخوارزمية دمج الفرز

فيما يلي تطبيق JavaScript لخوارزمية فرز الدمج:

// تنفيذ JavaScript لملف
// دمج خوارزمية الفرز
// تدمج هذه الوظيفة مصفوفتين فرعيتين لـ arr []
// اليسار subarray: arr [leftIndex..middleIndex]
// Right subarray: arr [midIndex + 1..rightIndex]
دمج الوظيفة (arr، leftIndex، middleIndex، rightIndex) {
دع leftSubarraySize = middleIndex - leftIndex + 1 ؛
دع rightSubarraySize = rightIndex - middleIndex ؛
// إنشاء مصفوفات مؤقتة
var L = new Array (leftSubarraySize) ؛
var R = new Array (rightSubarraySize) ؛
// نسخ البيانات إلى المصفوفات المؤقتة L [] و R []
لـ (دع أنا = 0 ؛ أناL [i] = arr [leftIndex + i] ؛
}
لـ (دع j = 0 ؛ يR [j] = arr [midIndex + 1 + j] ؛
}
// دمج المصفوفات المؤقتة مرة أخرى في arr [leftIndex..rightIndex]
// الفهرس الأولي للمصفوفة اليسرى
var i = 0 ؛
// الفهرس الأولي للمصفوفة اليمنى
فار ي = 0 ؛
// الفهرس الأولي للمصفوفة الفرعية المدمجة
var k = leftIndex ؛
بينما (i ​​{
إذا (L [i] <= R [j])
{
arr [k] = L [i] ؛
أنا ++ ؛
}
آخر
{
arr [k] = R [j] ؛
ي ++ ؛
}
ك ++ ؛
}
// إذا كانت هناك بعض العناصر المتبقية في L []
// نسخ إلى arr []
بينما (i ​​{
arr [k] = L [i] ؛
أنا ++ ؛
ك ++ ؛
}
// إذا كانت هناك بعض العناصر المتبقية في R []
// نسخ إلى arr []
بينما (j {
arr [k] = R [j] ؛
ي ++ ؛
ك ++ ؛
}
}
دالة mergeSort (arr، leftIndex، rightIndex) {
إذا (leftIndex> = rightIndex) {
إرجاع
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2) ؛
mergeSort (arr، leftIndex، middleIndex) ؛
mergeSort (arr، middleIndex + 1، rightIndex) ؛
دمج (arr، leftIndex، middleIndex، rightIndex) ؛
}
// وظيفة لطباعة العناصر
// من المصفوفة
وظيفة printArray (حجم ، حجم) {
لـ (دع أنا = 0 ؛ أناdocument.write (arr [i] + "") ؛
}
document.write ("
");
}
// كود السائق:
var arr = [16 ، 12 ، 15 ، 13 ، 19 ، 17 ، 11 ، 18] ؛
حجم فار = الطول الطول ؛
document.write ("مصفوفة غير مرتبة:
");
printArray (حجم ، حجم) ؛
mergeSort (arr ، 0 ، الحجم - 1) ؛
document.write ("المصفوفة المرتبة:
");
printArray (حجم ، حجم) ؛

انتاج:

مجموعة غير مرتبة:
16 12 15 13 19 17 11 18
مجموعة مرتبة:
11 12 13 15 16 17 18 19

متعلق ب: البرمجة الديناميكية: الأمثلة والمشكلات الشائعة والحلول

تنفيذ Python لخوارزمية فرز الدمج

فيما يلي تطبيق Python لخوارزمية فرز الدمج:

# تنفيذ Python لملف
# دمج خوارزمية الفرز
def mergeSort (arr):
إذا كان len (arr)> 1:
# إيجاد الفهرس الأوسط للمصفوفة
midIndex = len (arr) // 2
# النصف الأيسر من المصفوفة
L = arr [: middleIndex]
# النصف الأيمن من المصفوفة
R = arr [midIndex:]
# فرز النصف الأول من المصفوفة
mergeSort (L)
# فرز النصف الثاني من المصفوفة
mergeSort (R)
# الفهرس الأولي للصفيف الفرعي الأيسر
أنا = 0
# الفهرس الأولي للمصفوفة اليمنى
ي = 0
# الفهرس الأولي للمصفوفة الفرعية المدمجة
ك = 0
# نسخ البيانات إلى المصفوفتين المؤقتتين L [] و R []
بينما i إذا L [i] arr [k] = L [i]
أنا = أنا + 1
آخر:
arr [k] = R [j]
ي = ي + 1
ك = ك + 1
# التحقق مما إذا كانت هناك بعض العناصر المتبقية
بينما أنا arr [k] = L [i]
أنا = أنا + 1
ك = ك + 1
بينما j arr [k] = R [j]
ي = ي + 1
ك = ك + 1
# وظيفة لطباعة العناصر
# من المصفوفة
def printArray (حجم ، حجم):
لأني في النطاق (الحجم):
طباعة (arr [i]، end = "")
مطبعة()
# كود السائق
arr = [16 ، 12 ، 15 ، 13 ، 19 ، 17 ، 11 ، 18]
الحجم = len (arr)
طباعة ("مصفوفة غير مرتبة:")
printArray (حجم ، حجم)
mergeSort (arr)
طباعة ("مصفوفة مرتبة:")
printArray (حجم ، حجم)

انتاج:

مجموعة غير مرتبة:
16 12 15 13 19 17 11 18
مجموعة مرتبة:
11 12 13 15 16 17 18 19

فهم خوارزميات الفرز الأخرى

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

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

مقدمة في خوارزمية فرز الفقاعات

خوارزمية فرز الفقاعات: مقدمة ممتازة لفرز المصفوفات.

اقرأ التالي

عن المؤلف