Een inleiding tot het bellensorteeralgoritme

Sorteren is een van de meest elementaire bewerkingen die u op gegevens kunt toepassen. U kunt elementen in verschillende programmeertalen sorteren met behulp van verschillende sorteeralgoritmen zoals Quick Sort, Bubble Sort, Merge Sort, Insertion Sort, enz. Bubble Sort is het meest eenvoudige algoritme van al deze.

In dit artikel leer je over de werking van het Bubble Sort-algoritme, de pseudocode van de Bubble Sort algoritme, de complexiteit van tijd en ruimte, en de implementatie ervan in verschillende programmeertalen zoals C++, Python, C en JavaScript.

Hoe werkt het bubbelsorteeralgoritme?

Bubble Sort is het eenvoudigste sorteeralgoritme dat herhaaldelijk door de lijst stapt, aangrenzende elementen vergelijkt en ze verwisselt als ze in de verkeerde volgorde staan. Dit concept kan efficiënter worden uitgelegd aan de hand van een voorbeeld. Beschouw een ongesorteerde array met de volgende elementen: {16, 12, 15, 13, 19}.

Voorbeeld:

Hier worden de aangrenzende elementen vergeleken en als ze niet in oplopende volgorde staan, worden ze verwisseld.

Pseudocode van het bellensorteeralgoritme

in pseudocode, kan het Bubble Sort-algoritme worden uitgedrukt als:

bubbleSorteer (Arr[], grootte)
// lus om toegang te krijgen tot elk array-element
voor i=0 tot maat-1:
// lus om array-elementen te vergelijken
voor j=0 tot maat-i-1:
// vergelijk de aangrenzende elementen
als Arr[j] > Arr[j+1] dan
// verwissel ze
wisselen (Arr[j], Arr[j+1])
stop als
eindigen voor
eindigen voor
einde

Het bovenstaande algoritme verwerkt alle vergelijkingen, zelfs als de array al is gesorteerd. Het kan verder worden geoptimaliseerd door het algoritme te stoppen als de binnenste lus geen swap heeft veroorzaakt. Dit zal de uitvoeringstijd van het algoritme verkorten.

De pseudocode van het geoptimaliseerde Bubble Sort-algoritme kan dus worden uitgedrukt als:

bubbleSorteer (Arr[], grootte)
// lus om toegang te krijgen tot elk array-element
voor i=0 tot maat-1:
// controleer of er wordt gewisseld
verwisseld = false
// lus om array-elementen te vergelijken
voor j=0 tot maat-i-1:
// vergelijk de aangrenzende elementen
als Arr[j] > Arr[j+1] dan
// verwissel ze
wisselen (Arr[j], Arr[j+1])
verwisseld = waar
stop als
eindigen voor
// als er geen elementen zijn verwisseld, betekent dit dat de array nu is gesorteerd en dat de lus wordt verbroken.
indien (niet verwisseld) dan
breken
stop als
eindigen voor
einde

Tijdcomplexiteit en hulpruimte van het belsorteeralgoritme

De tijdscomplexiteit in het slechtste geval van het Bubble Sort Algorithm is O(n^2). Het komt voor wanneer de array in aflopende volgorde staat en u deze in oplopende volgorde wilt sorteren of omgekeerd.

De beste tijdscomplexiteit van het Bubble Sort Algorithm is O(n). Het treedt op wanneer de array al is gesorteerd.

Verwant: Wat is Big-O-notatie?

De gemiddelde tijdscomplexiteit van het Bubble Sort Algorithm is O(n^2). Het treedt op wanneer de elementen van de array in een door elkaar gegooide volgorde staan.

De hulpruimte die nodig is voor het Bubble Sort-algoritme is O(1).

C++ Implementatie van het Bubble Sort Algoritme

Hieronder staat de C++-implementatie van het Bubble Sort-algoritme:

