Uvod v algoritem razvrščanja mehurčkov

Razvrščanje je ena najosnovnejših operacij, ki jo lahko uporabite za podatke. Elemente lahko razvrščate v različnih programskih jezikih z različnimi algoritmi za razvrščanje, kot so hitro razvrščanje, razvrščanje po mehurčkih, združevanje, razvrščanje med vstavljanjem itd. Razvrstitev mehurčkov je med vsemi najbolj preprost algoritem.

V tem članku boste spoznali delovanje algoritma Bubble Sort, psevdokode Bubble Sort algoritem, njegova časovna in prostorska zapletenost ter njegova izvedba v različnih programskih jezikih, kot so C ++, Python, C in JavaScript.

Kako deluje algoritem razvrščanja mehurčkov?

Razvrstitev po mehurčkih je najpreprostejši algoritem za razvrščanje, ki večkrat prečka seznam, primerja sosednje elemente in jih zamenja, če so v napačnem vrstnem redu. Ta koncept lahko učinkoviteje razložimo s pomočjo primera. Razmislite o nesortirani matriki z naslednjimi elementi: {16, 12, 15, 13, 19}.

Primer:

Tu se primerjajo sosednji elementi in če niso v naraščajočem vrstnem redu, se zamenjajo.

Psevkodo algoritma za razvrščanje mehurčkov

V psevdokodo, algoritem razvrščanja po mehurčkih lahko izrazimo kot:

bubbleSort (Arr [], velikost)
// zanka za dostop do vsakega elementa matrike
za i = 0 do velikosti-1 naredite:
// zanka za primerjavo elementov matrike
za j = 0 do size-i-1 do:
// primerjamo sosednje elemente
če je Arr [j]> Arr [j + 1], potem
// jih zamenjajte
zamenjava (Arr [j], Arr [j + 1])
konec, če
konec za
konec za
konec

Zgornji algoritem obdela vse primerjave, tudi če je polje že razvrščeno. Nadalje ga je mogoče optimizirati z zaustavitvijo algoritma, če notranja zanka ni povzročila zamenjave. To bo skrajšalo čas izvajanja algoritma.

Tako lahko psevdokodo optimiziranega algoritma za razvrščanje po mehurčkih izrazimo kot:

bubbleSort (Arr [], velikost)
// zanka za dostop do vsakega elementa matrike
za i = 0 do velikosti-1 naredite:
// preverimo, ali pride do zamenjave
zamenjano = napačno
// zanka za primerjavo elementov matrike
za j = 0 do size-i-1 do:
// primerjamo sosednje elemente
če je Arr [j]> Arr [j + 1], potem
// jih zamenjajte
zamenjava (Arr [j], Arr [j + 1])
zamenjano = res
konec, če
konec za
// če ni bil zamenjan noben element, to pomeni, da je polje zdaj razvrščeno, nato prekinite zanko.
če (ne zamenja) potem
odmor
konec, če
konec za
konec

Časovna zapletenost in pomožni prostor algoritma razvrščanja mehurčkov

Najslabša časovna zapletenost algoritma razvrščanja mehurčkov je O (n ^ 2). Pojavi se, ko je matrika v padajočem vrstnem redu in jo želite razvrstiti po naraščajočem vrstnem redu ali obratno.

Najbolj primerna časovna zapletenost algoritma razvrščanja mehurčkov je O (n). Pojavi se, ko je polje že razvrščeno.

Sorodno: Kaj je zapis Big-O?

Zapletenost algoritma razvrščanja po mehurčkih je v povprečnem primeru O (n ^ 2). Pojavi se, ko so elementi matrike v zmedenem vrstnem redu.

Pomožni prostor, ki je potreben za algoritem razvrščanja po mehurčkih, je O (1).

C ++ Izvajanje algoritma razvrščanja po mehurčkih

Spodaj je C ++ izvedba algoritma Bubble Sort:

