En introduksjon til boblesorteringsalgoritmen

Sortering er en av de mest grunnleggende operasjonene du kan bruke på data. Du kan sortere elementer på forskjellige programmeringsspråk ved hjelp av forskjellige sorteringsalgoritmer som hurtig sortering, boblesortering, flette sortering, innsettingssortering, etc. Bubble Sort er den mest enkle algoritmen blant alle disse.

I denne artikkelen vil du lære om hvordan Bubble Sort-algoritmen fungerer, pseudokoden til Bubble Sort algoritme, dens tid og romkompleksitet, og implementeringen på forskjellige programmeringsspråk som C ++, Python, C og JavaScript.

Hvordan fungerer algoritmen for boblesortering?

Bubble Sort er den enkleste sorteringsalgoritmen som gjentatte ganger går gjennom listen, sammenligner tilstøtende elementer og bytter dem hvis de er i feil rekkefølge. Dette konseptet kan forklares mer effektivt ved hjelp av et eksempel. Vurder en usortert matrise med følgende elementer: {16, 12, 15, 13, 19}.

Eksempel:

Her sammenlignes de tilstøtende elementene, og hvis de ikke er i stigende rekkefølge, byttes de ut.

Pseudokode for boblesorteringsalgoritmen

I pseudokode, kan Bubble Sort-algoritmen uttrykkes som:

bubbleSort (Arr [], størrelse)
// loop for å få tilgang til hvert arrayelement
for i = 0 til størrelse-1 gjør:
// loop for å sammenligne matriseelementer
for j = 0 til størrelse-i-1 gjør:
// sammenligne de tilstøtende elementene
hvis Arr [j]> Arr [j + 1] da
// bytt dem
bytt (Arr [j], Arr [j + 1])
slutt om
slutt for
slutt for
slutt

Ovennevnte algoritme behandler alle sammenligningene selv om matrisen allerede er sortert. Det kan optimaliseres ytterligere ved å stoppe algoritmen hvis den indre sløyfen ikke forårsaket noe bytte. Dette vil redusere gjennomføringstiden for algoritmen.

Dermed kan pseudokoden til den optimaliserte boblesorteringsalgoritmen uttrykkes som:

bubbleSort (Arr [], størrelse)
// loop for å få tilgang til hvert arrayelement
for i = 0 til størrelse-1 gjør:
// sjekk om bytting skjer
byttet = falsk
// loop for å sammenligne matriseelementer
for j = 0 til størrelse-i-1 gjør:
// sammenligne de tilstøtende elementene
hvis Arr [j]> Arr [j + 1] da
// bytt dem
bytt (Arr [j], Arr [j + 1])
byttet = sant
slutt om
slutt for
// hvis ingen elementer ble byttet ut, betyr det at matrisen er sortert nå, så bryt løkken.
hvis (ikke byttes) da
gå i stykker
slutt om
slutt for
slutt

Tidskompleksitet og hjelpeareal for boblesorteringsalgoritmen

Den verste tilfelle tidskompleksiteten til Bubble Sort Algorithm er O (n ^ 2). Det oppstår når matrisen er i synkende rekkefølge, og du vil sortere den i stigende rekkefølge eller omvendt.

Best-time tidskompleksiteten til Bubble Sort Algorithm er O (n). Det oppstår når matrisen allerede er sortert.

I slekt: Hva er Big-O Notation?

Gjennomsnittlig sakstidskompleksitet for Bubble Sort Algorithm er O (n ^ 2). Det oppstår når elementene i matrisen er i rotet rekkefølge.

Hjelpeplassen som kreves for Bubble Sort-algoritmen er O (1).

C ++ Implementering av Bubble Sort Algorithm

Nedenfor er C ++ implementeringen av Bubble Sort-algoritmen:

// C ++ implementering av
// optimalisert Bubble Sort-algoritme
#inkludere 
bruker navneområde std;
// Funksjon for å utføre boblesortering
ugyldig bubbleSort (int arr [], int størrelse) {
// Loop for å få tilgang til hvert element i matrisen
for (int i = 0; i // Variabel for å sjekke om bytting skjer
bool swapped = false;
// loop for å sammenligne to tilstøtende elementer i matrisen
for (int j = 0; j // Sammenligning av to tilstøtende matriseelementer
hvis (arr [j]> arr [j + 1]) {
// Bytt begge elementene hvis de er
// ikke i riktig rekkefølge
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
byttet = sant;
}
}
// Hvis ingen elementer ble byttet ut, betyr det at matrisen er sortert nå,
// bryt deretter løkken.
hvis (byttet == usann) {
gå i stykker;
}
}
}
// Skriver ut elementene i matrisen
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};
// Finne lengden på matrisen
int size = sizeof (arr) / sizeof (arr [0]);
// Skrive ut den gitte usorterte matrisen
cout << "Usortert matrise:" << endl;
printArray (arr, størrelse);
// Calling bubbleSort () -funksjon
bubbleSort (arr, størrelse);
// Skriver ut den sorterte matrisen
cout << "Sortert matrise i stigende rekkefølge:" << endl;
printArray (arr, størrelse);
retur 0;
}

Produksjon:

Usortert matrise: 
16 12 15 13 19 
Sortert matrise i stigende rekkefølge:
12 13 15 16 19

Python Implementation of the Bubble Sort Algorithm

Nedenfor er Python-implementeringen av Bubble Sort-algoritmen:

