Sissejuhatus ühendamise sortimisalgoritmi

Ühendamise sort on sorteerimisalgoritm, mis põhineb jagamise ja vallutamise tehnikal. See on üks tõhusamaid sortimisalgoritme.

kuidas Facebooki postitusele kollaaži teha

Sellest artiklist saate teada ühendamise sortimise algoritmi töö, ühendamise sortimise algoritmi, selle aja ja ruumi keerukuse ning selle rakendamise kohta erinevates programmeerimiskeeltes nagu C ++, Python ja JavaScript.

---

---

Kuidas ühendamise sortimise algoritm töötab?

Merge sort töötab jagamise ja vallutamise põhimõttel. Ühendamissort jagab massiivi korduvalt kaheks võrdseks alammassiiviks, kuni iga alammassiiv koosneb ühest elemendist. Lõpuks ühendatakse kõik need alammassiivid nii, et saadud massiiv sorteeritakse.

Seda mõistet saab näite abil tõhusamalt selgitada. Kaaluge sorteerimata massiivi, mis sisaldab järgmisi elemente: {16, 12, 15, 13, 19, 17, 11, 18}.

Siin jagamise sortimise algoritm jagab massiivi kaheks pooleks, nimetab ennast kaheks pooleks ja ühendab seejärel kaks sorteeritud poolt.

Ühendamise sortimisalgoritm

Allpool on ühendamise sortimise algoritm:

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)

Seotud: Mis on rekursioon ja kuidas seda kasutada?

---

---

Ühendamise sortimisalgoritmi ajaline ja ruumiline keerukus

Ühendamise sortimisalgoritmi saab väljendada järgmise kordussuhte kujul:

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

---

---

Pärast selle kordussuhte lahendamist kapteni teoreemi või korduspuu meetodi abil saate lahenduse O (n logn). Seega on ühendamise sortimise algoritmi ajaline keerukus O (n logn) .

Liitmise parimal juhul ajaline keerukus: O (n logn)

Ühendamissordi keskmise aja keerukus: O (n logn)

Ühendamise tüübi halvim ajaline keerukus: O (n logn)

Seotud: Mis on Big-O märge?

Abiruumi keerukus ühendamise sortimise algoritm on Peal) nagu n ühendamise sortimise rakendamisel on vaja lisaruumi.

Ühendamise sortimisalgoritmi C ++ rakendamine

Allpool on ühendamise sortimise algoritmi C ++ rakendamine.

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

Väljund:

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

Ühendamise sortimisalgoritmi JavaScripti rakendamine

Allpool on ühendamise sortimise algoritmi JavaScripti rakendus.

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

Väljund:

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

Seotud: Dünaamiline programmeerimine: näited, levinumad probleemid ja lahendused

Ühendamise sortimisalgoritmi rakendamine Pythonis

Allpool on ühendamise sortimise algoritmi Pythoni rakendamine:

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


Väljund:

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

Mõista teisi sortimisalgoritme

Sortimine on programmeerimisel üks enim kasutatud algoritme. Saate sortida elemente erinevates programmeerimiskeeltes, kasutades erinevaid sortimisalgoritme, nagu kiire sortimine, mullide sortimine, ühendamise sortimine, sisestamise sortimine jne.

Mullide sortimine on parim valik, kui soovite õppida tundma lihtsaimat sortimisalgoritmi.

Jaga Jaga Piiksuma E -post Sissejuhatus mullide sortimise algoritmi

Mullide sortimise algoritm: suurepärane sissejuhatus massiivide sortimisse.

Loe edasi Seotud teemad

• Programmeerimine
• JavaScript
• Python
• Kodeerimise õpetused

Autori kohta Yuvraj Chandra(60 artiklit avaldatud)

Yuvraj on arvutiteaduse bakalaureuseõppe üliõpilane Indias Delhi ülikoolis. Ta on kirglik Full Stacki veebiarenduse vastu. Kui ta ei kirjuta, uurib ta erinevate tehnoloogiate sügavust.

Veel Yuvraj Chandrast

Telli meie uudiskiri

Liituge meie uudiskirjaga, et saada tehnilisi näpunäiteid, ülevaateid, tasuta e -raamatuid ja eksklusiivseid pakkumisi!

Tellimiseks klõpsake siin