Johdatus kuplalajittelualgoritmiin

Lajittelu on yksi perustoiminnoista, joita voit käyttää tiedoissa. Voit lajitella elementtejä eri ohjelmointikielillä käyttämällä erilaisia ​​lajittelualgoritmeja, kuten pikalajittelu, kuplalajittelu, yhdistämislajittelu, lisäyslajittelu jne. Bubble Sort on yksinkertaisin algoritmi kaikkien näiden joukossa.

Tässä artikkelissa opit Bubble Sort -algoritmin, Bubble Sort -pseudokoodin, toiminnasta algoritmi, sen ajan ja tilan monimutkaisuus ja sen toteutus useilla ohjelmointikielillä, kuten C ++, Python, C ja JavaScript.

Kuinka Bubble Sort -algoritmi toimii?

Bubble Sort on yksinkertaisin lajittelualgoritmi, joka selaa luetteloa toistuvasti, vertaa vierekkäisiä elementtejä ja vaihtaa ne väärässä järjestyksessä. Tämä käsite voidaan selittää tehokkaammin esimerkin avulla. Harkitse lajittelematon taulukko, jossa on seuraavat elementit: {16, 12, 15, 13, 19}.

Esimerkki:

Tässä verrataan vierekkäisiä elementtejä, ja jos ne eivät ole nousevassa järjestyksessä, ne vaihdetaan.

Bubble Sort -algoritmin pseudokoodi

Pseudokoodissa, Bubble Sort -algoritmi voidaan ilmaista seuraavasti:

bubbleSort (Arr [], koko)
// -silmukka kutakin taulukkoelementtiä varten
kun i = 0 kokoon 1, tee:
// -silmukka vertailla taulukkoelementtejä
kun j = 0 kokoon-i-1, tee:
// vertaa vierekkäisiä elementtejä
jos Arr [j]> Arr [j + 1] sitten
// vaihda ne
vaihda (Arr [j], Arr [j + 1])
loppu Jos
loppu
loppu
loppuun

Yllä oleva algoritmi käsittelee kaikki vertailut, vaikka taulukko on jo lajiteltu. Sitä voidaan optimoida edelleen pysäyttämällä algoritmi, jos sisäinen silmukka ei aiheuttanut vaihtamista. Tämä vähentää algoritmin suoritusaikaa.

Täten optimoidun Bubble Sort -algoritmin pseudokoodi voidaan ilmaista seuraavasti:

bubbleSort (Arr [], koko)
// -silmukka kutakin taulukkoelementtiä varten
kun i = 0 kokoon 1, tee:
// tarkista, tapahtuuko vaihto
vaihdettu = väärä
// -silmukka vertailla taulukkoelementtejä
kun j = 0 kokoon-i-1, tee:
// vertaa vierekkäisiä elementtejä
jos Arr [j]> Arr [j + 1] sitten
// vaihda ne
vaihda (Arr [j], Arr [j + 1])
vaihdettu = tosi
loppu Jos
loppu
// jos yhtään elementtiä ei vaihdettu, se tarkoittaa, että taulukko on lajiteltu nyt, katkaise sitten silmukka.
jos (ei vaihdettu) sitten
tauko
loppu Jos
loppu
loppuun

Bubble Sort -algoritmin aikakompleksisuus ja aputila

Bubble Sort -algoritmin pahin tapa-aika on O (n ^ 2). Se tapahtuu, kun taulukko on laskevassa järjestyksessä ja haluat lajitella sen nousevassa järjestyksessä tai päinvastoin.

Bubble Sort Algorithmin paras aikakompleksi on O (n). Se tapahtuu, kun taulukko on jo lajiteltu.

Liittyvät: Mikä on Big-O-merkintä?

Bubble Sort Algorithmin keskimääräinen tapausaika-monimutkaisuus on O (n ^ 2). Se tapahtuu, kun matriisin elementit ovat sekaisin.

Bubble Sort -algoritmin tarvitsema aputila on O (1).

C ++ Bubble Sort -algoritmin toteutus

Alla on Bubble Sort -algoritmin C ++ -toteutus:

