En introduktion til boblesorteringsalgoritmen

Sortering er en af ​​de mest basale operationer, du kan anvende på data. Du kan sortere elementer på forskellige programmeringssprog ved hjælp af forskellige sorteringsalgoritmer som hurtig sortering, boblesortering, flettsortering, indsættelsessortering osv. Bubble Sort er den mest enkle algoritme blandt alle disse.

I denne artikel lærer du om funktionen af ​​Bubble Sort-algoritmen, pseudocode for Bubble Sort algoritme, dens tid og plads kompleksitet og dens implementering på forskellige programmeringssprog som C ++, Python, C og JavaScript.

Hvordan fungerer algoritmen for boblesortering?

Boblesortering er den enkleste sorteringsalgoritme, der gentagne gange går gennem listen, sammenligner tilstødende elementer og bytter dem, hvis de er i den forkerte rækkefølge. 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}.

Eksempel:

Her sammenlignes de tilstødende elementer, og hvis de ikke er i stigende rækkefølge, byttes de.

Pseudokode for Bubble Sort Algorithm

I pseudokode, kan Bubble Sort-algoritmen udtrykkes som:

bubbleSort (Arr [], størrelse)
// loop for at få adgang til hvert array-element
for i = 0 til størrelse-1 gør:
// loop for at sammenligne matrixelementer
for j = 0 til størrelse-i-1 gør:
// sammenligne de tilstødende elementer
hvis Arr [j]> Arr [j + 1] så
// bytt dem
bytte (Arr [j], Arr [j + 1])
Afslut Hvis
slut for
slut for
ende

Ovenstående algoritme behandler alle sammenligninger, selvom arrayet allerede er sorteret. Det kan optimeres yderligere ved at stoppe algoritmen, hvis den indre sløjfe ikke forårsagede nogen swap. Dette reducerer algoritmens udførelsestid.

Således kan pseudokoden for den optimerede Bubble Sort-algoritme udtrykkes som:

bubbleSort (Arr [], størrelse)
// loop for at få adgang til hvert array-element
for i = 0 til størrelse-1 gør:
// kontroller, om der sker bytte
byttet = falsk
// loop for at sammenligne matrixelementer
for j = 0 til størrelse-i-1 gør:
// sammenligne de tilstødende elementer
hvis Arr [j]> Arr [j + 1] så
// bytt dem
bytte (Arr [j], Arr [j + 1])
byttet = sandt
Afslut Hvis
slut for
// hvis der ikke blev byttet nogen elementer, betyder det, at arrayet er sorteret nu, så bryd sløjfen.
hvis (ikke byttet) så
pause
Afslut Hvis
slut for
ende

Tidskompleksitet og hjælpeplads for boblesorteringsalgoritmen

Den værst tænkelige tidskompleksitet af Bubble Sort Algorithm er O (n ^ 2). Det sker, når arrayet er i faldende rækkefølge, og du vil sortere det i stigende rækkefølge eller omvendt.

Den bedste case-tidskompleksitet af Bubble Sort Algorithm er O (n). Det sker, når arrayet allerede er sorteret.

Relaterede: Hvad er Big-O Notation?

Den gennemsnitlige sags tidskompleksitet for Bubble Sort Algorithm er O (n ^ 2). Det sker, når elementerne i arrayet er i blandet rækkefølge.

Hjælpepladsen, der kræves til Bubble Sort-algoritmen, er O (1).

C ++ Implementering af Bubble Sort Algorithm

Nedenfor er C ++ implementeringen af ​​Bubble Sort algoritmen:

