Uvod u algoritam sortiranja mjehurića

Sortiranje je jedna od najosnovnijih operacija koje možete primijeniti na podatke. Elemente možete razvrstati u različitim programskim jezicima pomoću različitih algoritama za sortiranje kao što su Brzo sortiranje, Bubble Sort, Merge Sort, Insertion Sort itd. Bubble Sort je najjednostavniji algoritam među svima njima.

U ovom ćete članku saznati kako funkcionira algoritam sortiranja mjehurića, pseudokod kôda sortiranja mjehurića algoritam, njegova vremenska i prostorna složenost i njegova implementacija u razne programske jezike poput C ++, Python, C i JavaScript.

Kako djeluje algoritam sortiranja mjehurića?

Bubble Sort je najjednostavniji algoritam za sortiranje koji neprestano korača kroz popis, uspoređuje susjedne elemente i zamjenjuje ih ako su u pogrešnom redoslijedu. Ovaj se koncept može učinkovitije objasniti uz pomoć primjera. Razmotrite nesortirani niz sa sljedećim elementima: {16, 12, 15, 13, 19}.

Primjer:

Ovdje se uspoređuju susjedni elementi i ako nisu u rastućem redoslijedu, zamjenjuju se.

Pseudokod algoritma sortiranja mjehurića

U pseudokodu, algoritam sortiranja mjehurića može se izraziti kao:

bubbleSort (Arr [], veličina)
// petlja za pristup svakom elementu niza
za i = 0 do size-1 učinite:
// petlja za usporedbu elemenata niza
za j = 0 do size-i-1 učinite:
// uspoređujemo susjedne elemente
ako je Arr [j]> Arr [j + 1] onda
// zamijenite ih
zamijeni (Arr [j], Arr [j + 1])
završi ako
kraj za
kraj za
kraj

Gornji algoritam obrađuje sve usporedbe, čak i ako je niz već sortiran. Može se dodatno optimizirati zaustavljanjem algoritma ako unutarnja petlja nije uzrokovala zamjenu. To će smanjiti vrijeme izvršavanja algoritma.

Dakle, pseudokod optimiziranog algoritma Bubble Sort može se izraziti kao:

bubbleSort (Arr [], veličina)
// petlja za pristup svakom elementu niza
za i = 0 do size-1 učinite:
// provjeriti dolazi li do zamjene
zamijenjeno = lažno
// petlja za usporedbu elemenata niza
za j = 0 do size-i-1 učinite:
// uspoređujemo susjedne elemente
ako je Arr [j]> Arr [j + 1] onda
// zamijenite ih
zamijeni (Arr [j], Arr [j + 1])
zamijenjeno = točno
završi ako
kraj za
// ako nijedan element nije zamijenjen, to znači da je niz sada sortiran, tada prekinite petlju.
ako (nije zamijenjeno) onda
pauza
završi ako
kraj za
kraj

Složenost vremena i pomoćni prostor algoritma sortiranja mjehurića

Najlošija vremenska složenost algoritma sortiranja mjehurića je O (n ^ 2). To se događa kada je niz u opadajućem redoslijedu i želite ga sortirati u rastućem redoslijedu ili obrnuto.

Vremenska složenost algoritma sortiranja mjehurića je O (n). To se događa kada je niz već sortiran.

Povezano: Što je oznaka Big-O?

Prosječna vremenska složenost algoritma sortiranja mjehurića je O (n ^ 2). Događa se kada su elementi niza pomiješanim redoslijedom.

Pomoćni prostor potreban za algoritam sortiranja mjehurića je O (1).

C ++ Implementacija algoritma sortiranja mjehurića

Ispod je implementacija C ++ algoritma Bubble Sort:

