O introducere în algoritmul de sortare Merge

Merge sort este un algoritm de sortare bazat pe tehnica „împărțiți și cuceriți”. Este unul dintre cei mai eficienți algoritmi de sortare.

netflix avem probleme cu redarea acestui titlu chiar acum

În acest articol, veți afla despre funcționarea algoritmului de sortare a îmbinării, algoritmul sortării de îmbinare, complexitatea sa de timp și spațiu și implementarea sa în diferite limbaje de programare precum C ++, Python și JavaScript.

---

---

Cum funcționează algoritmul de sortare Merge?

Sortarea Merge funcționează pe principiul divizării și cuceririi. Merge sort descompune în mod repetat o matrice în două subarrayuri egale până când fiecare subarray constă dintr-un singur element. În cele din urmă, toate aceste subarrays sunt îmbinate astfel încât matricea rezultată este sortată.

Acest concept poate fi explicat mai eficient cu ajutorul unui exemplu. Luați în considerare o matrice nesortată cu următoarele elemente: {16, 12, 15, 13, 19, 17, 11, 18}.

Aici, algoritmul de sortare de îmbinare împarte matricea în două jumătăți, se numește singur pentru cele două jumătăți și apoi îmbină cele două jumătăți sortate.

Merge Sort Algorithm

Mai jos este algoritmul sortării de îmbinare:

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)

Related: Ce este recursivitatea și cum o utilizați?

---

---

Complexitatea de timp și spațiu a algoritmului de sortare Merge

Algoritmul de sortare Merge poate fi exprimat sub forma următoarei relații de recurență:

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

---

---

După rezolvarea acestei relații de recurență folosind teorema masterului sau metoda arborelui de recurență, veți obține soluția ca O (n logn). Astfel, complexitatea în timp a algoritmului de sortare a îmbinării este O (n logn) .

Complexitatea în cel mai bun caz a sortării fuziunii: O (n logn)

Complexitatea de timp a cazului mediu a sortării de îmbinare: O (n logn)

Cea mai dificilă complexitate temporală a sortării fuziunii: O (n logn)

Legate de: Ce este notația Big-O?

Complexitatea spațiului auxiliar al algoritmului de sortare merge este Pe) la fel de n spațiul auxiliar este necesar în implementarea sortare fuzionare.

Implementarea C ++ a algoritmului Merge Sort

Mai jos este implementarea C ++ a algoritmului de sortare a combinării:

// 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;
}

Ieșire:

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

Implementarea JavaScript a algoritmului Merge Sort

Mai jos este implementarea JavaScript a algoritmului de sortare a îmbinării:

// 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);

Ieșire:

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

Related: Programare dinamică: exemple, probleme comune și soluții

Implementarea Python a algoritmului Merge Sort

Mai jos este implementarea Python a algoritmului de sortare a îmbinării:

# 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)


Ieșire:

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

Înțelegeți alte algoritmi de sortare

Sortarea este unul dintre cei mai utilizați algoritmi în programare. Puteți sorta elemente în diferite limbaje de programare folosind diferiți algoritmi de sortare, cum ar fi sortare rapidă, sortare cu bule, sortare prin îmbinare, sortare prin inserție etc.

Sortarea cu bule este cea mai bună alegere dacă doriți să aflați despre cel mai simplu algoritm de sortare.

Acțiune Acțiune Tweet E-mail O introducere în algoritmul de sortare cu bule

Algoritmul Bubble Sort: o introducere excelentă în matricile de sortare.

Citiți în continuare Subiecte asemănătoare

• Programare
• JavaScript
• Piton
• Tutoriale de codare

Despre autor Yuvraj Chandra(60 de articole publicate)

Yuvraj este student la Universitatea din Delhi, India. Este pasionat de dezvoltarea web Full Stack. Când nu scrie, explorează profunzimea diferitelor tehnologii.

Mai multe de la Yuvraj Chandra

Aboneaza-te la newsletter-ul nostru

Alăturați-vă newsletter-ului pentru sfaturi tehnice, recenzii, cărți electronice gratuite și oferte exclusive!

Faceți clic aici pentru a vă abona