Úvod do algoritmu triedenia bublín

Triedenie je jednou z najzákladnejších operácií, ktoré môžete s dátami vykonať. Prvky môžete triediť v rôznych programovacích jazykoch pomocou rôznych triediacich algoritmov, ako sú rýchle triedenie, triedenie podľa bublín, zlúčenie, triedenie podľa vloženia atď. Bubble Sort je najjednoduchší algoritmus spomedzi všetkých týchto.

V tomto článku sa dozviete o fungovaní algoritmu Bubble Sort, pseudokódu Bubble Sort algoritmus, jeho časová a priestorová zložitosť a jeho implementácia v rôznych programovacích jazykoch ako C ++, Python, C a JavaScript.

Ako funguje algoritmus triedenia bublín?

Bubble Sort je najjednoduchší algoritmus triedenia, ktorý opakovane prechádza zoznamom, porovnáva susedné prvky a zamieňa ich, ak sú v nesprávnom poradí. Tento koncept je možné efektívnejšie vysvetliť pomocou príkladu. Zvážte netriedené pole s nasledujúcimi prvkami: {16, 12, 15, 13, 19}.

Príklad:

Tu sa porovnajú susedné prvky, a ak nie sú vo vzostupnom poradí, vymenia sa.

Pseudokód algoritmu triedenia bublín

V pseudokode, algoritmus Bubble Sort možno vyjadriť ako:

bubbleSort (Arr [], veľkosť)
// slučka na prístup ku každému prvku poľa
pre i = 0 až veľkosť-1 urobte:
// slučka na porovnanie prvkov poľa
pre j = 0 až veľkosť-i-1 urobte:
// porovnaj susedné prvky
ak Arr [j]> Arr [j + 1] potom
// vymeniť ich
swap (Arr [j], Arr [j + 1])
koniec Ak
koniec pre
koniec pre
koniec

Vyššie uvedený algoritmus spracuje všetky porovnania, aj keď je pole už zoradené. Môže sa ďalej optimalizovať zastavením algoritmu, ak vnútorná slučka nespôsobila žiadny swap. To zníži čas vykonania algoritmu.

Takže pseudokód optimalizovaného algoritmu Bubble Sort možno vyjadriť ako:

bubbleSort (Arr [], veľkosť)
// slučka na prístup ku každému prvku poľa
pre i = 0 až veľkosť-1 urobte:
// skontrolovať, či dôjde k zámene
vymenený = nepravda
// slučka na porovnanie prvkov poľa
pre j = 0 až veľkosť-i-1 urobte:
// porovnaj susedné prvky
ak Arr [j]> Arr [j + 1] potom
// vymeniť ich
swap (Arr [j], Arr [j + 1])
vymenené = pravda
koniec Ak
koniec pre
// ak neboli zamenené žiadne prvky, čo znamená, že pole je teraz zoradené, potom prerušte slučku.
ak (nevymenené) potom
prestávka
koniec Ak
koniec pre
koniec

Časová zložitosť a pomocný priestor algoritmu triedenia bublín

Najhoršia časová zložitosť Bubble Sort Algorithm je O (n ^ 2). Vyskytuje sa, keď je pole v zostupnom poradí a chcete ho zoradiť vzostupne alebo naopak.

Najlepšia časová zložitosť algoritmu triedenia bublín je O (n). Vyskytuje sa, keď je pole už zoradené.

Súvisiace: Čo je to Big-O notácia?

Priemerná časová zložitosť Bubble Sort Algorithm je O (n ^ 2). Nastáva, keď sú prvky poľa v neusporiadanom poradí.

Pomocný priestor požadovaný pre algoritmus Bubble Sort je O (1).

C ++ implementácia algoritmu triedenia bublín

Ďalej uvádzame implementáciu algoritmu Bubble Sort v jazyku C ++:

// C ++ implementácia
// optimalizovaný algoritmus Bubble Sort
#include 
pomocou namespace std;
// Funkcia na vykonávanie bublinového triedenia
void bubbleSort (int arr [], int size) {
// Smyčka na prístup ku každému prvku poľa
pre (int i = 0; i // Premenná na kontrolu, či dôjde k zámene
bool swapped = false;
// slučka na porovnanie dvoch susedných prvkov poľa
pre (int j = 0; j // Porovnanie dvoch susedných prvkov poľa
if (arr [j]> arr [j + 1]) {
// Zamieňajte obidva prvky, ak sú
// nie je v správnom poradí
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = teplota;
vymenený = true;
}
}
// Ak neboli zamenené žiadne prvky, znamená to, že pole je teraz zoradené,
// potom prelomi slucku.
if (zamenené == false) {
prestávka;
}
}
}
// Vypíše prvky poľa
void printArray (int arr [], int size) {
pre (int i = 0; i cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Nájdenie dĺžky poľa
int size = sizeof (arr) / sizeof (arr [0]);
// Tlač daného netriedeného poľa
cout << "Netriedené pole:" << endl;
printArray (veľkosť, veľkosť);
// Volanie funkcie bubbleSort ()
bubbleSort (arr, veľkosť);
// Tlač zoradeného poľa
cout << "Zoradené vo vzostupnom poradí:" << endl;
printArray (veľkosť, veľkosť);
návrat 0;
}

Výkon:

Netriedené pole: 
16 12 15 13 19 
Zoradené pole vzostupne:
12 13 15 16 19

Implementácia algoritmu triedenia bublín podľa Pythonu

Nižšie je uvedená implementácia algoritmu Bubble Sort v jazyku Python:

# Pythonová implementácia
# optimalizovaný algoritmus Bubble Sort
# Funkcia na vykonanie bublinového triedenia
def bubbleSort (arr, veľkosť):
# Slučka pre prístup k jednotlivým prvkom zoznamu
pre i v rozsahu (veľkosť-1):
# Premenná na kontrolu, či dôjde k zámene
vymenený = False
slučka # na porovnanie dvoch susedných prvkov zoznamu
pre j v rozsahu (veľkosť-i-1):
# Porovnanie dvoch susedných prvkov zoznamu
ak arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = tepl
zamenené = Pravda
# Ak neboli zamenené žiadne prvky, znamená to, že zoznam je teraz zoradený,
# potom pretrhni slučku.
ak je zamenený == False:
prestávka
# Vytlačí prvky zoznamu
def printArray (arr):
pre vložený prvok:
print (element, end = "")
print ("")
arr = [16, 12, 15, 13, 19]
# Nájdenie dĺžky zoznamu
size = len (arr)
# Tlač daného netriedeného zoznamu
print ("Nezoradený zoznam:")
printArray (arr)
# Volanie funkcie bubbleSort ()
bubbleSort (arr, veľkosť)
# Tlač zoradeného zoznamu
print ("Zoradený zoznam vzostupne:")
printArray (arr)

Výkon:

Netriedený zoznam:
16 12 15 13 19 
Zoradené vo vzostupnom poradí:
12 13 15 16 19

Súvisiace: Ako sa používa pre slučky v Pythone

C Implementácia algoritmu triedenia bublín

Nižšie je uvedená implementácia C algoritmu Bubble Sort:

// C implementácia
// optimalizovaný algoritmus Bubble Sort
#include 
#include 
// Funkcia na vykonávanie bublinového triedenia
void bubbleSort (int arr [], int size) {
// Smyčka na prístup ku každému prvku poľa
pre (int i = 0; i // Premenná na kontrolu, či dôjde k zámene
bool swapped = false;
// slučka na porovnanie dvoch susedných prvkov poľa
pre (int j = 0; j // Porovnanie dvoch susedných prvkov poľa
if (arr [j]> arr [j + 1]) {
// Zamieňajte obidva prvky, ak sú
// nie je v správnom poradí
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = teplota;
vymenený = true;
}
}
// Ak neboli zamenené žiadne prvky, znamená to, že pole je teraz zoradené,
// potom prelomi slucku.
if (zamenené == false) {
prestávka;
}
}
}
// Vypíše prvky poľa
void printArray (int arr [], int size) {
pre (int i = 0; i printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Nájdenie dĺžky poľa
int size = sizeof (arr) / sizeof (arr [0]);
// Tlač daného netriedeného poľa
printf ("Netriedené pole: \ ⁠n");
printArray (veľkosť, veľkosť);
// Volanie funkcie bubbleSort ()
bubbleSort (arr, veľkosť);
// Tlač zoradeného poľa
printf ("Zoradené pole vo vzostupnom poradí: \ ⁠n");
printArray (veľkosť, veľkosť);
návrat 0;
}

Výkon:

Netriedené pole: 
16 12 15 13 19 
Zoradené pole vzostupne: 
12 13 15 16 19

Implementácia JavaScriptu algoritmu triedenia bublín

Nižšie je uvedená implementácia algoritmu Bubble Sort do jazyka JavaScript:

// Implementácia JavaScriptu
// optimalizovaný algoritmus Bubble Sort
// Funkcia na vykonávanie bublinového triedenia
function bubbleSort (arr, size) {
// Smyčka na prístup ku každému prvku poľa
pre (nech i = 0; i// Premenná na kontrolu, či dôjde k zámene
var swapped = false;
// slučka na porovnanie dvoch susedných prvkov poľa
pre (nech j = 0; j// Porovnanie dvoch susedných prvkov poľa
if (arr [j]> arr [j + 1]) {
// Zamieňajte obidva prvky, ak sú
// nie je v správnom poradí
let temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = teplota;
vymenený = true;
}
// Ak neboli zamenené žiadne prvky, znamená to, že pole je teraz zoradené,
// potom prelomi slucku.
if (zamenené == false) {
prestávka;
}
}
}
}
// Vypíše prvky poľa
funkcia printArray (veľkosť, veľkosť) {
pre (nech i = 0; idocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Nájdenie dĺžky poľa
var veľkosť = dorazová dĺžka;
// Tlač daného netriedeného poľa
document.write ("Netriedené pole: 
");
printArray (veľkosť, veľkosť);
// Volanie funkcie bubbleSort ()
bubbleSort (arr, veľkosť);
// Tlač zoradeného poľa
document.write ("Zoradené pole vo vzostupnom poradí: 
");
printArray (veľkosť, veľkosť);

Výkon:

Netriedené pole:
16 12 15 13 19
Zoradené pole vzostupne:
12 15 13 16 19

Teraz rozumiete fungovaniu algoritmu triedenia bublín

Bubble Sort je najjednoduchší algoritmus triedenia a používa sa hlavne na pochopenie základov triedenia. Bubble Sort je možné implementovať aj rekurzívne, ale neposkytuje pre to žiadne ďalšie výhody.

Pomocou Pythonu môžete ľahko implementovať algoritmus Bubble Sort. Ak Python nepoznáte a chcete začať svoju cestu, skvelá voľba je začať skriptom „Hello World“.

Ako začať s programom Python pomocou skriptu „Hello World“

Python je dnes jedným z najpopulárnejších programovacích jazykov. Podľa tohto tutoriálu môžete začať s úplne prvým skriptom Python.

Prečítajte si Ďalej

O autorovi