// C++ implementatie van de
// geoptimaliseerd Bubble Sort-algoritme
#include 
namespace std; gebruiken;
// Functie om bellensortering uit te voeren
leegte bubbleSort (int arr[], int size) {
// Loop om toegang te krijgen tot elk element van de array
voor (int i=0; i// Variabele om te controleren of er wordt gewisseld
bool verwisseld = false;
// lus om twee aangrenzende elementen van de array te vergelijken
voor (int j = 0; j < (maat-i-1); j++) {
// Twee aangrenzende array-elementen vergelijken
if (arr[j] > arr[j + 1]) {
// Verwissel beide elementen als ze zijn
// niet in de juiste volgorde
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
verwisseld = waar;
}
}
// Als er geen elementen zijn verwisseld, betekent dit dat de array nu is gesorteerd,
// verbreek dan de lus.
if (verwisseld == false) {
breken;
}
}
}
// Drukt de elementen van de array af
void printArray (int arr[], int size) {
voor (int i = 0; ik < maat; ik++) {
cout << arr[i] << " ";
}
cout << endl;
}
int hoofd() {
int arr[] = {16, 12, 15, 13, 19};
// De lengte van de array vinden
int size = sizeof (arr) / sizeof (arr[0]);
// De gegeven ongesorteerde array afdrukken
cout << "Ongesorteerde array: " << endl;
printArray (arr, grootte);
// De functie bubbleSort() aanroepen
bubbleSort (arr, maat);
// De gesorteerde array afdrukken
cout << "Gesorteerde array in oplopende volgorde:" << endl;
printArray (arr, grootte);
retourneer 0;
}

Uitgang:

Ongesorteerde matrix: 
16 12 15 13 19 
Gesorteerde array in oplopende volgorde:
12 13 15 16 19

Python-implementatie van het bellensorteeralgoritme

Hieronder staat de Python-implementatie van het Bubble Sort-algoritme:

# Python-implementatie van de
# geoptimaliseerd Bubble Sort-algoritme
# Functie om bellensortering uit te voeren
def bubbleSort (arr, grootte):
# Loop om toegang te krijgen tot elk element van de lijst
voor i in bereik (maat-1):
# Variabele om te controleren of er wordt gewisseld
verwisseld = False
# lus om twee aangrenzende elementen van de lijst te vergelijken
voor j binnen bereik (maat-i-1):
# Twee aangrenzende lijstelementen vergelijken
als arr[j] > arr[j+1]:
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
verwisseld = True
# Als er geen elementen zijn verwisseld, betekent dit dat de lijst nu is gesorteerd,
# verbreek dan de lus.
indien verwisseld == False:
breken
# Drukt de elementen van de lijst af
def printArray (arr):
voor element in arr:
print (element, end=" ")
afdrukken("")
arr = [16, 12, 15, 13, 19]
# De lengte van de lijst vinden
maat = len (arr)
# De gegeven ongesorteerde lijst afdrukken
print("Ongesorteerde lijst:")
printArray (arr)
# BubbleSort() functie aanroepen
bubbleSort (arr, grootte)
# De gesorteerde lijst afdrukken
print("Gesorteerde lijst in oplopende volgorde:")
printArray (arr)

Uitgang:

Ongesorteerde lijst:
16 12 15 13 19 
Gesorteerde lijst in oplopende volgorde:
12 13 15 16 19

Verwant: Hoe te gebruiken voor lussen in Python

C Implementatie van het bellensorteeralgoritme

Hieronder staat de C-implementatie van het Bubble Sort-algoritme:

