>> [MUZYKI]
DOUG LLOYD: Dobrze, więc Sortowanie bąbelkowe jest algorytmem
można użyć do sortowania zestaw elementów.
Rzućmy okiem na, jak to działa.
>> Więc Podstawową ideą Sortowanie bąbelkowe jest to.
Zazwyczaj chcą przenieść wyżej wyceniane elementy ogólnie w prawo,
i obniżyć ogólnie cenionych elementów w lewo, jak to się spodziewać.
Chcemy niższe rzeczy być w początek, a wyższe rzeczy
się na końcu.
>> W jaki sposób to zrobić?
Cóż w kodzie pseudokod, moglibyśmy powiedzieć, niech
ustawić licznik wymiany na wartość niezerową.
Zobaczymy, dlaczego robimy to, że w drugim.
A potem powtórzyć następujące Proces dopóki licznik wymiany jest 0,
lub do czasu robimy żadnych swapów w ogóle.
>> Wyzerować licznik wymiany do 0 jeśli nie jest już 0.
Następnie spójrz na co parę sąsiednich elementów.
Jeśli te dwa elementy są nie w porządku, ich wymiany,
i dodać 1 do licznika wymiany.
Jeśli myślisz o to przed wizualizację,
zauważysz, że będzie to przenieść niższe wyceniane elementy w lewo
i wyżej cenione elementy do prawej, skutecznie robić to, co chcemy zrobić,
co jest przenieść te grupy elementów w ten sposób.
Powiedzmy, wizualizować, jak to może wyglądać przy użyciu naszą tablicę
który zastosowano do badania z tych algorytmów.
Znów mamy tutaj jakiś nieposortowanej tablicy, oznaczone wszystkie elementy
jest w kolorze czerwonym.
I mogę ustawić licznik wymiany na wartość niezerową.
I arbitralnie wybrała negatywne 1-- to nie jest 0.
Chcemy, aby powtórzyć ten proces do licznika wymiany to 0.
Dlatego też ustawić swap Licznik jakąś wartość niezerową,
ponieważ w przeciwnym wypadku Licznik wymiany będzie 0.
My nawet nie rozpocząć Proces algorytmu.
Więc jeszcze raz, kroki are-- wyzerować licznik wymiany
na 0, a następnie spójrz na każde sąsiadujące para, a jeśli są w porządku,
zamienić je i dodać 1 do licznika wymiany.
Warto więc rozpocząć ten proces.
Tak więc pierwszą rzeczą, jaką możemy zrobić, to możemy ustawić licznik wymiany na 0,
i wtedy zacząć szukać w każdej sąsiedniej pary.
>> Więc najpierw zacząć patrzeć na 5 i 2.
Widzimy, że są one z zamówienie i tak zamienić je.
I możemy dodać 1 do licznika wymiany.
Więc teraz nasze przeciw wymiany to 1, oraz 2 i 5 zostały włączone.
Teraz ponownie powtórzyć proces.
>> Patrzymy na następnej sąsiedniej pary, 5 i 1-- są też w porządku,
więc zamienić je i dodaj 1 do licznika wymiany.
Następnie patrzymy na 5 i 3.
Są w porządku, więc zamienić je i dodać 1 do licznika wymiany.
Następnie patrzymy na 5 i 6.
Są w porządku, więc w rzeczywistości nie trzeba zamieniać cokolwiek ten czas.
Następnie patrzymy na 6 i 4.
Są także w porządku, więc zamienić je i dodać 1 do licznika wymiany.
>> Teraz zauważył, co się stało.
Mamy przeniósł 6, aż do końca.
Więc wybór rodzaju, jeśli już widać, że film, co zrobiliśmy było
Skończyło się przesunięcie Najmniejsze elementy budynku
posortowanej tablicy zasadniczo od od lewej do prawej strony, najmniejszych do największych.
W przypadku sortowanie bąbelkowe, czy jesteśmy w następstwie tego konkretnego algorytmu,
my rzeczywiście będzie budowa posortowanej tablicy z prawej
do lewej, od największej do najmniejszej.
Mamy skutecznie przepuszcza 6, największa wartość, aż do końca.
>> I tak możemy zadeklarować że jest posortowana,
aw przyszłości iterations-- przechodzi tablicy again--
nie mamy do rozważenia 6 więcej.
Mamy tylko do rozważenia nieposortowanej elementy
kiedy patrzymy na sąsiednich par.
Więc mamy gotowy jeden przejść przez bubble rodzaju.
Więc teraz wracamy do pytania, powtarzać aż licznik wymiany jest 0.
Cóż licznik wymiany jest 4, więc jedziemy
utrzymać powtarzając ten proces.
>> Jedziemy, aby wyzerować licznik wymiany 0, i spojrzeć na każdą parą sąsiednich.
Więc zaczynamy 2 i 1-- są w porządku, więc możemy je zamienić
i dodać 1 do licznika wymiany.
2 i 3, są w porządku.
Nie musimy nic robić.
3 i 5 są w porządku.
Nie musimy robić coś.
>> 5 i 4, są z porządku, a więc
należy zamienić je i dodaj 1 do licznika wymiany.
A teraz mamy przeniósł 5, następna największa elementem,
na końcu części sortowane.
Więc teraz możemy nazwać część posortowane części.
>> Teraz jesteś patrząc na Ekran i chyba mogę powiedzieć,
jak mogę, że na tablicy jest posortowana teraz.
Ale nie możemy udowodnić, że jeszcze.
Nie mamy gwarancji że to jest klasyfikowane.
Ale to jest, gdy zamiana Licznik będzie wchodzić w grę.
>> Więc mamy zakończone przepustkę.
Licznik wymiany to 2.
Tak więc mamy zamiar powtórzyć znowu ten proces,
powtarzać aż licznik wymiany jest 0.
Wyzerować licznik wymiany 0.
Więc będziemy go zresetować.
>> Teraz spójrz na każdej sąsiedniej pary.
To jest w kolejności 1 i 2.
2 i 3 jest w porządku.
3 i 4 są w porządku.
Więc w tym momencie zauważyć, mamy zakończone patrząc na każdej sąsiedniej pary,
ale licznik wymiany jest wciąż 0.
>> Jeśli nie mamy, aby przełączyć wszelkie elementy, a potem
muszą być w stanie, poprzez zaletą tego procesu.
I tak sprawność rodzaju, że naukowcy mamy komputer miłość,
jest teraz możemy zadeklarować cała tablica musi
być sortowane, bo nie trzeba zamienić wszystkie elementy.
To całkiem miłe.
>> Więc co jest najgorszym przypadku Scenariusz z bańki rodzaju?
W najgorszym przypadku, gdy matryca jest w zupełnie odwrotnej kolejności,
i tak musimy bańka każdego dużych elementów wszystkich
sposób w całej tablicy.
I skutecznie również do bańka wszystkich małych elementów z powrotem
aż poprzez tablicy, też.
Tak więc każdy z elementów n musi poruszać we wszystkich pozostałych elementów N.
Więc to najgorszy scenariusz.
W najlepszym wypadku Scenariusz jeśli jest to
nieznacznie różnić się od wyboru rodzaju.
Tablica jest już klasyfikowane, gdy idziemy w.
Nie trzeba wprowadzać żadnych swap na pierwszym przejeździe.
Więc może musimy patrzeć w mniejszej ilości elementów, prawda?
Nie musimy to powtórzyć przetwarzać wiele razy.
>> Więc co to oznacza?
Więc co jest najgorszym przypadku dla bubble rodzaju, a co
najlepszy scenariusz dla bubble rodzaju?
Czy, że to?
W najgorszym przypadku trzeba iteracji we wszystkich elementach n n razy.
Tak więc w najgorszym przypadku jest n do kwadratu.
>> Jeśli tablica jest idealnie sortowane choć, tylko ty
patrzeć na siebie Once elementów.
A jeśli licznik wymiany jest nadal 0, można powiedzieć, ta tablica jest posortowana.
A więc w najlepszym przypadku jest lepsza niż wybór
sort-- to omega n.
>> Jestem Doug Lloyd.
To CS50.