En introduktion till bubblasorteringsalgoritmen

Sortering är en av de mest grundläggande åtgärderna du kan tillämpa på data. Du kan sortera element på olika programmeringsspråk med hjälp av olika sorteringsalgoritmer som Snabbsortering, Bubbelsortering, Sammanfogningssortering, Insättningssortering etc. Bubble Sort är den enklaste algoritmen bland alla dessa.

I den här artikeln lär du dig om hur Bubble Sort-algoritmen fungerar, pseudokoden för Bubble Sort algoritm, dess tids- och rymdkomplexitet och dess implementering på olika programmeringsspråk som C ++, Python, C och JavaScript.

Hur fungerar bubblasorteringsalgoritmen?

Bubblesortering är den enklaste sorteringsalgoritmen som upprepade gånger går igenom listan, jämför intilliggande element och byter dem om de är i fel ordning. Detta koncept kan förklaras mer effektivt med hjälp av ett exempel. Tänk på en osorterad matris med följande element: {16, 12, 15, 13, 19}.

Exempel:

Här jämförs de intilliggande elementen och om de inte är i stigande ordning byts de ut.

Pseudokod för Bubble Sort Algorithm

I pseudokod, Bubble Sort-algoritmen kan uttryckas som:

bubbleSort (Arr [], storlek)
// loop för att komma åt varje arrayelement
för i = 0 till storlek-1 gör:
// loop för att jämföra arrayelement
för j = 0 till storlek-i-1 gör:
// jämför de intilliggande elementen
om Arr [j]> Arr [j + 1] då
// byt dem
byt (Arr [j], Arr [j + 1])
avsluta om
slut för
slut för
slutet

Ovanstående algoritm bearbetar alla jämförelser även om matrisen redan är sorterad. Det kan optimeras ytterligare genom att stoppa algoritmen om den inre slingan inte orsakade någon byte. Detta minskar algoritmens exekveringstid.

Således kan pseudokoden för den optimerade bubbelsorteringsalgoritmen uttryckas som:

bubbleSort (Arr [], storlek)
// loop för att komma åt varje arrayelement
för i = 0 till storlek-1 gör:
// kontrollera om byte sker
bytt = falskt
// loop för att jämföra arrayelement
för j = 0 till storlek-i-1 gör:
// jämför de intilliggande elementen
om Arr [j]> Arr [j + 1] då
// byt dem
byt (Arr [j], Arr [j + 1])
bytt = sant
avsluta om
slut för
// om inga element byttes betyder det att matrisen är sorterad nu, bryt sedan slingan.
om (inte bytt) då
ha sönder
avsluta om
slut för
slutet

Tidskomplexitet och hjälputrymme för bubblasorteringsalgoritmen

Den värsta fallkomplexiteten i Bubble Sort Algorithm är O (n ^ 2). Det inträffar när matrisen är i fallande ordning och du vill sortera den i stigande ordning eller vice versa.

Den bästa fallkomplexiteten i Bubble Sort Algorithm är O (n). Det inträffar när arrayen redan är sorterad.

Relaterad: Vad är Big-O-notering?

Den genomsnittliga fallkomplexiteten för Bubble Sort Algorithm är O (n ^ 2). Det inträffar när elementen i matrisen är i rörlig ordning.

Hjälputrymmet som krävs för Bubble Sort-algoritmen är O (1).

C ++ Implementering av Bubble Sort Algorithm

Nedan följer C ++ -implementeringen av Bubble Sort-algoritmen:

