En introduktion til flette -sorteringsalgoritmen

En introduktion til flette -sorteringsalgoritmen

Fletningssortering er en sorteringsalgoritme baseret på 'divider og erobre' teknikken. Det er en af ​​de mest effektive sorteringsalgoritmer.





hvordan man læser mac harddisk på windows

I denne artikel lærer du om funktionen af ​​flette -sorteringsalgoritmen, sammensmeltningssortens algoritme, dens tid og rumkompleksitet og dens implementering på forskellige programmeringssprog som C ++, Python og JavaScript.





Hvordan fungerer flette -sorteringsalgoritmen?

Fletningssortering fungerer efter princippet om opdeling og erobring. Fletningssortering nedbryder gentagne gange et array til to lige underarrays, indtil hvert delarray består af et enkelt element. Endelig flettes alle disse underarrays således, at det resulterende array sorteres.





Dette koncept kan forklares mere effektivt ved hjælp af et eksempel. Overvej et usorteret array med følgende elementer: {16, 12, 15, 13, 19, 17, 11, 18}.

Her deler flette -sorteringsalgoritmen matrixen i to halvdele, kalder sig selv for de to halvdele og fletter derefter de to sorterede halvdele.



Flet sorteringsalgoritme

Nedenfor er algoritmen for fletningssorteren:

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)

Relateret: Hvad er rekursion, og hvordan bruger du det?





Tid og rum Kompleksitet af flette sorteringsalgoritmen

Merge -sorteringsalgoritmen kan udtrykkes i form af følgende gentagelsesrelation:

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





Efter at have løst denne tilbagefaldsrelation ved hjælp af masterens sætning eller metoden til tilbagevendende træ, får du løsningen som O (n logn). Tidskompleksiteten af ​​flette -sorteringsalgoritmen er således O (n logn) .

Tidskompleksiteten i bedste tilfælde af flette-sorteringen: O (n logn)

Kompleksitetens gennemsnitlige sagstids kompleksitet: O (n logn)

Tidens kompleksitet i værste tilfælde af fletningssorteringen: O (n logn)

Relaterede: Hvad er Big-O Notation?

Hjælperummets kompleksitet af flette sorteringsalgoritmen er På) som n ekstra plads er påkrævet i implementeringen af ​​sammensmeltningssortering.

C ++ Implementering af flette -sorteringsalgoritmen

Nedenfor er C ++ implementeringen af ​​flette sorteringsalgoritmen:

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

Produktion:

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

JavaScript -implementering af flette -sorteringsalgoritmen

Nedenfor er JavaScript -implementeringen af ​​flette -sorteringsalgoritmen:

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

Produktion:

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

Relateret: Dynamisk programmering: eksempler, almindelige problemer og løsninger

Python -implementering af flette -sorteringsalgoritmen

Nedenfor er Python -implementeringen af ​​flette -sorteringsalgoritmen:

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

Produktion:

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

Forstå andre sorteringsalgoritmer

Sortering er en af ​​de mest anvendte algoritmer inden for programmering. Du kan sortere elementer på forskellige programmeringssprog ved hjælp af forskellige sorteringsalgoritmer som hurtig sortering, boblesortering, flettesortering, indsættelsessortering osv.

Boblesortering er det bedste valg, hvis du vil lære mere om den enkleste sorteringsalgoritme.

Del Del Tweet E -mail En introduktion til boblesorteringsalgoritmen

Bubble Sort -algoritmen: en glimrende introduktion til sorteringsarrays.

Læs Næste
Relaterede emner
  • Programmering
  • JavaScript
  • Python
  • Kodning Tutorials
Om forfatteren Yuvraj Chandra(60 artikler udgivet)

Yuvraj er en datalogi bachelorstuderende ved University of Delhi, Indien. Han brænder for Full Stack Web Development. Når han ikke skriver, undersøger han dybden af ​​forskellige teknologier.

Mere fra Yuvraj Chandra

Abonner på vores nyhedsbrev

Tilmeld dig vores nyhedsbrev for at få tekniske tips, anmeldelser, gratis e -bøger og eksklusive tilbud!

Klik her for at abonnere