Įvadas į burbulų rūšiavimo algoritmą

Rūšiavimas yra viena iš pagrindinių operacijų, kurią galite pritaikyti duomenims. Elementus galite rūšiuoti skirtingomis programavimo kalbomis naudodami įvairius rūšiavimo algoritmus, tokius kaip „Quick Sort“, „Bubble Sort“, „Merge Sort“, „Insertion Sort“ ir kt. „Bubble Sort“ yra pats paprasčiausias algoritmas tarp visų šių.

Šiame straipsnyje sužinosite apie „Bubble Sort“ algoritmo, „Bubble Sort“ pseudokodo, veikimą algoritmas, jo laiko ir erdvės sudėtingumas ir įgyvendinimas įvairiomis programavimo kalbomis, tokiomis kaip C ++, Python, C ir „JavaScript“.

Kaip veikia burbulų rūšiavimo algoritmas?

„Bubble Sort“ yra paprasčiausias rūšiavimo algoritmas, kuris pakartotinai pereina sąrašą, palygina gretimus elementus ir keičia juos, jei jie yra neteisinga tvarka. Šią sąvoką galima efektyviau paaiškinti pavyzdžiu. Apsvarstykite nerūšiuotą masyvą su šiais elementais: {16, 12, 15, 13, 19}.

Pavyzdys:

Čia lyginami gretimi elementai ir, jei jie nėra didėjimo tvarka, jie keičiami.

Burbulo rūšiavimo algoritmo pseudokodas

Pseudokode, „Bubble Sort“ algoritmą galima išreikšti taip:

„bubbleSort“ (Arr [], dydis)
// kilpa prieiti prie kiekvieno masyvo elemento
i = 0 iki 1 dydžio:
// kilpa masyvo elementams palyginti
jei j = 0 iki dydžio-i-1, atlikite:
// palyginkite gretimus elementus
jei Arr [j]> Arr [j + 1] tada
// juos sukeisti
sukeisti (Arr [j], Arr [j + 1])
pabaiga jei
pabaigos
pabaigos
galas

Aukščiau pateiktas algoritmas apdoroja visus palyginimus, net jei masyvas jau yra rūšiuojamas. Tai galima toliau optimizuoti sustabdžius algoritmą, jei vidinė kilpa nesukėlė jokio apsikeitimo. Tai sumažins algoritmo vykdymo laiką.

Taigi optimizuoto „Bubble Sort“ algoritmo pseudokodą galima išreikšti taip:

„bubbleSort“ (Arr [], dydis)
// kilpa prieiti prie kiekvieno masyvo elemento
i = 0 iki 1 dydžio:
// patikrinkite, ar įvyksta apsikeitimas
sukeista = klaidinga
// kilpa masyvo elementams palyginti
jei j = 0 iki dydžio-i-1, atlikite:
// palyginkite gretimus elementus
jei Arr [j]> Arr [j + 1] tada
// juos sukeisti
sukeisti (Arr [j], Arr [j + 1])
sukeista = tiesa
pabaiga jei
pabaigos
// jei elementai nebuvo sukeisti, tai reiškia, kad masyvas yra rūšiuojamas dabar, tada pertraukite kilpą.
jei (nepakeista) tada
pertrauka
pabaiga jei
pabaigos
galas

Burbulų rūšiavimo algoritmo laiko kompleksiškumas ir pagalbinė erdvė

Blogiausio burbulų rūšiavimo algoritmo laiko sudėtingumas yra O (n ^ 2). Jis įvyksta, kai masyvas yra mažėjimo tvarka ir norite jį rūšiuoti didėjimo tvarka arba atvirkščiai.

Geriausias burbulų rūšiavimo algoritmo laiko sudėtingumas yra O (n). Tai įvyksta, kai masyvas jau yra rūšiuojamas.

Susijęs: Kas yra „Big-O“ žymėjimas?

Burbulų rūšiavimo algoritmo vidutinis laiko sudėtingumas yra O (n ^ 2). Jis įvyksta, kai masyvo elementai yra susimaišę.

„Bubble Sort“ algoritmui reikalinga pagalbinė erdvė yra O (1).

C ++ Burbulų rūšiavimo algoritmo įgyvendinimas