# Python implementering av
# optimalisert Bubble Sort-algoritme
# Funksjon for å utføre boblesortering
def bubbleSort (arr, størrelse):
# Sløyfe for å få tilgang til hvert element i listen
for jeg innen rekkevidde (størrelse 1):
# Variabel for å sjekke om bytting skjer
byttet = Falsk
# loop for å sammenligne to tilstøtende elementer på listen
for j innen rekkevidde (størrelse-i-1):
# Sammenligning av to tilstøtende listeelementer
hvis arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = temp
byttet = Sant
# Hvis ingen elementer ble byttet ut, betyr det at listen er sortert nå,
# bryt deretter løkken.
hvis byttet == Falsk:
gå i stykker
# Skriver ut elementene i listen
def printArray (arr):
for element i arr:
print (element, end = "")
skrive ut("")
arr = [16, 12, 15, 13, 19]
# Finne lengden på listen
størrelse = len (arr)
# Skrive ut den gitte usorterte listen
skriv ut ("Usortert liste:")
printArray (arr)
# Calling bubbleSort () -funksjon
bubbleSort (arr, størrelse)
# Skriver ut den sorterte listen
utskrift ("Sortert liste i stigende rekkefølge:")
printArray (arr)

Produksjon:

Usortert liste:
16 12 15 13 19 
Sortert liste i stigende rekkefølge:
12 13 15 16 19

I slekt: Hvordan bruke for løkker i Python

C Implementering av boblesorteringsalgoritmen

Nedenfor er C-implementeringen av Bubble Sort-algoritmen:

// C implementering av
// optimalisert Bubble Sort-algoritme
#inkludere 
#inkludere 
// Funksjon for å utføre boblesortering
ugyldig bubbleSort (int arr [], int størrelse) {
// Loop for å få tilgang til hvert element i matrisen
for (int i = 0; i // Variabel for å sjekke om bytting skjer
bool swapped = false;
// loop for å sammenligne to tilstøtende elementer i matrisen
for (int j = 0; j // Sammenligning av to tilstøtende matriseelementer
hvis (arr [j]> arr [j + 1]) {
// Bytt begge elementene hvis de er
// ikke i riktig rekkefølge
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
byttet = sant;
}
}
// Hvis ingen elementer ble byttet ut, betyr det at matrisen er sortert nå,
// bryt deretter løkken.
hvis (byttet == usann) {
gå i stykker;
}
}
}
// Skriver ut elementene i matrisen
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};
// Finne lengden på matrisen
int size = sizeof (arr) / sizeof (arr [0]);
// Skrive ut den gitte usorterte matrisen
printf ("Usortert matrise: \ ⁠n");
printArray (arr, størrelse);
// Calling bubbleSort () -funksjon
bubbleSort (arr, størrelse);
// Skriver ut den sorterte matrisen
printf ("Sortert matrise i stigende rekkefølge: \ ⁠n");
printArray (arr, størrelse);
retur 0;
}

Produksjon:

Usortert matrise: 
16 12 15 13 19 
Sortert matrise i stigende rekkefølge: 
12 13 15 16 19

JavaScript-implementering av boblesorteringsalgoritmen

Nedenfor er JavaScript-implementeringen av Bubble Sort-algoritmen:

// JavaScript-implementering av
// optimalisert Bubble Sort-algoritme
// Funksjon for å utføre boblesortering
funksjon bubbleSort (arr, størrelse) {
// Loop for å få tilgang til hvert element i matrisen
for (la i = 0; Jeg// Variabel for å sjekke om bytting skjer
var byttet = falsk;
// loop for å sammenligne to tilstøtende elementer i matrisen
for (la j = 0; j// Sammenligning av to tilstøtende matriseelementer
hvis (arr [j]> arr [j + 1]) {
// Bytt begge elementene hvis de er
// ikke i riktig rekkefølge
la temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
byttet = sant;
}
// Hvis ingen elementer ble byttet ut, betyr det at matrisen er sortert nå,
// bryt deretter løkken.
hvis (byttet == usann) {
gå i stykker;
}
}
}
}
// Skriver ut elementene i matrisen
funksjon printArray (arr, størrelse) {
for (la i = 0; Jegdocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Finne lengden på matrisen
var størrelse = arr. lengde;
// Skrive ut den gitte usorterte matrisen
document.write ("Usortert matrise: 
");
printArray (arr, størrelse);
// Calling bubbleSort () -funksjon
bubbleSort (arr, størrelse);
// Skriver ut den sorterte matrisen
document.write ("Sortert matrise i stigende rekkefølge: 
");
printArray (arr, størrelse);

Produksjon:

Usortert matrise:
16 12 15 13 19
Sortert matrise i stigende rekkefølge:
12 15 13 16 19

Nå forstår du bruken av boblesorteringsalgoritmen

Bubble Sort er den enkleste sorteringsalgoritmen og brukes hovedsakelig til å forstå grunnlaget for sortering. Bubble Sort kan også implementeres rekursivt, men det gir ingen ekstra fordeler å gjøre det.

Ved hjelp av Python kan du enkelt implementere Bubble Sort-algoritmen. Hvis du ikke er kjent med Python og ønsker å starte reisen, er det et godt valg å starte med et "Hello World" -skript.

Hvordan komme i gang med Python ved hjelp av et "Hello World" -skript

Python er et av de mest populære programmeringsspråkene som brukes i dag. Følg denne opplæringen for å komme i gang med ditt aller første Python-skript.

Les Neste

Om forfatteren