מבוא לאלגוריתם המיזוג למיזוג

מיון מיזוג הוא אלגוריתם מיון המבוסס על טכניקת "לחלק ולכבוש". זהו אחד מאלגוריתמי המיון היעילים ביותר.

במאמר זה תוכלו ללמוד על אופן הפעולה של אלגוריתם המיזוג, האלגוריתם של מיון המיזוג, שלו מורכבות זמן ומרחב, והטמעתו בשפות תכנות שונות כמו C ++, Python ו- JavaScript.

כיצד עובד אלגוריתם המיזוג למיזוג?

מיון מיזוג עובד על עקרון החלוקה והכיבוש. מיון מיזוג מפרק שוב ושוב מערך לשני מערכי משנה שווים עד שכל מערך משנה מורכב מאלמנט יחיד. לבסוף, כל מערכי המשנה הללו מוזגו כך שמערך התוצאה מיון.

ניתן להסביר מושג זה בצורה יעילה יותר בעזרת דוגמא. שקול מערך לא ממוין עם האלמנטים הבאים: {16, 12, 15, 13, 19, 17, 11, 18}.

כאן, אלגוריתם המיזוג מחלק את המערך לשני חצאים, קורא לעצמו לשני החצאים ואז ממזג את שני החצאים הממוינים.

מיזוג אלגוריתם מיון

להלן האלגוריתם של מיזוג המיזוג:

MergeSort (arr [], leftIndex, rightIndex)
אם leftIndex> = rightIndex
לַחֲזוֹר
אַחֵר
מצא את האינדקס האמצעי המחלק את המערך לשני חצאים: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
התקשר ל- mergeSort () למחצית הראשונה: 
Call mergeSort (arr, leftIndex, middleIndex)





instagram viewer


התקשר ל- mergeSort () למחצית השנייה:
Call mergeSort (arr, middleIndex + 1, rightIndex)
מיזג את שני החצאים הממוינים בשלב 2 ו- 3:
מיזוג שיחות (arr, leftIndex, middleIndex, rightIndex)

קָשׁוּר: מהי רקורסיה ואיך משתמשים בה?

מורכבות הזמן והמרחב של אלגוריתם המיזוג

אלגוריתם המיזוג של מיזוג יכול לבוא לידי ביטוי בצורה של יחס ההישנות הבא:

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

לאחר פתרון יחס הישנות זה בשיטת משפט המאסטר או בשיטת עץ ההישנות, תקבל את הפתרון כ- O (n logn). לפיכך, מורכבות הזמן של אלגוריתם מיון המיזוג היא O (n logn).

מורכבות הזמן הטובה ביותר במיון המיזוג: O (n logn)

מורכבות הזמן הממוצעת של מקרה המיזוג: O (n logn)

מורכבות הזמן הגרועה ביותר בסוג המיזוג: O (n logn)

קָשׁוּר: מהי סימון ביג-או?

מורכבות החלל העזר של אלגוריתם המיזוג הוא עַל) כפי ש נ נדרש מרחב עזר ביישום מיון המיזוג.

יישום C ++ של אלגוריתם המיזוג למיזוג

להלן הטמעת C ++ של אלגוריתם המיזוג למיזוג:

