[Powered by Google Translate] [BUBBLE SORT] [JACKSON STEINKAMP Univerzi Harvard] [To je CS50. CS50TV] Bubble Sortiraj je primer algoritma za razvrščanje - da je postopek za razvrščanje niz elementov v naraščajočem ali padajočem vrstnem redu. Na primer, če si hotel, da razvrstite niz, sestavljen iz številk [3, 5, 2, 9], bi pravilno izvajanje Razvrsti Bubble vrne razporejene array [2, 3, 5, 9], v naraščajočem vrstnem redu. Zdaj bom razložiti, psevdokod, kako algoritem deluje. 

Recimo, da smo sortiranje seznam celih 5 - 3, 2, 9, 6, 5. Algoritem začne z opazovanjem prvih dveh elementov, 3 in 2, in preverjanja, če si v okvari relativno druga na drugo. So - 3 je večja od 2. Če želite biti v naraščajočem vrstnem redu, bi morali biti ravno obratno. Torej, jih zamenjajte. Zdaj je seznam izgleda takole: [2, 3, 9, 6, 5]. 

Nato smo si na drugi in tretji element, 3 in 9. Oni so v pravilnem vrstnem redu glede na drug drugega. To pomeni, da je manj kot 3 9, tako da algoritem ne swap njih. Nato si bomo ogledali 9 in 6. Oni so v okvari. 

Torej, jih moramo zamenjati, ker je 9 več kot 6 let. Na koncu pogledamo zadnjih dveh števil, 9 in 5. Oni so v drugačnem vrstnem redu, tako da jih je treba zamenjati. Po prvem prehodu skozi celoten seznam, izgleda takole: [2, 3, 6, 5, 9]. Ni slabo. Skoraj je urejeno. Vendar moramo teči po seznamu še enkrat, da se popolnoma urejeno. Dva manjša od 3, zato jih ne bomo zamenjali. 

Tri manj kot 6, zato jih ne bomo zamenjali. Šest je večja od 5 mm. Smo zamenjali. Šest manj kot 9. Ne zamenjati. Po drugem prehodu skozi, izgleda takole: [2, 3, 5, 6, 9]. Popolno. Zdaj pa napišite ga v Psevdokoda. V bistvu, za vsak element na seznamu, moramo pogledati in element neposredno na svoje pravice. Če so v drugačnem vrstnem redu glede na drug drugega - to je, če je element na levi strani večji od tistega na desni - bi morali zamenjati oba elementa. 

To počnemo za vsak element seznama, in smo naredili eno dovolilnico skozi. Zdaj moramo le še narediti pri prehodu skozi dovolj časa, da se zagotovi seznam se v celoti pravilno razvrščeni. Ampak kolikokrat moramo skozi seznamu zagotoviti, da bomo končali? No, najslabši scenarij, če imamo popolnoma nazaj seznam. Potem pa je potrebno veliko prehodu za kanale enako številu elementov n-1. Če to ni smiselno, intuitivno, pomislite na preprostem primeru - seznam [2, 1]. 

To bo trajalo 1 pass-through za pravilno razvrstiti. [3, 2, 1] - V najslabšem primeru je, da s 3 elementi, razvrščeni nazaj, to bo trajalo 2 do ponovitve takega. Po eni iteraciji, je [2, 1, 3]. Drugi dobimo razporejene array [1, 2, 3]. Torej veste, da vam nikoli ne bo šel skozi niz, na splošno, več kot n-1-krat, pri čemer je n število elementov v matriki. To se imenuje Bubble Razvrsti ker je največji elementi ponavadi "bubble-up" na desni precej hitro. V bistvu je to algoritem ima zelo zanimivo obnašanje. 

Po m ponovitev prek celotnega niza, skrajnem desnem m elementi so zagotovljena da se združimo v svojem pravem mestu. Če želite prepričati o tem, lahko poskusite na povsem zavoljo seznama [9, 6, 5, 3, 2]. Po enem prehodu skozi celoten seznam, [Zvok pisno] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] na skrajni desni element 9 je na ustreznem mestu. Po drugi pass-through bo 6 imajo "mehurčki-up" za 2. skrajno desno mesto. Dva elementa na desni - 6 in 9 - bo v svojih pravih mestih po prvih dveh pass-kanale. 

Torej, kako lahko to uporabimo za optimizacijo algoritma? No, po eni iteraciji skozi niz pravzaprav ne potrebujejo, da preverite desna element saj vemo, da je razvrščena. Po dveh ponovitvah, smo prepričani, skrajno desno dva elementa sta na mestu. Torej, na splošno, potem kv iteracij prek celotnega niza, preverjanje zadnjih K elementov je odveč, saj vemo, oni so na pravem mestu že. 

Torej, če ste sortiranje niz elementov n, na prvi ponovitvi - boš moral rešiti vse elemente - prvi n-0. Po drugi ponovitvi, boste morali gledati na vse elemente razen zadnjega - 1. n-1. Druga optimizacijo lahko preverite, ali je seznam že razporejene po vsaki ponovitvi. Če je že urejen, ne rabimo narediti nič več ponovitev po seznamu. Kako lahko to storimo? No, če ne bo nobenih zamenjav na pass-through seznama, je jasno, da je bil seznam že razporejene, ker nismo zamenjali ničesar. Zato smo zagotovo ne bi bilo treba ponovno razvrstiti. 

Morda bi lahko inicializacija zastave spremenljivko, imenovano "ni urejen" v neresnično in jo spremenite res, če imate, da bi zamenjali vse elemente ena ponovitev z matriko. Ali prav, da števec prešteti, koliko zamenjav naredite na katerem koli ponovitev. Na koncu je ponovitev, če ne bi zamenjal katerega koli od elementov, Veš seznam že razporejene in ste končali. Bubble Sortiraj, tako kot drugi algoritmi razvrščanja, je lahko tweaked za delo vseh elementov, ki imajo naročanje metodo. 

To je, glede na dva elementa, morate način, kako povedati, če prva , večji je enaka ali manjša od drugega. Na primer, lahko razvrstimo črke abecede z besedami da <b, b <c, itd Ali pa bi lahko razvrščate dni v tednu nedelja, kjer je manj kot ponedeljek kar je manj kot v torek. 

Bubble Razvrsti nikakor ni zelo učinkovito in hitro sortiranje algoritem. Njegov najslabši teka je Big O n ² ker moraš narediti n ponovitev po seznamu preverjanje vseh elementov, vsak n pass-through, nxn = n ². To pomeni, da čas teče, saj je število elementov, da ste sortiranje povečuje, čas delovanja povečuje kvadratom. 

Ampak, če učinkovitost ni glavna skrb vašega programa ali če ste le sortiranje majhno število elementov, boste morda našli Bubble Razvrsti koristno, saj to je eden od najpreprostejših algoritmov za razumevanje in za kodiranje. To je tudi odličen način, da izkušnje s prevajanjem teoretično Algoritem v dejansko oznako delovanja. No, to je Bubble Sortiraj za vas. Hvala za ogled. CS50.TV