// C ++ izvedba
// optimiziran algoritem razvrščanja po mehurčkih
#include 
uporaba imenskega prostora std;
// Funkcija za izvajanje razvrščanja po mehurčkih
void bubbleSort (int arr [], int size) {
// Zanka za dostop do vsakega elementa polja
za (int i = 0; i // Spremenljivka za preverjanje, ali pride do zamenjave
bool zamenjal = false;
// zanka za primerjavo dveh sosednjih elementov polja
za (int j = 0; j // Primerjava dveh sosednjih elementov matrike
če (arr [j]> arr [j + 1]) {
// Zamenjajte oba elementa, če sta
// ni v pravilnem vrstnem redu
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
zamenjano = resnično;
}
}
// Če ni bil zamenjan noben element, to pomeni, da je polje zdaj razvrščeno,
// nato prekinemo zanko.
če (zamenjano == napačno) {
odmor;
}
}
}
// Natisne elemente polja
void printArray (int arr [], int size) {
za (int i = 0; i cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Iskanje dolžine polja
int size = sizeof (arr) / sizeof (arr [0]);
// Tiskanje dane nesortirane matrike
cout << "Nerazvrščeno polje:" << endl;
printArray (dol, velikost);
// Klicanje funkcije bubbleSort ()
bubbleSort (arr, velikost);
// Tiskanje razvrščenega polja
cout << "Razvrščeno polje v naraščajočem vrstnem redu:" << endl;
printArray (dol, velikost);
vrnitev 0;
}

Izhod:

Nerazvrščena matrika: 
16 12 15 13 19 
Razvrščeno polje v naraščajočem vrstnem redu:
12 13 15 16 19

Python Implementacija algoritma za razvrščanje mehurčkov

Spodaj je izvedba Python algoritma Bubble Sort:

# Python izvedba
# optimiziran algoritem razvrščanja po mehurčkih
# Funkcija za izvedbo razvrščanja po mehurčkih
def bubbleSort (arr, size):
# Loop za dostop do vsakega elementa seznama
za i v območju (velikost-1):
# Spremenljivka za preverjanje, ali pride do zamenjave
zamenjano = False
# zanka za primerjavo dveh sosednjih elementov seznama
za j v območju (velikost-i-1):
# Primerjava dveh sosednjih elementov seznama
če je arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = temp
zamenjano = True
# Če ni bil zamenjan noben element, to pomeni, da je seznam zdaj razvrščen,
# nato prekinite zanko.
če je zamenjano == False:
odmor
# Natisne elemente seznama
def printArray (arr):
za element v arr:
tisk (element, konec = "")
natisni ("")
arr = [16, 12, 15, 13, 19]
# Iskanje dolžine seznama
velikost = len (arr)
# Tiskanje danega nesortiranega seznama
print ("Nerazvrščen seznam:")
printArray (arr)
# Klicanje funkcije bubbleSort ()
bubbleSort (dol, velikost)
# Tiskanje razvrščenega seznama
print ("Razvrščen seznam v naraščajočem vrstnem redu:")
printArray (arr)

Izhod:

Nerazvrščen seznam:
16 12 15 13 19 
Razvrščen seznam v naraščajočem vrstnem redu:
12 13 15 16 19

Sorodno: Kako uporabljati zanke v Pythonu

C Izvajanje algoritma razvrščanja po mehurčkih

Spodaj je izvedba algoritma Bubble Sort:

// C izvedba
// optimiziran algoritem razvrščanja po mehurčkih
#include 
#include 
// Funkcija za izvajanje razvrščanja po mehurčkih
void bubbleSort (int arr [], int size) {
// Zanka za dostop do vsakega elementa polja
za (int i = 0; i // Spremenljivka za preverjanje, ali pride do zamenjave
bool zamenjal = false;
// zanka za primerjavo dveh sosednjih elementov polja
za (int j = 0; j // Primerjava dveh sosednjih elementov matrike
če (arr [j]> arr [j + 1]) {
// Zamenjajte oba elementa, če sta
// ni v pravilnem vrstnem redu
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
zamenjano = resnično;
}
}
// Če ni bil zamenjan noben element, to pomeni, da je polje zdaj razvrščeno,
// nato prekinemo zanko.
če (zamenjano == napačno) {
odmor;
}
}
}
// Natisne elemente polja
void printArray (int arr [], int size) {
za (int i = 0; i printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Iskanje dolžine polja
int size = sizeof (arr) / sizeof (arr [0]);
// Tiskanje dane nesortirane matrike
printf ("Nerazvrščeno polje: \ ⁠n");
printArray (dol, velikost);
// Klicanje funkcije bubbleSort ()
bubbleSort (arr, velikost);
// Tiskanje razvrščenega polja
printf ("Razvrščeno polje v naraščajočem vrstnem redu: \ ⁠n");
printArray (dol, velikost);
vrnitev 0;
}

Izhod:

Nerazvrščena matrika: 
16 12 15 13 19 
Razvrščeno polje v naraščajočem vrstnem redu: 
12 13 15 16 19

Izvajanje JavaScript algoritma razvrščanja po mehurčkih

Spodaj je implementacija algoritma Bubble Sort z uporabo JavaScript:

// JavaScript izvedba
// optimiziran algoritem razvrščanja po mehurčkih
// Funkcija za izvajanje razvrščanja po mehurčkih
function bubbleSort (arr, size) {
// Zanka za dostop do vsakega elementa polja
za (naj je i = 0; jaz// Spremenljivka za preverjanje, ali pride do zamenjave
var zamenjano = napačno;
// zanka za primerjavo dveh sosednjih elementov polja
za (naj bo j = 0; j// Primerjava dveh sosednjih elementov matrike
če (arr [j]> arr [j + 1]) {
// Zamenjajte oba elementa, če sta
// ni v pravilnem vrstnem redu
naj bo temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
zamenjano = resnično;
}
// Če ni bil zamenjan noben element, to pomeni, da je polje zdaj razvrščeno,
// nato prekinemo zanko.
če (zamenjano == napačno) {
odmor;
}
}
}
}
// Natisne elemente polja
funkcija printArray (arr, velikost) {
za (naj je i = 0; jazdocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Iskanje dolžine polja
var size = dolžina arr;
// Tiskanje dane nesortirane matrike
document.write ("Nerazvrščeno polje: 
");
printArray (dol, velikost);
// Klicanje funkcije bubbleSort ()
bubbleSort (arr, velikost);
// Tiskanje razvrščenega polja
document.write ("Razvrščeno polje v naraščajočem vrstnem redu: 
");
printArray (dol, velikost);

Izhod:

Nerazvrščena matrika:
16 12 15 13 19
Razvrščeno polje v naraščajočem vrstnem redu:
12 15 13 16 19

Zdaj razumete delovanje algoritma za razvrščanje mehurčkov

Razvrstitev po mehurčkih je najpreprostejši algoritem za razvrščanje in se v glavnem uporablja za razumevanje temeljev razvrščanja. Razvrstitev mehurčkov je mogoče izvajati tudi rekurzivno, vendar za to ne zagotavlja dodatnih prednosti.

Z uporabo Pythona lahko z lahkoto implementirate algoritem Bubble Sort. Če Pythona ne poznate in želite začeti potovanje, je odlična izbira, če začnete s skriptom "Hello World".

Kako začeti uporabljati Python s pomočjo skripta "Hello World"

Python je eden najbolj priljubljenih programskih jezikov, ki se danes uporablja. Sledite tej vadnici, da začnete s svojim prvim skriptom Python.

Preberite Naprej

O avtorju