Flettsortering er en sorteringsalgoritme baseret på "del og sejr" -teknikken. Det er en af ​​de mest effektive sorteringsalgoritmer.

I denne artikel lærer du om funktionen af ​​flettsorteringsalgoritmen, algoritmen for flettesorteringen, dens tid og rum kompleksitet, og dens implementering i forskellige programmeringssprog som C ++, Python og JavaScript.

Hvordan fungerer den flette sorteringsalgoritme?

Flet sortering fungerer på princippet om opdeling og erobring. Flettsorter nedbryder en række gentagne gange i to lige store underarrays, indtil hvert underarray består af et enkelt element. Endelig flettes alle disse underarrays, så den resulterende matrix 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 opdeler flettsorteringsalgoritmen arrayet i to halvdele, kalder sig på de to halvdele og fletter derefter de to sorterede halvdele.

Flet sorteringsalgoritme

Nedenfor er algoritmen for flettsorteringen:

instagram viewer 
MergeSort (arr [], leftIndex, rightIndex)
hvis leftIndex> = rightIndex
Vend tilbage
andet
Find det midterste indeks, der deler arrayet i to halvdele: 
middleIndex = leftIndex + (rightIndex-leftIndex) / 2
Call mergeSort () i første halvdel: 
Call mergeSort (arr, leftIndex, middleIndex)
Call mergeSort () til anden halvdel:
Call mergeSort (arr, middleIndex + 1, rightIndex)
Flet de to halvdele sorteret i trin 2 og 3:
Opkaldsfletning (arr, leftIndex, middleIndex, rightIndex)

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

Tids- og rumkompleksitet af Merge Sort Algorithm

Flettsorteringsalgoritmen kan udtrykkes i form af følgende gentagelsesrelation:

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

Efter at have løst dette gentagelsesforhold ved hjælp af mesterens sætning eller gentagelsestræmetoden får du løsningen som O (n logn). Således er tidskompleksiteten af ​​flettsorteringsalgoritmen O (n logn).

Den bedste case-tidskompleksitet af fusionssorteringen: O (n logn)

Den gennemsnitlige sags tidskompleksitet af fusionssorteringen: O (n logn)

Den mest worst-case tidskompleksitet af fusionen sortering: O (n logn)

Relaterede: Hvad er Big-O Notation?

Hjælpepladsens kompleksitet af algoritmen for fusionssortering er På) som n der kræves hjælpeplads i implementeringen af ​​flettsorteringen.

C ++ Implementering af Merge Sort Algorithm

Nedenfor er C ++ implementeringen af ​​flettsorteringsalgoritmen: 

