[Powered by Google Translate] [BUBBLE SORT]
[JACKSON STEINKAMP Sveučilištu Harvard]
[OVO JE CS50. CS50TV]
Bubble Sortiraj je primjer sortiranje algoritma -
to jest, postupak za sortiranje skup elemenata u
uzlazno ili silazno.
Na primjer, ako ste htjeli sortirati niz koji se sastoji od brojeva
[3, 5, 2, 9], ispravna provedba Bubble Poredaj bi povratak
razvrstani niz [2, 3, 5, 9] uzlaznim redoslijedom.
Sada, ja ću objasniti u pseudocode kako algoritam radi.
>> Recimo da smo sortiranje popis pet brojeva - 3, 2, 9, 6, i 5.
Algoritam započinje gledanjem na prva dva elementa, 3 i 2,
i provjere da li su iz reda u odnosu na druge.
Oni su - 3 je veći od 2.
Da bi se u uzlaznom redoslijedu, oni bi trebali biti obrnuto.
Dakle, mi ih zamijeniti.
Sada popis izgleda ovako: [2, 3, 9, 6, 5].
>> Dalje, mi gledamo na drugi i treći elementima, tri i devet.
Oni su u ispravnom redoslijedu u odnosu na drugoga.
To je, tri manje od 9 pa algoritam ne mijenjati ih.
Dalje, mi gledamo na devet i šest. Oni su iz reda.
>> Dakle, moramo ih zamijeniti, jer devet je veća od šest.
Na kraju, mi gledamo na posljednja dva cijeli brojevi, 9 i 5.
Oni su od reda, tako da oni moraju biti zamijeniti.
Nakon prvog kompletni prolaze kroz popisu
to izgleda ovako: [2, 3, 6, 5, 9].
Nije loše. To je gotovo riješeno.
Ali moramo pokrenuti kroz popis opet da ga u potpunosti riješeno.
Dva je manje od tri, tako da mi ne mijenjati ih.
>> Tri je manje od 6, pa mi ne mijenjati ih.
Šest je veći od 5. Mi zamijenili.
Šest je manji od 9. Mi ne zamijene.
Nakon drugog prolaza kroz, to izgleda ovako: [2, 3, 5, 6, 9]. Savršeno.
Sada, neka je napisati u pseudocode.
Uglavnom, za svaki element u listi, trebamo gledati na to
i element izravno svojoj desnoj strani.
Ako su iz reda u odnosu na svaki drugi - to jest, ako se element na lijevoj
je veća od one na desnoj strani - treba zamijeniti dva elementa.
>> Mi to učiniti za svaki element liste, a mi smo napravili jedan proći kroz.
Sada samo moramo raditi na prolazni dovoljno puta da se osigura popis
je u potpunosti, pravilno razvrstani.
No, koliko puta moramo proći kroz popisu
jamčiti da ćemo učiniti?
Pa, najgori scenarij je da imamo potpuno unatrag popis.
Tada je potrebno nekoliko pass-through jednak broju
elemenata n-1.
Ako to ne smisla intuitivno, mislim jednostavnog slučaju - popis [2, 1].
>> To se događa da se jedan prolazni sortirati ispravno.
[3, 2, 1] - Najgori slučaj je da se s tri elementa razvrstani unatrag,
to će potrajati dva ponavljanja za sortiranje.
Nakon jednog iteraciji, to je [2, 1, 3].
Drugi rađa sortirani array [1, 2, 3].
Pa znaš da nikada ne morate proći kroz niz, u cjelini,
više od n-1 puta, gdje je n broj elemenata u polju.
To se zove Bubble Sortiraj jer najveći elementi imaju tendenciju da "balon-up '
desno prilično brzo.
U stvari, ovaj algoritam ima vrlo zanimljivu ponašanje.
>> Nakon m iteracija kroz cijeli niz,
krajnjem desnom m elementi su zajamčena
biti razvrstani u njihovom ispravnom mjestu.
Ako želite vidjeti ovo za sebe,
možemo probati na potpuno unatrag popisu [9, 6, 5, 3, 2].
Nakon jednom prolazu kroz cijeli popis,
[Zvuk pisanja]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
desni elemenat 9 je na svom mjestu.
Nakon što je drugi prolazni, 6 će imati 'bubbled-up "na
drugi desni mjesto.
Ova dva elementa na desno - 6 i 9 - bit će u njihovim pravilnim mjestima
nakon prva dva pass-through.
>> Dakle, kako možemo koristiti ovu optimizirati algoritam?
Pa, nakon jedne iteracije kroz niz
mi zapravo ne trebaju provjeriti desni elementa
jer znamo da je riješeno.
Nakon dva iteracija, znamo jesu li desni dva elementa su na mjestu.
Dakle, u cjelini, nakon k iteracija kroz cijeli niz,
Provjera posljednje k elemenata je suvišan, jer znamo
oni su na pravom mjestu već.
>> Dakle, ako ste sortiranje niz od n elemenata,
na prvoj iteraciji - you'll morati sortirati sve elemente - prvi n-0.
Na drugoj iteraciji, morat ćete pogledati sve elemente, ali zadnji -
prvi n-1.
Drugi optimizacija može biti da provjerite je li popis već razvrstani
nakon svake iteracije.
Ako je već razvrstani, mi ne trebamo da bi bilo više iteracije
kroz popis.
Kako možemo to učiniti?
Pa, ako mi ne bi bilo zamjene na prolazni popisa,
jasno je da je popis već razvrstani jer nismo zamijeniti ništa.
Dakle, mi definitivno nemamo za sortiranje ponovno.
>> Možda bi mogao inicijalizirati varijablu zastave pod nazivom 'Ne razvrstani' na
false i promijenite ga vrijedi ako imate za zamjenu nikakve elemente na
jedan iteracija kroz niz.
Ili slično, napraviti brojač brojati koliko swaps napraviti
na svakom iteracija.
Na kraju je iteracija, ako nije zamijeniti bilo kojeg od elemenata,
znate popis već razvrstani i gotovi ste.
Bubble Sortiranje, kao i druge sortiranja algoritama, može biti
praćka za rad svih elemenata koji imaju naručivanja metodu.
>> To je, s obzirom na dva elementa imate način za reći, ako prvi
je veći od, jednak ili manji od drugog.
Na primjer, možete sortirati slova abecede rekavši
da <b, b <c, itd.
Ili ste mogli sortirati dana u tjednu u kojem je nedjelja manje nego ponedjeljak
što je manje od utorak.
>> Bubble Sortiraj nipošto nije vrlo učinkovit ili brzo sortiranje algoritam.
Njegova najgorem slučaju enja je Big O n ²
jer morate napraviti n iteracija kroz popis
provjeru svih n elemente svaki prolazni, nxn = n ².
Ovaj put pokrenuti znači da kao broj elemenata ste sortiranje povećava,
pokrenuti vrijeme povećava kvadratnom.
>> Ali ako učinkovitost nije glavna briga programu
ili ako ste samo sortiranje mali broj elemenata,
možda će vam Bubble Sortiraj koristan jer
to je jedan od najjednostavnijih sortiranje algoritama razumjeti
i kodirati.
To je također odličan način da dobijete iskustvo s prevođenjem teorijsko
algoritam u stvarnom funkcioniranju koda.
Pa, to je Bubble Poredaj za vas. Hvala za gledanje.
CS50.TV