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

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

כיצד להאיץ דיסק קשיח

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

---

---

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

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

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

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

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

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

MergeSort(arr[], leftIndex, rightIndex)
if leftIndex >= rightIndex
return
else
Find the middle index that divides the array into two halves:
middleIndex = leftIndex + (rightIndex-leftIndex)/2
Call mergeSort() for the first half:
Call mergeSort(arr, leftIndex, middleIndex)
Call mergeSort() for the second half:
Call mergeSort(arr, middleIndex+1, rightIndex)
Merge the two halves sorted in step 2 and 3:
Call merge(arr, leftIndex, middleIndex, rightIndex)

קשור: מהו רקורסיה וכיצד אתה משתמש בה?

---

---

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

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

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

---

---

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

מורכבות הזמן במקרה הטוב ביותר של המיזוג: O (n התחברות)

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

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

קָשׁוּר: מהו סימון Big-O?

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

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

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

// C++ implementation of the
// merge sort algorithm
#include
using namespace std;
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
void merge(int arr[], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
int L[leftSubarraySize], R[rightSubarraySize];
// Copying data to temporary arrays L[] and R[]
for (int i = 0; i L[i] = arr[leftIndex + i];
for (int j = 0; j R[j] = arr[middleIndex + 1 + j];
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
int i = 0;
// Initial index of Right subarray
int j = 0;
// Initial index of merged subarray
int k = leftIndex;
while (i {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i {
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int leftIndex, int rightIndex)
{
if(leftIndex >= rightIndex)
{
return;
}
int middleIndex = leftIndex + (rightIndex - leftIndex)/2;
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}

// Function to print the elements
// of the array
void printArray(int arr[], int size)
{
for (int i = 0; i {
cout << arr[i] << ' ';
}
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 16, 12, 15, 13, 19, 17, 11, 18 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << 'Unsorted array:' << endl;
printArray(arr, size);
mergeSort(arr, 0, size - 1);
cout << 'Sorted array:' << endl;
printArray(arr, size);
return 0;
}

תְפוּקָה:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19

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

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

// JavaScript implementation of the
// merge sort algorithm
// This function merges two subarrays of arr[]
// Left subarray: arr[leftIndex..middleIndex]
// Right subarray: arr[middleIndex+1..rightIndex]
function merge(arr, leftIndex, middleIndex, rightIndex) {
let leftSubarraySize = middleIndex - leftIndex + 1;
let rightSubarraySize = rightIndex - middleIndex;
// Create temporary arrays
var L = new Array(leftSubarraySize);
var R = new Array(rightSubarraySize);
// Copying data to temporary arrays L[] and R[]
for(let i = 0; i L[i] = arr[leftIndex + i];
}
for (let j = 0; j R[j] = arr[middleIndex + 1 + j];
}
// Merge the temporary arrays back into arr[leftIndex..rightIndex]
// Initial index of Left subarray
var i = 0;
// Initial index of Right subarray
var j = 0;
// Initial index of merged subarray
var k = leftIndex;
while (i {
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
// If there're some remaining elements in L[]
// Copy to arr[]
while (i {
arr[k] = L[i];
i++;
k++;
}
// If there're some remaining elements in R[]
// Copy to arr[]
while (j {
arr[k] = R[j];
j++;
k++;
}
}
function mergeSort(arr, leftIndex, rightIndex) {
if(leftIndex >= rightIndex) {
return
}
var middleIndex = leftIndex + parseInt((rightIndex - leftIndex)/2);
mergeSort(arr, leftIndex, middleIndex);
mergeSort(arr, middleIndex+1, rightIndex);
merge(arr, leftIndex, middleIndex, rightIndex);
}
// Function to print the elements
// of the array
function printArray(arr, size) {
for(let i = 0; i document.write(arr[i] + ' ');
}
document.write('
');
}
// Driver code:
var arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ];
var size = arr.length;
document.write('Unsorted array:
');
printArray(arr, size);
mergeSort(arr, 0, size - 1);
document.write('Sorted array:
');
printArray(arr, size);

תְפוּקָה:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19

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

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

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

# Python implementation of the
# merge sort algorithm
def mergeSort(arr):
if len(arr) > 1:
# Finding the middle index of the array
middleIndex = len(arr)//2
# Left half of the array
L = arr[:middleIndex]
# Right half of the array
R = arr[middleIndex:]
# Sorting the first half of the array
mergeSort(L)
# Sorting the second half of the array
mergeSort(R)
# Initial index of Left subarray
i = 0
# Initial index of Right subarray
j = 0
# Initial index of merged subarray
k = 0
# Copy data to temp arrays L[] and R[]
while i if L[i] arr[k] = L[i]
i = i + 1
else:
arr[k] = R[j]
j = j + 1
k = k + 1
# Checking if there're some remaining elements
while i arr[k] = L[i]
i = i + 1
k = k + 1
while j arr[k] = R[j]
j = j + 1
k = k + 1
# Function to print the elements
# of the array
def printArray(arr, size):
for i in range(size):
print(arr[i], end=' ')
print()

# Driver code
arr = [ 16, 12, 15, 13, 19, 17, 11, 18 ]
size = len(arr)
print('Unsorted array:')
printArray(arr, size)
mergeSort(arr)
print('Sorted array:')
printArray(arr, size)


תְפוּקָה:

Unsorted array:
16 12 15 13 19 17 11 18
Sorted array:
11 12 13 15 16 17 18 19

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

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

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

לַחֲלוֹק לַחֲלוֹק צִיוּץ אימייל מבוא לאלגוריתם מיון הבועות

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

קרא הבא נושאים קשורים

• תִכנוּת
• JavaScript
• פִּיתוֹן
• הדרכות קידוד

על הסופר יובראג 'צ'נדרה(פורסמו 60 מאמרים)

יובראג 'הוא סטודנט לתואר ראשון במדעי המחשב באוניברסיטת דלהי, הודו. הוא נלהב מ- Full Stack Web Development. כשהוא לא כותב, הוא בוחן את עומק הטכנולוגיות השונות.

עוד מאת Yuvraj Chandra

הירשם לניוזלטר שלנו

הצטרף לניוזלטר שלנו לקבלת טיפים, סקירות, ספרים אלקטרוניים בחינם ומבצעים בלעדיים!

לחצו כאן להרשמה