[Powered by Google Translate] [SORT BUBBLE]
[JACKSON Steinkamp Harvard University]
[Jest to CS50. CS50TV]
Sortuj Bubble jest przykładem algorytmu sortowania -
to jest procedura sortowania zestawu elementów w
rosnąco lub malejąco.
Na przykład, jeśli chcesz posortować tablicę składającą się z liczb
[3, 5, 2, 9], prawidłowe wdrażanie Sortuj Bubble wróci
posortowana tablica [2, 3, 5, 9] w porządku rosnącym.
Teraz mam zamiar wyjaśnić w Pseudokod jak algorytm działa.
>> Powiedzmy, że mamy do sortowania listy 5 liczb - 3, 2, 9, 6, i 5.
Algorytm rozpoczyna od na dwóch pierwszych elementów, 3 i 2,
i sprawdza, czy są one w porządku w stosunku do siebie.
Są - 3 jest większy niż 2,.
Żeby być w porządku rosnącym, powinny być odwrotnie.
Tak więc zamienić je.
Teraz lista wygląda następująco: [2, 3, 9, 6, 5].
>> Następnie patrzymy na drugim i trzecim elementów, 3 i 9.
Są w odpowiedniej kolejności względem siebie.
Oznacza to, że jest mniejsza niż 3 9 tak algorytm nie zamiany.
Następnie patrzymy na 9 i 6. Są w porządku.
>> Tak więc, musimy zamienić je, ponieważ 9 jest większa niż 6.
Wreszcie, patrzymy na ostatnich dwóch liczb, 9 i 5.
Oni są w porządku, więc muszą zostać zamienione.
Po pierwszym przebiegu przez pełnej listy
wygląda to tak: [2, 3, 6, 5, 9].
Nie jest źle. To prawie posortowane.
Ale musimy uruchomić listę ponownie, aby ją całkowicie posortowane.
Dwa to mniej niż 3, więc nie zamienić je.
>> Trzy jest mniejsza niż 6, więc nie zamiany.
Sześć jest większa niż 5 mm. Mamy zamienione.
Sześć jest mniejsza od 9. Nie zamieniać.
Po drugim przejściu przez, wygląda to tak: [2, 3, 5, 6, 9]. Perfect.
A teraz piszę to w Pseudokod.
Zasadniczo, dla każdego elementu na liście, musimy na to patrzeć
a elementem bezpośrednio po prawej stronie.
Jeśli są one w porządku w odniesieniu do siebie - to jest, gdy element na lewo
jest większa niż na prawo - należy zamienić dwa elementy.
>> Robimy to dla każdego elementu na liście, a zrobiliśmy jeden przejść.
Teraz musimy zrobić przełożenia tyle razy, aby zapewnić listę
jest w pełni, prawidłowo posortowane.
Ale ile razy mamy przejść przez liście
Gwarantujemy, że skończyliśmy?
Cóż, najgorszy scenariusz jest, jeśli mamy całkowicie wsteczną listę.
Następnie bierze szereg przejazdu throughs równą liczbie
elementów n-1.
Jeśli to nie ma sensu, intuicyjnie, myślę o prostym przypadku - list [2, 1].
>> To zajmie jeden pass-through do sortowania poprawnie.
[3, 2, 1] - w najgorszym przypadku jest to, że z 3 elementów posortowane tyłu
to zajmie 2 iteracji do sortowania.
Po jednej iteracji, to [2, 1, 3].
Drugi szereg plony posortowane [1, 2, 3].
Więc wiesz, że nigdy nie musiał przejść przez tablicę, w ogóle,
więcej niż 1 razy N-, w którym n jest liczbą elementów w tablicy.
To się nazywa Sortuj Bubble ponieważ największe elementy mają tendencję do "bubble-up '
w prawo dość szybko.
W rzeczywistości, to algorytm jest bardzo interesujące zachowanie.
>> Po m iteracjach dzięki całej tablicy,
skrajnej prawej elementy m są gwarantowane
być posortowane w ich właściwym miejscu.
Jeśli chcesz zobaczyć na własne oczy,
możemy spróbować go na zupełnie wstecznej liście [9, 6, 5, 3, 2].
Po jednym przejściu przez całą listę,
[Dźwięk pisania]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
prawej stronie elementu 9 jest na swoim miejscu.
Po drugim pass-through, 6 będzie miał "przepuszcza się" do
sekund prawej stronie miejsce.
Te dwa elementy na prawo - 6 i 9 - będzie w ich właściwych miejscach
po pierwszych dwóch obwodnic-through.
>> Tak, jak możemy to wykorzystać do optymalizacji algorytmu?
Cóż, po jednej iteracji przez tablicę
nie faktycznie trzeba sprawdzić element, po prawej stronie,
ponieważ wiemy, że jest posortowane.
Po dwóch iteracji, wiemy na pewno, po prawej stronie, dwa elementy są na swoim miejscu.
Tak więc, ogólnie, po iteracji k do pełnej tablicy
Sprawdzanie ostatnio k elementów jest zbędna, ponieważ wiemy
są one w odpowiednim miejscu już.
>> Więc jeśli jesteś sortowania tablicy n elementów,
w pierwszej iteracji - you'll sortowania mają wszystkie elementy - pierwszy N-0.
Na drugiej iteracji, trzeba patrzeć na wszystkie elementy, ale ostatni -
pierwszy n-1.
Kolejna optymalizacja może być sprawdzenie, czy lista jest już posortowana
po każdej iteracji.
Jeśli jest już posortowane, nie musimy tworzyć kolejnych iteracji
listę.
W jaki sposób możemy to zrobić?
Cóż, jeśli nie podejmiemy żadnych swapów na przełożenia na liście,
to jasne, że lista została już posortowane, bo nie wymieniać wszystkiego.
Więc na pewno nie trzeba sortować ponownie.
>> Być może można zainicjować zmiennej flag nazwie 'nie posortowane "na
false i zmień go na prawdziwe, jeśli masz do wymiany elementów na
jedno powtórzenie przez tablicę.
Lub podobnie, zrobić licznik na zliczyć swapy zrobić
na każdej iteracji.
Na koniec iteracji, jeżeli nie zmieniać pozycję elementów,
wiesz, lista jest już posortowane i gotowe.
Sortuj Bubble, podobnie jak inne algorytmy sortowania, mogą być
manipulowane do pracy dla wszystkich elementów, które mają metodę zamawiania.
>> Oznacza to, że biorąc pod uwagę dwa elementy, które mają sposób, aby powiedzieć, czy pierwsza
jest większa, równa lub mniejsza od drugiej.
Na przykład, można posortować litery alfabetu, mówiąc
a <b, b <c, itp.
Albo można sortować dni tygodnia, gdzie niedziela jest mniej niż w poniedziałek
co jest mniej niż we wtorek.
>> Sortuj Bubble nie jest wcale bardzo skuteczny lub szybki algorytm sortowania.
Jego najgorszy czas pracy jest Big O n ²
bo masz do iteracji n poprzez listę
sprawdzenie wszystkich n elementów każdego pass-through, NxN = n ².
To oznacza, że ​​czas pracy, jak liczba elementów ty sortowania wzrost,
czas pracy zwiększa kwadratu.
>> Ale jeśli wydajność nie jest głównym problemem programu jest
lub jeśli jesteś tylko sortowania niewielkiej liczby elementów,
może się okazać użyteczne, ponieważ Bubble Sort
jest to jeden z najprostszych algorytmów sortowania, aby zrozumieć
i kod.
Jest to również świetny sposób, aby doświadczenie z tłumaczeniem teoretycznym
Algorytm do rzeczywistego kodu funkcjonowania.
Dobrze, że to sortowanie bąbelkowe dla Ciebie. Dzięki za oglądanie.
CS50.TV