Uvod v algoritem razvrščanja za združevanje

Merge sort je algoritem razvrščanja, ki temelji na tehniki 'deli in osvoji'. To je eden najučinkovitejših algoritmov razvrščanja.

kje lahko kupim kužka v svoji bližini

V tem članku boste izvedeli o delovanju algoritma razvrščanja združevanja, algoritmu razvrščanja združevanja, njegove časovne in prostorske kompleksnosti ter o njegovem izvajanju v različnih programskih jezikih, kot so C ++, Python in JavaScript.

---

---

Kako deluje algoritem razvrščanja za združevanje?

Razvrščanje po združitvi deluje po principu loči in osvoji. Razvrstitev pri združevanju večkrat razčleni matriko v dva enaka podmaza, dokler ni vsaka podmozga sestavljena iz enega samega elementa. Nazadnje se vsi ti podnizi združijo, tako da se dobljeno polje razvrsti.

Ta koncept je mogoče učinkoviteje razložiti s pomočjo primera. Razmislite o nerazvrščeni matriki z naslednjimi elementi: {16, 12, 15, 13, 19, 17, 11, 18}.

Tu algoritem razvrščanja po združitvi razdeli matriko na dve polovici, sam pokliče dve polovici in nato združi dve razvrščeni polovici.

Algoritem združevanja razvrščanja

Spodaj je algoritem združevanja:

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)

Povezano: Kaj je rekurzija in kako jo uporabljate?

---

---

Časovna in prostorska kompleksnost algoritma za združevanje razvrščanja

Algoritem razvrščanja združi lahko izrazimo v obliki naslednje relacije ponavljanja:

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

---

---

Ko rešite to relacijo ponovitve z uporabo glavnega izreka ali metode drevesa ponavljanja, boste dobili rešitev kot O (n logn). Tako je časovna zapletenost algoritma razvrščanja združevanja O (n prijava) .

Najboljši časovni zapletenost vrste združevanja: O (n prijava)

Povprečna časovna zapletenost vrste združevanja: O (n prijava)

Najhujša časovna zapletenost vrste združevanja: O (n prijava)

Povezano: Kaj je zapis Big-O?

Kompleksnost pomožnega prostora algoritma razvrščanja združevanja je O (n) kot n pri izvedbi razvrščanja združevanja je potreben pomožni prostor.

C ++ Izvajanje algoritma za razvrščanje združitve

Spodaj je izvedba algoritma razvrščanja za združevanje v 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;
}

Izhod:

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

JavaScript Izvajanje algoritma za razvrščanje združitve

Spodaj je JavaScript izvedba algoritma razvrščanja za združevanje:

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

Izhod:

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

Sorodno: Dinamično programiranje: primeri, pogoste težave in rešitve

Python implementacija algoritma za razvrščanje združitve

Spodaj je izvedba algoritma razvrščanja za združevanje v Pythonu:

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


Izhod:

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

Razumeti druge algoritme razvrščanja

Razvrščanje je eden najpogosteje uporabljenih algoritmov pri programiranju. Elemente lahko razvrščate v različne programske jezike z različnimi algoritmi razvrščanja, kot so hitro razvrščanje, razvrščanje z mehurčki, združevanje, razvrščanje vstavljanja itd.

Razvrščanje mehurčkov je najboljša izbira, če želite izvedeti o najpreprostejšem algoritmu razvrščanja.

Deliti Deliti Cvrkutati E-naslov Uvod v algoritem razvrščanja mehurčkov

Algoritem razvrščanja mehurčkov: odličen uvod v razvrščanje nizov.

Preberite Naprej Sorodne teme

• Programiranje
• JavaScript
• Python
• Vadnice za kodiranje

O avtorju Yuvraj Chandra(Objavljenih 60 člankov)

Yuvraj je dodiplomski študent računalništva na Univerzi v Delhiju v Indiji. Navdušen je nad spletnim razvojem Full Stack. Ko ne piše, raziskuje globino različnih tehnologij.

Več od Yuvraja Chandre

Naročite se na naše novice

Pridružite se našemu glasilu za tehnične nasvete, ocene, brezplačne e -knjige in ekskluzivne ponudbe!

Kliknite tukaj, če se želite naročiti