Žemiau yra „Bubble Sort“ algoritmo „C ++“ įgyvendinimas:

// C ++ diegimas
// optimizuotas burbulų rūšiavimo algoritmas
# įtraukti 
naudojant vardų sritį std;
// Funkcija atlikti burbulų rūšiavimą
void bubbleSort (int arr [], int dydis) {
// Pakartokite, norėdami pasiekti kiekvieną masyvo elementą
už (int i = 0; i // Kintamasis norint patikrinti, ar įvyksta apsikeitimas
bool swapped = klaidinga;
// kilpa, norint palyginti du gretimus masyvo elementus
už (int j = 0; j // Palyginti du gretimus masyvo elementus
jei (arr [j]> arr [j + 1]) {
// Pakeiskite abu elementus, jei jie yra
// neteisinga tvarka
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
sukeista = tiesa;
}
}
// Jei elementai nebuvo sukeisti, tai reiškia, kad masyvas yra rūšiuojamas dabar,
// tada nutraukite kilpą.
jei (pakeista == klaidinga) {
pertrauka;
}
}
}
// Spausdina masyvo elementus
void printArray (int arr [], int dydis) {
už (int i = 0; i cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Masyvo ilgio radimas
int dydis = dydis (arr) / dydisof (arr [0]);
// Pateikto nesurūšiuoto masyvo spausdinimas
cout << "Nerūšiuotas masyvas:" << endl;
printArray (arr, dydis);
// Skambinimo funkcija bubbleSort ()
bubbleSort (arr, dydis);
// Rūšiuoto masyvo spausdinimas
cout << "Rūšiuotas masyvas didėjimo tvarka:" << endl;
printArray (arr, dydis);
grąžinti 0;
}

Išvestis:

Nerūšiuotas masyvas: 
16 12 15 13 19 
Surūšiuotas masyvas didėjimo tvarka:
12 13 15 16 19

„Python“ burbulų rūšiavimo algoritmo įgyvendinimas

Žemiau yra „Bubble Sort“ algoritmo „Python“ diegimas:

# Python diegimas
# optimizuotas burbulų rūšiavimo algoritmas
# Funkcija atlikti burbulų rūšiavimą
def burbulas Rūšiuoti (arr, dydis):
# Loop pasiekti kiekvieną sąrašo elementą
i diapazone (dydis-1):
# Kintamasis norint patikrinti, ar įvyksta apsikeitimas
sukeista = klaidinga
# kilpa, norint palyginti du gretimus sąrašo elementus
j diapazone (dydis-i-1):
# Palyginti du gretimus sąrašo elementus
jei arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = temp
sukeista = Tiesa
# Jei elementai nebuvo sukeisti, tai reiškia, kad sąrašas yra surūšiuotas dabar,
# tada nutraukite kilpą.
jei pakeista == Klaidinga:
pertrauka
# Spausdina sąrašo elementus
def printArray (arr):
elementui arr:
spausdinti (elementas, pabaiga = "")
spausdinti ("")
arr = [16, 12, 15, 13, 19]
# Sąrašo ilgio radimas
dydis = len (arr)
# Pateikto nerūšiuoto sąrašo spausdinimas
spausdinti ("Nerūšiuotas sąrašas:")
spausdinti masyvą (arr)
# Skambinimo funkcija bubbleSort ()
bubbleSort (arr, dydis)
# Rūšiuoto sąrašo spausdinimas
spausdinti ("Rūšiuotas sąrašas didėjimo tvarka:")
spausdinti masyvą (arr)

Išvestis:

Nerūšiuotas sąrašas:
16 12 15 13 19 
Surūšiuotas sąrašas didėjimo tvarka:
12 13 15 16 19

Susijęs: Kaip naudotis „Python“ kilpomis

C Burbulų rūšiavimo algoritmo įgyvendinimas

Žemiau yra „Bubble Sort“ algoritmo C įgyvendinimas:

// C įgyvendinimas
// optimizuotas burbulų rūšiavimo algoritmas
# įtraukti 
# įtraukti 
// Funkcija atlikti burbulų rūšiavimą
void bubbleSort (int arr [], int dydis) {
// Pakartokite, norėdami pasiekti kiekvieną masyvo elementą
už (int i = 0; i // Kintamasis norint patikrinti, ar įvyksta apsikeitimas
bool swapped = klaidinga;
// kilpa, norint palyginti du gretimus masyvo elementus
už (int j = 0; j // Palyginti du gretimus masyvo elementus
jei (arr [j]> arr [j + 1]) {
// Pakeiskite abu elementus, jei jie yra
// neteisinga tvarka
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
sukeista = tiesa;
}
}
// Jei elementai nebuvo sukeisti, tai reiškia, kad masyvas yra rūšiuojamas dabar,
// tada nutraukite kilpą.
jei (pakeista == klaidinga) {
pertrauka;
}
}
}
// Spausdina masyvo elementus
void printArray (int arr [], int dydis) {
už (int i = 0; i printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Masyvo ilgio radimas
int dydis = dydis (arr) / dydisof (arr [0]);
// Pateikto nesurūšiuoto masyvo spausdinimas
printf ("Nesurūšiuotas masyvas: \ ⁠n");
printArray (arr, dydis);
// Skambinimo funkcija bubbleSort ()
bubbleSort (arr, dydis);
// Rūšiuoto masyvo spausdinimas
printf ("Rūšiuotas masyvas didėjimo tvarka: \ ⁠n");
printArray (arr, dydis);
grąžinti 0;
}

Išvestis:

Nerūšiuotas masyvas: 
16 12 15 13 19 
Surūšiuotas masyvas didėjimo tvarka: 
12 13 15 16 19

„JavaScript“ pritaikymas burbulų rūšiavimo algoritmui

Žemiau yra „Bubble Sort“ algoritmo „JavaScript“ diegimas:

// „JavaScript“ diegimas
// optimizuotas burbulų rūšiavimo algoritmas
// Funkcija atlikti burbulų rūšiavimą
funkcija bubbleSort (arr, dydis) {
// Pakartokite, norėdami pasiekti kiekvieną masyvo elementą
už (tegul i = 0; i// Kintamasis norint patikrinti, ar įvyksta apsikeitimas
var sukeitė = klaidinga;
// kilpa, norint palyginti du gretimus masyvo elementus
už (tegul j = 0; j// Palyginti du gretimus masyvo elementus
jei (arr [j]> arr [j + 1]) {
// Pakeiskite abu elementus, jei jie yra
// neteisinga tvarka
tegul temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
sukeista = tiesa;
}
// Jei elementai nebuvo sukeisti, tai reiškia, kad masyvas yra rūšiuojamas dabar,
// tada nutraukite kilpą.
jei (pakeista == klaidinga) {
pertrauka;
}
}
}
}
// Spausdina masyvo elementus
funkcija printArray (arr, dydis) {
už (tegul i = 0; idocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Masyvo ilgio radimas
var dydis = arr.length;
// Pateikto nesurūšiuoto masyvo spausdinimas
document.write ("Nesurūšiuotas masyvas: 
");
printArray (arr, dydis);
// Skambinimo funkcija bubbleSort ()
bubbleSort (arr, dydis);
// Rūšiuoto masyvo spausdinimas
document.write ("Rūšiuotas masyvas didėjimo tvarka: 
");
printArray (arr, dydis);

Išvestis:

Nerūšiuotas masyvas:
16 12 15 13 19
Surūšiuotas masyvas didėjimo tvarka:
12 15 13 16 19

Dabar jūs suprantate burbulų rūšiavimo algoritmo veikimą

„Bubble Sort“ yra paprasčiausias rūšiavimo algoritmas ir daugiausia naudojamas norint suprasti rūšiavimo pagrindus. „Bubble Sort“ taip pat galima įdiegti rekursyviai, tačiau tai nesuteikia papildomų pranašumų.

Naudodami „Python“ galite lengvai įdiegti „Bubble Sort“ algoritmą. Jei nesate susipažinę su „Python“ ir norite pradėti savo kelionę, pradėti nuo „Hello World“ scenarijaus yra puikus pasirinkimas.

Kaip pradėti naudotis „Python“ naudojant „Hello World“ scenarijų

Python yra viena iš populiariausių programavimo kalbų, naudojamų šiandien. Vykdykite šią mokymo programą, kad pradėtumėte naudoti savo pirmąjį „Python“ scenarijų.

Skaitykite toliau

Apie autorių