// C ++ implementering av
// optimerad Bubble Sort-algoritm
#omfatta 
använder namnrymd std;
// Funktion för att utföra Bubblesortering
ogiltig bubbleSort (int arr [], int storlek) {
// Loop för att komma åt varje element i arrayen
för (int i = 0; i // Variabel för att kontrollera om byte sker
bool swapped = false;
// loop för att jämföra två intilliggande element i matrisen
för (int j = 0; j // Jämföra två intilliggande arrayelement
om (arr [j]> arr [j + 1]) {
// Byt båda elementen om de är
// inte i rätt ordning
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
bytt = sant;
}
}
// Om inga element byttes betyder det att matrisen är sorterad nu,
// bryt sedan slingan.
if (swapped == false) {
ha sönder;
}
}
}
// Skriver ut elementen i matrisen
ogiltig printArray (int arr [], int storlek) {
för (int i = 0; i cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Hitta längden på matrisen
int storlek = sizeof (arr) / sizeof (arr [0]);
// Skriva ut den angivna osorterade matrisen
cout << "Osorterad matris:" << endl;
printArray (arr, storlek);
// Calling bubbleSort () -funktion
bubbleSort (arr, storlek);
// Skriva ut den sorterade matrisen
cout << "Sorterad matris i stigande ordning:" << endl;
printArray (arr, storlek);
returnera 0;
}

Produktion:

Osorterad matris: 
16 12 15 13 19 
Sorterad matris i stigande ordning:
12 13 15 16 19

Python Implementation of the Bubble Sort Algorithm

Nedan följer Python-implementeringen av Bubble Sort-algoritmen:

# Python-implementering av
# optimerad Bubble Sort-algoritm
# Funktion för att utföra Bubblesortering
def bubbleSort (arr, storlek):
# Loop för att komma åt varje element i listan
för jag inom intervallet (storlek-1):
# Variabel för att kontrollera om byte sker
bytt = Falskt
# loop för att jämföra två intilliggande element i listan
för j inom intervallet (storlek-i-1):
# Jämföra två intilliggande listelement
om arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = temp
bytt = Sant
# Om inga element byttes betyder det att listan är sorterad nu,
# bryt sedan slingan.
om bytt == Falskt:
ha sönder
# Skriver ut elementen i listan
def printArray (arr):
för element i arr:
skriva ut (element, slut = "")
skriva ut("")
arr = [16, 12, 15, 13, 19]
# Hitta längden på listan
storlek = len (arr)
# Skriva ut den osorterade listan
skriva ut ("osorterad lista:")
printArray (arr)
# Calling bubbleSort () -funktion
bubbleSort (arr, storlek)
# Skriva ut den sorterade listan
skriva ut ("Sorterad lista i stigande ordning:")
printArray (arr)

Produktion:

Osorterad lista:
16 12 15 13 19 
Sorterad lista i stigande ordning:
12 13 15 16 19

Relaterad: Hur man använder för loopar i Python

C Implementering av bubblasorteringsalgoritmen

Nedan följer C-implementeringen av Bubble Sort-algoritmen:

// C genomförande av
// optimerad Bubble Sort-algoritm
#omfatta 
#omfatta 
// Funktion för att utföra Bubblesortering
ogiltig bubbleSort (int arr [], int storlek) {
// Loop för att komma åt varje element i arrayen
för (int i = 0; i // Variabel för att kontrollera om byte sker
bool swapped = false;
// loop för att jämföra två intilliggande element i matrisen
för (int j = 0; j // Jämföra två intilliggande arrayelement
om (arr [j]> arr [j + 1]) {
// Byt båda elementen om de är
// inte i rätt ordning
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
bytt = sant;
}
}
// Om inga element byttes betyder det att matrisen är sorterad nu,
// bryt sedan slingan.
if (swapped == false) {
ha sönder;
}
}
}
// Skriver ut elementen i matrisen
ogiltig printArray (int arr [], int storlek) {
för (int i = 0; i printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Hitta längden på matrisen
int storlek = sizeof (arr) / sizeof (arr [0]);
// Skriva ut den angivna osorterade matrisen
printf ("Osorterad matris: \ ⁠n");
printArray (arr, storlek);
// Calling bubbleSort () -funktion
bubbleSort (arr, storlek);
// Skriva ut den sorterade matrisen
printf ("Sorterad matris i stigande ordning: \ ⁠n");
printArray (arr, storlek);
returnera 0;
}

Produktion:

Osorterad matris: 
16 12 15 13 19 
Sorterad matris i stigande ordning: 
12 13 15 16 19

JavaScript-implementering av Bubble Sort Algorithm

Nedan följer JavaScript-implementeringen av Bubble Sort-algoritmen:

// JavaScript-implementering av
// optimerad Bubble Sort-algoritm
// Funktion för att utföra Bubblesortering
funktion bubbleSort (arr, storlek) {
// Loop för att komma åt varje element i arrayen
för (låt i = 0; i// Variabel för att kontrollera om byte sker
var swapped = false;
// loop för att jämföra två intilliggande element i matrisen
för (låt j = 0; j// Jämföra två intilliggande arrayelement
om (arr [j]> arr [j + 1]) {
// Byt båda elementen om de är
// inte i rätt ordning
låt temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
bytt = sant;
}
// Om inga element byttes betyder det att matrisen är sorterad nu,
// bryt sedan slingan.
if (swapped == false) {
ha sönder;
}
}
}
}
// Skriver ut elementen i matrisen
funktion printArray (arr, storlek) {
för (låt i = 0; idocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Hitta längden på matrisen
var storlek = arrlängd;
// Skriva ut den angivna osorterade matrisen
document.write ("Osorterad matris: 
");
printArray (arr, storlek);
// Calling bubbleSort () -funktion
bubbleSort (arr, storlek);
// Skriva ut den sorterade matrisen
document.write ("Sorterad matris i stigande ordning: 
");
printArray (arr, storlek);

Produktion:

Osorterad matris:
16 12 15 13 19
Sorterad matris i stigande ordning:
12 15 13 16 19

Nu förstår du hur bubblasorteringsalgoritmen fungerar

Bubble Sort är den enklaste sorteringsalgoritmen och används främst för att förstå grunden för sortering. Bubble Sort kan också implementeras rekursivt, men det ger inga ytterligare fördelar att göra det.

Med Python kan du enkelt implementera Bubble Sort-algoritmen. Om du inte känner till Python och vill starta din resa är det ett bra val att börja med ett "Hello World" -skript.

Så här kommer du igång med Python med hjälp av ett "Hello World" -skript

Python är ett av de mest populära programmeringsspråken som används idag. Följ den här guiden för att komma igång med ditt allra första Python-skript.

Läs Nästa

Om författaren