// C ++ implementacija
// optimizirani algoritam sortiranja mjehurića
#include 
pomoću prostora imena std;
// Funkcija izvođenja sortiranja mjehurića
void bubbleSort (int arr [], int veličina) {
// Petlja za pristup svakom elementu niza
za (int i = 0; i // Varijabla za provjeru da li dolazi do zamjene
bool zamijenjen = lažno;
// petlja za usporedbu dva susjedna elementa niza
za (int j = 0; j // Usporedba dva susjedna elementa niza
ako (arr [j]> arr [j + 1]) {
// Zamijenite oba elementa ako jesu
// nije u ispravnom redoslijedu
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
zamijenjeno = točno;
}
}
// Ako nijedan element nije zamijenjen, to znači da je niz sada sortiran,
// zatim prekinite petlju.
if (zamijenjeno == false) {
pauza;
}
}
}
// Ispisuje elemente niza
void printArray (int arr [], int veličina) {
za (int i = 0; i cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Pronalaženje duljine niza
int veličina = veličina (arr) / veličina (arr [0]);
// Ispis datog nerazvrstanog polja
cout << "Nesortirani niz:" << endl;
printArray (arr, veličina);
// Pozivanje funkcije bubbleSort ()
bubbleSort (arr, veličina);
// Ispis razvrstanog niza
cout << "Sortirani niz u rastućem redoslijedu:" << endl;
printArray (arr, veličina);
return 0;
}

Izlaz:

Nesortirani niz: 
16 12 15 13 19 
Sortirani niz u rastućem redoslijedu:
12 13 15 16 19

Python implementacija algoritma sortiranja mjehurića

Ispod je Python implementacija algoritma Bubble Sort:

# Python implementacija
# optimiziran algoritam sortiranja mjehurića
# Funkcija za izvođenje mjehurića
def bubbleSort (arr, veličina):
# Petlja za pristup svakom elementu popisa
za i u rasponu (veličina-1):
# Varijabla za provjeru dolazi li do zamjene
zamijenjeno = Lažno
# petlja za usporedbu dva susjedna elementa popisa
za j u rasponu (veličina-i-1):
# Usporedba dva susjedna elementa popisa
ako je arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = temp
zamijenjeno = Istina
# Ako niti jedan element nije zamijenjen, to znači da je popis sada sortiran,
# onda prekini petlju.
ako je zamijenjeno == False:
pauza
# Ispisuje elemente popisa
def printArray (arr):
za element u arr:
ispis (element, kraj = "")
ispis ("")
arr = [16, 12, 15, 13, 19]
# Pronalaženje duljine popisa
veličina = len (arr)
# Ispis datog nerazvrstanog popisa
ispis ("Nerazvrstani popis:")
printArray (arr)
# Pozivanje funkcije bubbleSort ()
bubbleSort (arr, veličina)
# Ispis razvrstanog popisa
print ("Poredani popis u rastućem redoslijedu:")
printArray (arr)

Izlaz:

Nerazvrstani popis:
16 12 15 13 19 
Poredani popis u rastućem redoslijedu:
12 13 15 16 19

Povezano: Kako se koristi za petlje u Pythonu

C Provedba algoritma sortiranja mjehurića

Ispod je C implementacija algoritma Bubble Sort:

// C provedba
// optimizirani algoritam sortiranja mjehurića
#include 
#include 
// Funkcija izvođenja sortiranja mjehurića
void bubbleSort (int arr [], int veličina) {
// Petlja za pristup svakom elementu niza
za (int i = 0; i // Varijabla za provjeru da li dolazi do zamjene
bool zamijenjen = lažno;
// petlja za usporedbu dva susjedna elementa niza
za (int j = 0; j // Usporedba dva susjedna elementa niza
ako (arr [j]> arr [j + 1]) {
// Zamijenite oba elementa ako jesu
// nije u ispravnom redoslijedu
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
zamijenjeno = točno;
}
}
// Ako nijedan element nije zamijenjen, to znači da je niz sada sortiran,
// zatim prekinite petlju.
if (zamijenjeno == false) {
pauza;
}
}
}
// Ispisuje elemente niza
void printArray (int arr [], int veličina) {
za (int i = 0; i printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Pronalaženje duljine niza
int veličina = veličina (arr) / veličina (arr [0]);
// Ispis datog nerazvrstanog polja
printf ("Nesortirani niz: \ ⁠n");
printArray (arr, veličina);
// Pozivanje funkcije bubbleSort ()
bubbleSort (arr, veličina);
// Ispis razvrstanog niza
printf ("Sortirani niz u rastućem redoslijedu: \ ⁠n");
printArray (arr, veličina);
return 0;
}

Izlaz:

Nesortirani niz: 
16 12 15 13 19 
Sortirani niz u rastućem redoslijedu: 
12 13 15 16 19

JavaScript implementacija algoritma sortiranja mjehurića

Ispod je JavaScript implementacija algoritma Bubble Sort:

// JavaScript implementacija
// optimizirani algoritam sortiranja mjehurića
// Funkcija izvođenja sortiranja mjehurića
function bubbleSort (arr, size) {
// Petlja za pristup svakom elementu niza
za (neka je i = 0; ja// Varijabla za provjeru da li dolazi do zamjene
var zamijenjeno = lažno;
// petlja za usporedbu dva susjedna elementa niza
za (neka j = 0; j// Usporedba dva susjedna elementa niza
ako (arr [j]> arr [j + 1]) {
// Zamijenite oba elementa ako jesu
// nije u ispravnom redoslijedu
neka temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
zamijenjeno = točno;
}
// Ako nijedan element nije zamijenjen, to znači da je niz sada sortiran,
// zatim prekinite petlju.
if (zamijenjeno == false) {
pauza;
}
}
}
}
// Ispisuje elemente niza
funkcija printArray (arr, veličina) {
za (neka je i = 0; jadocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Pronalaženje duljine niza
var veličina = dužina arr.length;
// Ispis datog nerazvrstanog polja
document.write ("Nesortirani niz: 
");
printArray (arr, veličina);
// Pozivanje funkcije bubbleSort ()
bubbleSort (arr, veličina);
// Ispis razvrstanog niza
document.write ("Sortirani niz u rastućem redoslijedu: 
");
printArray (arr, veličina);

Izlaz:

Nesortirani niz:
16 12 15 13 19
Sortirani niz u rastućem redoslijedu:
12 15 13 16 19

Sada razumijete kako funkcionira algoritam sortiranja mjehurića

Bubble Sort je najjednostavniji algoritam sortiranja i uglavnom se koristi za razumijevanje temelja sortiranja. Bubble Sort se također može implementirati rekurzivno, ali ne pruža dodatne prednosti za to.

Koristeći Python, s lakoćom možete implementirati algoritam sortiranja mjehurića. Ako vam Python nije poznat i želite započeti putovanje, započinjanje skriptom "Hello World" izvrstan je izbor.

Kako započeti s Pythonom pomoću skripte "Hello World"

Python je jedan od najpopularnijih programskih jezika koji se danas koristi. Slijedite ovaj vodič za početak rada s vašom prvom Python skriptom.

Pročitajte Dalje

O autoru