Ievads apvienošanas kārtošanas algoritmā

Apvienot šķirošanu ir šķirošanas algoritms, kura pamatā ir “sadalīt un iekarot” tehnika. Tas ir viens no visefektīvākajiem šķirošanas algoritmiem.

kā novērst 100% diska izmantošanu

Šajā rakstā jūs uzzināsit par sapludināšanas kārtošanas algoritma darbību, apvienošanas kārtošanas algoritmu, tā laiku un telpas sarežģītību un tā ieviešanu dažādās programmēšanas valodās, piemēram, C ++, Python un JavaScript.

---

---

Kā darbojas apvienošanas kārtošanas algoritms?

Apvienošanas kārtošana darbojas pēc sadalīšanas un iekarošanas principa. Apvienošanas kārtošana atkārtoti sadala masīvu divos vienādos apakšslāņos, līdz katrs apakšmasīts sastāv no viena elementa. Visbeidzot, visi šie apakšmasīvi tiek apvienoti tā, lai iegūtais masīvs tiktu sakārtots.

Šo jēdzienu var efektīvāk izskaidrot, izmantojot piemēru. Apsveriet nešķirotu masīvu ar šādiem elementiem: {16, 12, 15, 13, 19, 17, 11, 18}.

Šeit apvienošanas kārtošanas algoritms sadala masīvu divās daļās, sauc sevi par abām pusēm un pēc tam apvieno abas sakārtotās puses.

Apvienot kārtošanas algoritmu

Zemāk ir sapludināšanas kārtošanas algoritms:

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)

Saistīts: Kas ir rekursija un kā to izmantot?

---

---

Apvienošanas kārtošanas algoritma laika un telpas sarežģītība

Apvienošanas kārtošanas algoritmu var izteikt šādas atkārtošanās relācijas veidā:

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

---

---

Pēc šīs atkārtošanās relācijas atrisināšanas, izmantojot maģistra teorēmu vai atkārtošanās koka metodi, jūs saņemsiet risinājumu kā O (n logn). Tādējādi apvienošanas kārtošanas algoritma laika sarežģītība ir O (n pieteikšanās) .

Apvienošanas veida labākā laika sarežģītība: O (n pieteikšanās)

Apvienošanas veida vidējā gadījuma laika sarežģītība: O (n pieteikšanās)

Apvienošanas veida sliktākā laika sarežģītība: O (n pieteikšanās)

Saistīts: Kas ir Big-O apzīmējums?

Palīgtelpas sarežģītība Apvienošanas kārtošanas algoritms ir O (n) kā n sapludināšanas kārtošanas ieviešanā ir nepieciešama papildu telpa.

Apvienošanas kārtošanas algoritma C ++ ieviešana

Zemāk ir sapludināšanas kārtošanas algoritma C ++ ieviešana:

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

Izeja:

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

Apvienošanas kārtošanas algoritma JavaScript ieviešana

Zemāk ir sapludināšanas kārtošanas algoritma JavaScript ieviešana:

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

Izeja:

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

Saistītie: Dinamiskā programmēšana: piemēri, izplatītas problēmas un risinājumi

Apvienošanas kārtošanas algoritma Python ieviešana

Zemāk ir sapludināšanas kārtošanas algoritma Python ieviešana:

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


Izeja:

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

Izprotiet citus šķirošanas algoritmus

Kārtošana ir viens no visbiežāk izmantotajiem programmēšanas algoritmiem. Jūs varat kārtot elementus dažādās programmēšanas valodās, izmantojot dažādus šķirošanas algoritmus, piemēram, ātro kārtošanu, burbuļu kārtošanu, sapludināšanas kārtošanu, ievietošanas kārtošanu utt.

Burbuļu kārtošana ir labākā izvēle, ja vēlaties uzzināt par vienkāršāko šķirošanas algoritmu.

Kopīgot Kopīgot Čivināt E -pasts Ievads burbuļu kārtošanas algoritmā

Burbuļu kārtošanas algoritms: lielisks ievads masīvu šķirošanā.

Lasīt Tālāk Saistītās tēmas

• Programmēšana
• JavaScript
• Python
• Kodēšanas apmācības

Par autoru Yuvraj Chandra(60 raksti publicēti)

Yuvraj ir datorzinātņu bakalaura students Deli universitātē, Indijā. Viņš aizraujas ar Full Stack tīmekļa izstrādi. Kad viņš neraksta, viņš pēta dažādu tehnoloģiju dziļumu.

Vairāk no Yuvraj Chandra

Abonējiet mūsu biļetenu

Pievienojieties mūsu informatīvajam izdevumam, lai iegūtu tehniskus padomus, pārskatus, bezmaksas e -grāmatas un ekskluzīvus piedāvājumus!

Noklikšķiniet šeit, lai abonētu