// C ++ implementering af
// flette sorteringsalgoritme
#omfatte 
ved hjælp af namespace std;
// Denne funktion fletter to underarrays af arr []
// Venstre subarray: arr [leftIndex..middleIndex]
// Højre underarray: arr [middleIndex + 1..rightIndex]
ugyldig fletning (int arr [], int leftIndex, int middleIndex, int rightIndex)
{
int leftSubarraySize = middleIndex - leftIndex + 1;
int rightSubarraySize = rightIndex - middleIndex;
// Opret midlertidige arrays
int L [leftSubarraySize], R [rightSubarraySize];
// Kopiering af data til midlertidige matriser L [] og R []
for (int i = 0; i L [i] = arr [leftIndex + i];
for (int j = 0; j R [j] = arr [middleIndex + 1 + j];
// Flet de midlertidige arrays tilbage til arr [leftIndex..rightIndex]
// Indledende indeks for venstre subarray
int i = 0;
// Indledende indeks for højre subarray
int j = 0;
// Indledende indeks over fusioneret underarray
int k = leftIndex;
mens (i {
hvis (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
andet
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Hvis der er nogle resterende elementer i L []
// Kopiér til arr []
mens (i {
arr [k] = L [i];
i ++;
k ++;
}
// Hvis der er nogle resterende elementer i R []
// Kopiér til arr []
mens (j {
arr [k] = R [j];
j ++;
k ++;
}
}
ugyldig mergeSort (int arr [], int leftIndex, int rightIndex)
{
hvis (leftIndex> = rightIndex)
{
Vend tilbage;
}
int middleIndex = leftIndex + (rightIndex - leftIndex) / 2;
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
fusionere (arr, leftIndex, middleIndex, rightIndex);
}
// Funktion til at udskrive elementerne
// af arrayet
ugyldig printArray (int arr [], int størrelse)
{
for (int i = 0; jeg {
cout << arr [i] << "";
}
cout << endl;
}
// Førerkode
int main ()
{
int arr [] = {16, 12, 15, 13, 19, 17, 11, 18};
int størrelse = størrelse af (arr) / størrelse af (arr [0]);
cout << "Usorteret array:" << endl;
printArray (arr, størrelse);
mergeSort (arr, 0, størrelse - 1);
cout << "Sorteret matrix:" << endl;
printArray (arr, størrelse);
returnere 0;
}

Produktion: 

Usorteret matrix:
16 12 15 13 19 17 11 18 
Sorteret matrix:
11 12 13 15 16 17 18 19

JavaScript-implementering af Merge Sort Algorithm

Nedenfor er JavaScript-implementeringen af ​​flettsorteringsalgoritmen: 

// JavaScript-implementering af
// flette sorteringsalgoritme
// Denne funktion fletter to underarrays af arr []
// Venstre subarray: arr [leftIndex..middleIndex]
// Højre underarray: arr [middleIndex + 1..rightIndex]
funktionsfletning (arr, leftIndex, middleIndex, rightIndex) {
lad leftSubarraySize = middleIndex - leftIndex + 1;
lad rightSubarraySize = rightIndex - middleIndex;
// Opret midlertidige arrays
var L = ny matrix (leftSubarraySize);
var R = ny matrix (rightSubarraySize);
// Kopiering af data til midlertidige matriser L [] og R []
for (lad i = 0; jegL [i] = arr [leftIndex + i];
}
for (lad j = 0; jR [j] = arr [middleIndex + 1 + j];
}
// Flet de midlertidige arrays tilbage til arr [leftIndex..rightIndex]
// Indledende indeks for venstre subarray
var i = 0;
// Indledende indeks for højre subarray
var j = 0;
// Indledende indeks over fusioneret underarray
var k = leftIndex;
mens (i {
hvis (L [i] <= R [j])
{
arr [k] = L [i];
i ++;
}
andet
{
arr [k] = R [j];
j ++;
}
k ++;
}
// Hvis der er nogle resterende elementer i L []
// Kopiér til arr []
mens (i {
arr [k] = L [i];
i ++;
k ++;
}
// Hvis der er nogle resterende elementer i R []
// Kopiér til arr []
mens (j {
arr [k] = R [j];
j ++;
k ++;
}
}
funktion mergeSort (arr, leftIndex, rightIndex) {
hvis (leftIndex> = rightIndex) {
Vend tilbage
}
var middleIndex = leftIndex + parseInt ((rightIndex - leftIndex) / 2);
mergeSort (arr, leftIndex, middleIndex);
mergeSort (arr, middleIndex + 1, rightIndex);
fusionere (arr, leftIndex, middleIndex, rightIndex);
}
// Funktion til at udskrive elementerne
// af arrayet
funktion printArray (arr, størrelse) {
for (lad i = 0; jegdocument.write (arr [i] + "");
}
document.write ("
");
}
// Førerkode:
var arr = [16, 12, 15, 13, 19, 17, 11, 18];
var størrelse = arr. længde;
document.write ("Usorteret matrix:
");
printArray (arr, størrelse);
mergeSort (arr, 0, størrelse - 1);
document.write ("Sorteret matrix:
");
printArray (arr, størrelse);

Produktion: 

Usorteret matrix:
16 12 15 13 19 17 11 18
Sorteret matrix:
11 12 13 15 16 17 18 19

Relaterede: Dynamisk programmering: Eksempler, almindelige problemer og løsninger

Python-implementering af Merge Sort Algorithm

Nedenfor er Python-implementeringen af ​​flettsorteringsalgoritmen: 

# Python implementering af
# flet sorteringsalgoritme
def mergeSort (arr):
hvis len (arr)> 1:
# Find det midterste indeks for arrayet
middleIndex = len (arr) // 2
# Venstre halvdel af arrayet
L = arr [: middleIndex]
# Højre halvdel af arrayet
R = arr [middleIndex:]
# Sortering af den første halvdel af arrayet
mergeSort (L)
# Sortering af anden halvdel af arrayet
mergeSort (R)
# Indledende indeks for venstre subarray
i = 0
# Indledende indeks for højre subarray
j = 0
# Indledende indeks over fusioneret underarray
k = 0
# Kopier data til temp-arrays L [] og R []
mens jeg hvis L [i] arr [k] = L [i]
i = i + 1
andet:
arr [k] = R [j]
j = j + 1
k = k + 1
# Kontrollerer, om der er nogle resterende elementer
mens jeg arr [k] = L [i]
i = i + 1
k = k + 1
mens j arr [k] = R [j]
j = j + 1
k = k + 1
# Funktion til at udskrive elementerne
# af arrayet
def printArray (arr, størrelse):
for jeg inden for rækkevidde (størrelse):
print (arr [i], slut = "")
Print()
# Førerkode
arr = [16, 12, 15, 13, 19, 17, 11, 18]
størrelse = len (arr)
print ("Usorteret matrix:")
printArray (arr, størrelse)
mergeSort (arr)
print ("Sorteret matrix:")
printArray (arr, størrelse)

Produktion: 

Usorteret matrix:
16 12 15 13 19 17 11 18
Sorteret matrix:
11 12 13 15 16 17 18 19

Forstå andre sorteringsalgoritmer

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

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

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 (27 artikler offentliggjort)

Yuvraj er en bachelorstudent i datalogi ved University of Delhi, Indien. Han brænder for Full Stack Webudvikling. Når han ikke skriver, udforsker han dybden af ​​forskellige teknologier.

Mere fra Yuvraj Chandra

Abonner på vores nyhedsbrev

Deltag i vores nyhedsbrev for tekniske tip, anmeldelser, gratis e-bøger og eksklusive tilbud!

Et trin mere !!!

Bekræft din e-mail-adresse i den e-mail, vi lige har sendt dig.

.