// C implementatie van de
// geoptimaliseerd Bubble Sort-algoritme
#include 
#include 
// Functie om bellensortering uit te voeren
leegte bubbleSort (int arr[], int size) {
// Loop om toegang te krijgen tot elk element van de array
voor (int i=0; i// Variabele om te controleren of er wordt gewisseld
bool verwisseld = false;
// lus om twee aangrenzende elementen van de array te vergelijken
voor (int j = 0; j < (maat-i-1); j++) {
// Twee aangrenzende array-elementen vergelijken
if (arr[j] > arr[j + 1]) {
// Verwissel beide elementen als ze zijn
// niet in de juiste volgorde
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
verwisseld = waar;
}
}
// Als er geen elementen zijn verwisseld, betekent dit dat de array nu is gesorteerd,
// verbreek dan de lus.
if (verwisseld == false) {
breken;
}
}
}
// Drukt de elementen van de array af
void printArray (int arr[], int size) {
voor (int i = 0; ik < maat; ik++) {
printf("%d", arr[i]);
}
printf(" \⁠n ");
}
int hoofd() {
int arr[] = {16, 12, 15, 13, 19};
// De lengte van de array vinden
int size = sizeof (arr) / sizeof (arr[0]);
// De gegeven ongesorteerde array afdrukken
printf("Ongesorteerde matrix: \⁠n");
printArray (arr, grootte);
// De functie bubbleSort() aanroepen
bubbleSort (arr, maat);
// De gesorteerde array afdrukken
printf("Gesorteerde array in oplopende volgorde: \⁠n");
printArray (arr, grootte);
retourneer 0;
}

Uitgang:

Ongesorteerde matrix: 
16 12 15 13 19 
Gesorteerde array in oplopende volgorde: 
12 13 15 16 19

JavaScript-implementatie van het bellensorteeralgoritme

Hieronder staat de JavaScript-implementatie van het Bubble Sort-algoritme:

// JavaScript-implementatie van de
// geoptimaliseerd Bubble Sort-algoritme
// Functie om bellensortering uit te voeren
functie bubbleSort (arr, grootte) {
// Loop om toegang te krijgen tot elk element van de array
voor (laat i=0; ik// Variabele om te controleren of er wordt gewisseld
var verwisseld = onwaar;
// lus om twee aangrenzende elementen van de array te vergelijken
voor (laat j=0; j// Twee aangrenzende array-elementen vergelijken
if (arr[j] > arr[j+1]) {
// Verwissel beide elementen als ze zijn
// niet in de juiste volgorde
laat temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temperatuur;
verwisseld = waar;
}
// Als er geen elementen zijn verwisseld, betekent dit dat de array nu is gesorteerd,
// verbreek dan de lus.
if (verwisseld == false) {
breken;
}
}
}
}
// Drukt de elementen van de array af
functie printArray (arr, grootte) {
voor (laat i=0; ikdocument.schrijven (arr[i] + " ");
}
document.schrijven("
")
}
var arr = [16, 12, 15, 13, 19];
// De lengte van de array vinden
var grootte = arr.lengte;
// De gegeven ongesorteerde array afdrukken
document.write("Ongesorteerde matrix: 
");
printArray (arr, grootte);
// De functie bubbleSort() aanroepen
bubbleSort (arr, maat);
// De gesorteerde array afdrukken
document.write("Gesorteerde array in oplopende volgorde: 
");
printArray (arr, grootte);

Uitgang:

Ongesorteerde matrix:
16 12 15 13 19
Gesorteerde array in oplopende volgorde:
12 15 13 16 19

Nu begrijp je de werking van het bellensorteeralgoritme

Bubble Sort is het eenvoudigste sorteeralgoritme en wordt voornamelijk gebruikt om de basis van sorteren te begrijpen. Bubble Sort kan ook recursief worden geïmplementeerd, maar biedt geen extra voordelen om dit te doen.

Met Python kunt u het Bubble Sort-algoritme gemakkelijk implementeren. Als je niet bekend bent met Python en je reis een kickstart wilt geven, is het een goede keuze om te beginnen met een "Hello World"-script.

Aan de slag met Python met behulp van een "Hello World"-script

Python is een van de meest populaire programmeertalen die tegenwoordig wordt gebruikt. Volg deze tutorial om aan de slag te gaan met je allereerste Python-script.

Lees volgende

Over de auteur