// C ++ implementering af
// optimeret Bubble Sort-algoritme
#omfatte 
ved hjælp af namespace std;
// Funktion til at udføre boblesortering
ugyldig bubbleSort (int arr [], int størrelse) {
// Loop for at få adgang til hvert element i arrayet
for (int i = 0; i // Variabel for at kontrollere, om bytte sker
bool swapped = false;
// loop for at sammenligne to tilstødende elementer i arrayet
for (int j = 0; j // Sammenligning af to tilstødende matrixelementer
hvis (arr [j]> arr [j + 1]) {
// Byt begge elementer, hvis de er
// ikke i korrekt rækkefølge
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
byttet = sandt;
}
}
// Hvis der ikke blev byttet nogen elementer betyder det, at arrayet er sorteret nu,
// bryd derefter løkken.
hvis (byttet == falsk) {
pause;
}
}
}
// Udskriver elementerne i arrayet
ugyldig printArray (int arr [], int størrelse) {
for (int i = 0; jeg cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Find længden af ​​arrayet
int størrelse = størrelse af (arr) / størrelse af (arr [0]);
// Udskrivning af det givne usorterede array
cout << "Usorteret matrix:" << endl;
printArray (arr, størrelse);
// Calling bubbleSort () -funktion
bubbleSort (arr, størrelse);
// Udskrivning af det sorterede array
cout << "Sorteret matrix i stigende rækkefølge:" << endl;
printArray (arr, størrelse);
returnere 0;
}

Produktion:

Usorteret matrix: 
16 12 15 13 19 
Sorteret matrix i stigende rækkefølge:
12 13 15 16 19

Python-implementering af boblesorteringsalgoritmen

Nedenfor er Python-implementeringen af ​​Bubble Sort-algoritmen:

# Python implementering af
# optimeret Bubble Sort-algoritme
# Funktion til at udføre boblesortering
def bubbleSort (arr, størrelse):
# Loop for at få adgang til hvert element på listen
for jeg inden for rækkevidde (størrelse-1):
# Variabel for at kontrollere, om bytte sker
byttet = Falsk
# loop for at sammenligne to tilstødende elementer på listen
for j i området (størrelse-i-1):
# Sammenligning af to tilstødende listeelementer
hvis arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = temp
byttet = Sandt
# Hvis der ikke blev byttet nogen elementer, betyder det, at listen er sorteret nu,
# bryd derefter løkken.
hvis byttet == Falsk:
pause
# Udskriver elementerne på listen
def printArray (arr):
for element i arr:
print (element, end = "")
Print("")
arr = [16, 12, 15, 13, 19]
# Find længden af ​​listen
størrelse = len (arr)
# Udskrivning af den givne usorterede liste
print ("Usorteret liste:")
printArray (arr)
# Opkald til bubbleSort () -funktion
bubbleSort (arr, størrelse)
# Udskrivning af den sorterede liste
print ("Sorteret liste i stigende rækkefølge:")
printArray (arr)

Produktion:

Usorteret liste:
16 12 15 13 19 
Sorteret liste i stigende rækkefølge:
12 13 15 16 19

Relaterede: Sådan bruges til sløjfer i Python

C Implementering af boblesorteringsalgoritmen

Nedenfor er C-implementeringen af ​​Bubble Sort-algoritmen:

// C implementering af
// optimeret Bubble Sort-algoritme
#omfatte 
#omfatte 
// Funktion til at udføre boblesortering
ugyldig bubbleSort (int arr [], int størrelse) {
// Loop for at få adgang til hvert element i arrayet
for (int i = 0; i // Variabel for at kontrollere, om bytte sker
bool swapped = false;
// loop for at sammenligne to tilstødende elementer i arrayet
for (int j = 0; j // Sammenligning af to tilstødende matrixelementer
hvis (arr [j]> arr [j + 1]) {
// Byt begge elementer, hvis de er
// ikke i korrekt rækkefølge
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
byttet = sandt;
}
}
// Hvis der ikke blev byttet nogen elementer betyder det, at arrayet er sorteret nu,
// bryd derefter løkken.
hvis (byttet == falsk) {
pause;
}
}
}
// Udskriver elementerne i arrayet
ugyldig printArray (int arr [], int størrelse) {
for (int i = 0; jeg printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Find længden af ​​arrayet
int størrelse = størrelse af (arr) / størrelse af (arr [0]);
// Udskrivning af det givne usorterede array
printf ("Usorteret matrix: \ ⁠n");
printArray (arr, størrelse);
// Calling bubbleSort () -funktion
bubbleSort (arr, størrelse);
// Udskrivning af det sorterede array
printf ("Sorteret matrix i stigende rækkefølge: \ ⁠n");
printArray (arr, størrelse);
returnere 0;
}

Produktion:

Usorteret matrix: 
16 12 15 13 19 
Sorteret matrix i stigende rækkefølge: 
12 13 15 16 19

JavaScript-implementering af Bubble Sort Algorithm

Nedenfor er JavaScript-implementeringen af ​​Bubble Sort-algoritmen:

// JavaScript-implementering af
// optimeret Bubble Sort-algoritme
// Funktion til at udføre boblesortering
funktion bubbleSort (arr, størrelse) {
// Loop for at få adgang til hvert element i arrayet
for (lad i = 0; jeg// Variabel for at kontrollere, om bytte sker
var byttet = falsk;
// loop for at sammenligne to tilstødende elementer i arrayet
for (lad j = 0; j// Sammenligning af to tilstødende matrixelementer
hvis (arr [j]> arr [j + 1]) {
// Byt begge elementer, hvis de er
// ikke i korrekt rækkefølge
lad temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
byttet = sandt;
}
// Hvis der ikke blev byttet nogen elementer betyder det, at arrayet er sorteret nu,
// bryd derefter løkken.
hvis (byttet == falsk) {
pause;
}
}
}
}
// Udskriver elementerne i arrayet
funktion printArray (arr, størrelse) {
for (lad i = 0; jegdocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Find længden af ​​arrayet
var størrelse = arr. længde;
// Udskrivning af det givne usorterede array
document.write ("Usorteret matrix: 
");
printArray (arr, størrelse);
// Calling bubbleSort () -funktion
bubbleSort (arr, størrelse);
// Udskrivning af det sorterede array
document.write ("Sorteret matrix i stigende rækkefølge: 
");
printArray (arr, størrelse);

Produktion:

Usorteret matrix:
16 12 15 13 19
Sorteret matrix i stigende rækkefølge:
12 15 13 16 19

Nu forstår du arbejdet med boblesorteringsalgoritmen

Bubble Sort er den enkleste sorteringsalgoritme og bruges hovedsageligt til at forstå grundlaget for sortering. Bubble Sort kan også implementeres rekursivt, men det giver ingen yderligere fordele ved at gøre det.

Ved hjælp af Python kan du nemt implementere Bubble Sort-algoritmen. Hvis du ikke er bekendt med Python og ønsker at starte din rejse, er det et godt valg at starte med et "Hello World"-script.

Sådan kommer du i gang med Python ved hjælp af et "Hello World" script

Python er et af de mest populære programmeringssprog, der bruges i dag. Følg denne vejledning for at komme i gang med dit allerførste Python-script.

Læs Næste

Om forfatteren