// C ++ -toteutus
// optimoitu Bubble Sort -algoritmi
#sisältää 
käyttämällä nimitilaa vakio;
// Toiminto kuplalajittelun suorittamiseksi
void bubbleSort (int arr [], int-koko) {
// Silmukka päästäksesi matriisin jokaiseen elementtiin
for (int i = 0; i // Muuttuja, jolla tarkistetaan, tapahtuuko vaihto
bool vaihdettu = false;
// -silmukka vertailla taulukon kahta vierekkäistä elementtiä
for (int j = 0; j // Kahden vierekkäisen taulukkoelementin vertailu
jos (arr [j]> arr [j + 1]) {
// Vaihda molemmat elementit, jos ne ovat
// ei oikeassa järjestyksessä
int lämpötila = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = lämpötila;
vaihdettu = tosi;
}
}
// Jos yhtään elementtiä ei vaihdettu, taulukko on nyt lajiteltu,
// sitten katkaise silmukka.
jos (vaihdettu == väärä) {
tauko;
}
}
}
// Tulostaa taulukon elementit
void printArray (int arr [], int-koko) {
for (int i = 0; i cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Taulukon pituuden etsiminen
int koko = koko (arr) / kokoof (arr [0]);
// Annetun lajittelemattoman taulukon tulostaminen
cout << "Lajittelematon taulukko:" << endl;
printArray (arr, koko);
// Calling bubbleSort () -toiminto
bubbleSort (arr, koko);
// Lajiteltu taulukko
cout << "Lajiteltu taulukko nousevassa järjestyksessä:" << endl;
printArray (arr, koko);
paluu 0;
}

Tuotos:

Lajittelematon taulukko: 
16 12 15 13 19 
Lajiteltu taulukko nousevassa järjestyksessä:
12 13 15 16 19

Bubble Sort -algoritmin Python-toteutus

Alla on Bubble Sort -algoritmin Python-toteutus:

# Python-toteutus
# optimoitu Bubble Sort -algoritmi
# Toiminto kuplalajittelun suorittamiseen
def bubbleSort (arr, koko):
# Loop käyttää luettelon jokaista osaa
i: lle alueella (koko-1):
# Muuttuja tarkistaa, tapahtuuko vaihto
vaihdettu = väärä
# silmukka vertailla luettelon kahta vierekkäistä elementtiä
j: lle alueella (koko-i-1):
# Vertaamalla kahta vierekkäistä luetteloelementtiä
jos arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = lämpötila
vaihdettu = tosi
# Jos elementtejä ei vaihdettu, luettelo on nyt lajiteltu,
# sitten katkaise silmukka.
vaihdettu == Väärä:
tauko
# Tulostaa luettelon elementit
def print Array (arr):
elementille arr:
tulosta (elementti, loppu = "")
Tulosta("")
arr = [16, 12, 15, 13, 19]
# Luettelon pituuden etsiminen
koko = len (arr)
# Annetun lajittelemattoman luettelon tulostaminen
tulosta ("Lajittelematon luettelo:")
printArray (arr)
# Soittaminen bubbleSort () -toiminto
bubbleSort (arr, koko)
# Lajitellun luettelon tulostaminen
tulosta ("Lajiteltu luettelo nousevassa järjestyksessä:")
printArray (arr)

Tuotos:

Lajittelematon luettelo:
16 12 15 13 19 
Lajiteltu luettelo nousevassa järjestyksessä:
12 13 15 16 19

Liittyvät: Kuinka käyttää silmukoita Pythonissa

C Bubble Sort -algoritmin toteutus

Alla on Bubble Sort -algoritmin C-toteutus:

// C-toteutus
// optimoitu Bubble Sort -algoritmi
#sisältää 
#sisältää 
// Toiminto kuplalajittelun suorittamiseksi
void bubbleSort (int arr [], int-koko) {
// Silmukka päästäksesi matriisin jokaiseen elementtiin
for (int i = 0; i // Muuttuja, jolla tarkistetaan, tapahtuuko vaihto
bool vaihdettu = false;
// -silmukka vertailla taulukon kahta vierekkäistä elementtiä
for (int j = 0; j // Kahden vierekkäisen taulukkoelementin vertailu
jos (arr [j]> arr [j + 1]) {
// Vaihda molemmat elementit, jos ne ovat
// ei oikeassa järjestyksessä
int lämpötila = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = lämpötila;
vaihdettu = tosi;
}
}
// Jos yhtään elementtiä ei vaihdettu, taulukko on nyt lajiteltu,
// sitten katkaise silmukka.
jos (vaihdettu == väärä) {
tauko;
}
}
}
// Tulostaa taulukon elementit
void printArray (int arr [], int-koko) {
for (int i = 0; i printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Taulukon pituuden etsiminen
int koko = koko (arr) / kokoof (arr [0]);
// Annetun lajittelemattoman taulukon tulostaminen
printf ("Lajittelematon taulukko: \ ⁠n");
printArray (arr, koko);
// Calling bubbleSort () -toiminto
bubbleSort (arr, koko);
// Lajiteltu taulukko
printf ("Lajiteltu taulukko nousevassa järjestyksessä: \ ⁠n");
printArray (arr, koko);
paluu 0;
}

Tuotos:

Lajittelematon taulukko: 
16 12 15 13 19 
Lajiteltu taulukko nousevassa järjestyksessä: 
12 13 15 16 19

Bubble Sort -algoritmin JavaScript-toteutus

Alla on Bubble Sort -algoritmin JavaScript-toteutus:

// JavaScriptin toteutus
// optimoitu Bubble Sort -algoritmi
// Toiminto kuplalajittelun suorittamiseksi
funktio bubbleSort (arr, koko) {
// Silmukka päästäksesi matriisin jokaiseen elementtiin
for (olkoon i = 0; i// Muuttuja, jolla tarkistetaan, tapahtuuko vaihto
var vaihdettu = väärä;
// -silmukka vertailla taulukon kahta vierekkäistä elementtiä
for (olkoon j = 0; j// Kahden vierekkäisen taulukkoelementin vertailu
jos (arr [j]> arr [j + 1]) {
// Vaihda molemmat elementit, jos ne ovat
// ei oikeassa järjestyksessä
anna temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = lämpötila;
vaihdettu = tosi;
}
// Jos yhtään elementtiä ei vaihdettu, taulukko on nyt lajiteltu,
// sitten katkaise silmukka.
jos (vaihdettu == väärä) {
tauko;
}
}
}
}
// Tulostaa taulukon elementit
funktio printArray (arr, koko) {
for (olkoon i = 0; idocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Taulukon pituuden etsiminen
var koko = arr.pituus;
// Annetun lajittelemattoman taulukon tulostaminen
document.write ("Lajittelematon taulukko: 
");
printArray (arr, koko);
// Calling bubbleSort () -toiminto
bubbleSort (arr, koko);
// Lajiteltu taulukko
document.write ("Lajiteltu taulukko nousevassa järjestyksessä: 
");
printArray (arr, koko);

Tuotos:

Lajittelematon taulukko:
16 12 15 13 19
Lajiteltu taulukko nousevassa järjestyksessä:
12 15 13 16 19

Nyt ymmärrät Bubble Sort -algoritmin toiminnan

Bubble Sort on yksinkertaisin lajittelualgoritmi, jota käytetään pääasiassa lajittelun perusteiden ymmärtämiseen. Bubble Sort voidaan toteuttaa myös rekursiivisesti, mutta se ei tarjoa lisäetuja.

Pythonin avulla voit toteuttaa Bubble Sort -algoritmin helposti. Jos et tunne Pythonia ja haluat aloittaa matkan, "Hello World" -komentosarjan käyttäminen on loistava valinta.

Pythonin käytön aloittaminen "Hello World" -komentosarjan avulla

Python on yksi suosituimmista ohjelmointikielistä, jota käytetään nykyään. Seuraa tätä opetusohjelmaa aloittaaksesi ensimmäisen Python-komentosarjosi.

Lue seuraava

Kirjailijasta