// יישום C ++ של ה-
// מיזוג אלגוריתם למיון
#לִכלוֹל 
באמצעות std namespace;
// פונקציה זו ממזגת שני מערכי משנה של arr []
// מערך משנה שמאלי: arr [leftIndex..middleIndex]
// מערך משנה ימני: arr [middleIndex + 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; i L [i] = arr [leftIndex + i];
עבור (int j = 0; j R [j] = arr [middleIndex + 1 + j];
// מיזג את המערכים הזמניים בחזרה ל- arr [leftIndex..rightIndex]
// אינדקס ראשוני של מערך משנה שמאלי
int i = 0;
// אינדקס ראשוני של מערך משנה ימני
int j = 0;
// אינדקס ראשוני של מערך משנה ממוזג
int k = leftIndex;
ואילו (i {
אם (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
אַחֵר
{
arr [k] = R [j];
j ++;
}
k ++;
}
// אם ישנם כמה אלמנטים שנותרו ב- L []
// העתק ל- arr []
בעוד (i {
arr [k] = L [i];
i ++;
k ++;
}
// אם ישנם כמה אלמנטים שנותרו ב- R []
// העתק ל- arr []
בעוד (j {
arr [k] = R [j];
j ++;
k ++;
}
}
void 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);
}
// פונקציה להדפסת האלמנטים
// של המערך
בטל printArray (int arr [], גודל int)
{
עבור (int i = 0; אני {
cout << arr [i] << "";
}
cout << endl;
}
// קוד נהג
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int גודל = sizeof (arr) / sizeof (arr [0]);
cout << "מערך לא ממוין:" << endl;
printArray (arr, גודל);
mergeSort (arr, 0, גודל - 1);
cout << "מערך ממוין:" << endl;
printArray (arr, גודל);
החזר 0;
}

תְפוּקָה:

מערך לא ממוין:
16 12 15 13 19 17 11 18 
מערך ממוין:
11 12 13 15 16 17 18 19

יישום JavaScript של אלגוריתם המיזוג למיזוג

להלן הטמעת JavaScript של אלגוריתם המיזוג למיזוג:

// יישום JavaScript של
// מיזוג אלגוריתם למיון
// פונקציה זו ממזגת שני מערכי משנה של arr []
// מערך משנה שמאלי: arr [leftIndex..middleIndex]
// מערך משנה ימני: arr [middleIndex + 1..rightIndex]
מיזוג פונקציות (arr, leftIndex, middleIndex, rightIndex) {
תן ל- leftSubarraySize = middleIndex - leftIndex + 1;
תן ל- RightSubarraySize = rightIndex - middleIndex;
// צור מערכים זמניים
var L = מערך חדש (leftSubarraySize);
var R = מערך חדש (rightSubarraySize);
// העתקת נתונים למערכים זמניים L [] ו- R []
עבור (תן i = 0; אניL [i] = arr [leftIndex + i];
}
עבור (תן j = 0; יR [j] = arr [middleIndex + 1 + j];
}
// מיזג את המערכים הזמניים בחזרה ל- arr [leftIndex..rightIndex]
// אינדקס ראשוני של מערך משנה שמאלי
var i = 0;
// אינדקס ראשוני של מערך משנה ימני
var j = 0;
// אינדקס ראשוני של מערך משנה ממוזג
var k = leftIndex;
ואילו (i {
אם (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
אַחֵר
{
arr [k] = R [j];
j ++;
}
k ++;
}
// אם ישנם כמה אלמנטים שנותרו ב- L []
// העתק ל- arr []
בעוד (i {
arr [k] = L [i];
i ++;
k ++;
}
// אם ישנם כמה אלמנטים שנותרו ב- R []
// העתק ל- arr []
בעוד (j {
arr [k] = R [j];
j ++;
k ++;
}
}
function 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);
}
// פונקציה להדפסת האלמנטים
// של המערך
function printArray (arr, size) {
עבור (תן i = 0; אניdocument.write (arr [i] + "");
}
document.write ("
");
}
// קוד נהג:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
גודל var = אורך arr;
document.write ("מערך לא ממוין:
");
printArray (arr, גודל);
mergeSort (arr, 0, גודל - 1);
document.write ("מערך ממוין:
");
printArray (arr, גודל);

תְפוּקָה:

מערך לא ממוין:
16 12 15 13 19 17 11 18
מערך ממוין:
11 12 13 15 16 17 18 19

קָשׁוּר: תכנות דינמי: דוגמאות, בעיות נפוצות ופתרונות

יישום פיתון של אלגוריתם המיזוג למיזוג

להלן הטמעת הפיתון של אלגוריתם המיזוג למיזוג:

# יישום פייתון של
# מיזוג מיון מיזוג
def mergeSort (arr):
אם len (arr)> 1:
# מציאת האינדקס האמצעי של המערך
middleIndex = len (arr) // 2
# חצי משמאל למערך
L = arr [: middleIndex]
# חצי ימני של המערך
R = arr [middleIndex:]
# מיון המחצית הראשונה של המערך
mergeSort (L)
# מיון המחצית השנייה של המערך
mergeSort (R)
# אינדקס ראשוני של תת-מערך שמאלי
i = 0
# אינדקס ראשוני של מערך משנה ימני
j = 0
# אינדקס ראשוני של מערך משנה ממוזג
k = 0
# העתק נתונים למערכים זמניים L [] ו- R []
ואילו אני אם L [i] arr [k] = L [i]
i = i + 1
אַחֵר:
arr [k] = R [j]
j = j + 1
k = k + 1
# בודק אם יש כמה אלמנטים שנותרו
ואילו אני arr [k] = L [i]
i = i + 1
k = k + 1
ואילו j arr [k] = R [j]
j = j + 1
k = k + 1
# פונקציה להדפסת האלמנטים
מספר המערך
def printArray (arr, גודל):
עבור אני בטווח (גודל):
הדפס (arr [i], end = "")
הדפס()
# קוד נהג
arr = [16, 12, 15, 13, 19, 17, 11, 18]
גודל = len (arr)
הדפס ("מערך לא ממוין:")
printArray (arr, גודל)
mergeSort (arr)
הדפס ("מערך ממוין:")
printArray (arr, גודל)

תְפוּקָה:

מערך לא ממוין:
16 12 15 13 19 17 11 18
מערך ממוין:
11 12 13 15 16 17 18 19

להבין אלגוריתמי מיון אחרים

מיון הוא אחד האלגוריתמים הנפוצים ביותר בתכנות. ניתן למיין אלמנטים בשפות תכנות שונות באמצעות אלגוריתמי מיון שונים כמו מיון מהיר, מיון בועות, מיון מיזוג, מיון הכנסה וכו '.

מיון בועות הוא הבחירה הטובה ביותר אם ברצונך ללמוד על אלגוריתם המיון הפשוט ביותר.

מבוא לאלגוריתם של מיון הבועות

אלגוריתם מיון הבועות: מבוא מצוין למערכי מיון.

קרא הבא

על הסופר