>> MARK Grozen-Smith: Cześć, jestem Mark Grozen-Smith, i jest Quicksort.
Podobnie jak wstawiania rodzaju i bańki sortowania, Quicksort jest algorytm
Sortowanie listy lub tablicę rzeczy.
Dla uproszczenia załóżmy, że ci, rzeczy są tylko liczby całkowite, ale
wiem, że Quicksort pracuje dla więcej niż tylko liczby.
Szybki start jest nieco bardziej skomplikowana, niż wstawiania lub bańki, ale to
znacznie bardziej skuteczna w większości przypadków.
Chwileczkę.
Czy on powiedział "najbardziej przypadków, "nie" wszystko "?
Co ciekawe, nie.
Nie we wszystkich przypadkach jest taka sama.
Nie martw się o tym szczegółowo, jeśli ci Nie widziałem jeszcze duży notacji O, ale
Quicksort jest O (n do kwadratu) algorytm w najgorszym wypadku, jak
wstawiania lub sortowanie bąbelkowe.
Jednakże, zwykle występuje znacznie więcej jak stary m algorytmu analogowego.
Dlaczego?
Wrócimy do tego później.
Ale teraz, po prostu dowiedzieć się, jak Quicksort działa.
>> Warto więc przejść przez Quicksorting to tablica liczb całkowitych z najmniejszą
do największych.
Tutaj mamy liczby całkowite 6, 5, 1, 3, 8, 4, 7, 9 i 2.
Po pierwsze, możemy odebrać element końcowy Ta tablica - w tym przypadku, dwa -
i zadzwonić, że "oś." Następnie, zacząć patrzeć na dwie rzeczy -
jeden, najniższy wskaźnik, który będę odnosić jako pobytu na prawej
ściana, i, dwa, od lewej elementem, który ja nazywam "prąd
elementem. "Co mamy zamiar zrobić, to wyglądają wszystkie inne elementy, inne
od osi obrotu, i umieścić wszystkie elementy mniejsze niż trzpienia do
na lewo od ściany i wszystkich tych, większy od przegubu do
prawej ściany.
Wtedy wreszcie będziemy upuszczać pivot prawo na tej ścianie, aby umieścić go między
wszystkie liczby mniejsze od niej oraz wszystkie liczby większe.
>> Więc zróbmy to.
Podnieść 2, umieścić w ścianę począwszy, i wywołać 6 "bieżący
elementem. "Dlatego chcemy, aby spojrzeć na nasz bieżący element, 6.
A ponieważ jest większy niż 2, zostawiamy go tam
prawej ściany.
Następnie przechodzimy do spojrzeć na 5, jak nasze bieżący element i zobaczyć, że to
jest znowu większe od osi obrotu, tak, że zostawić je tam, gdzie jest po prawej stronie
boczne ścianki.
Ruszamy dalej.
Nasza obecna elementem jest teraz 1, i - och.
To jest teraz inna.
Bieżący element jest mniejszy niż obrotu, więc chcemy go umieścić
z lewej strony ścianie.
Aby to zrobić, po prostu przełączyć Prąd element o najniższej liczbie
Usytuowana na prawej ścianie.
Teraz przechodzimy do jednej ściany indeksu to 1 znajduje się po lewej
strona teraz ściany.
>> Czekać.
Właśnie pomieszane elementy dotyczące prawej stronie ściany, prawda?
Nie martw się.
To dobrze.
Jedyne, co nam zależy teraz jest to, że wszystkie te elementy do
prawej ściany są większe od osi obrotu.
Nie jest jednak rzeczywista kolejność zakłada.
>> Wróćmy teraz do sortowania.
Więc dalej, patrząc na Pozostałe elementy.
I w tym przypadku widać, że istnieją żadne inne elementy poniżej
obrotu, więc je wszystkie zostawić na prawej stronie ściany.
Wreszcie docieramy do bieżącego elementu i zobaczyć, że jest obrotowy.
Teraz, to znaczy, że mamy dwa fragmenty tablicy, pierwszej istoty
znajdującą się na osi obrotu, a z lewej strony ściany, a druga jest
większy od przegubu do prawej stronie ściany.
Chcemy umieścić element obrotowy pomiędzy dwa, a potem będziemy wiedzieć
że oś jest w prawo Ostateczna posortowane miejsce.
Więc przejść do pierwszego elementu na prawej stronie ściany z osią,
i wiemy obrotu jest w odpowiedniej pozycji.
>> Następnie powtórz tę czynność dla subarrays lewo i na prawo od osi obrotu.
Ponieważ ostatnio subarray jest tylko jeden Element długo, wiemy, że to już
sortowane, bo jak można być z zamawiać jeśli jesteś tylko jednym z elementów?
Na prawej stronie subarray, że zobaczyć, że przegub jest 5, a ścianą
jest po prostu na lewo od 6.
I bieżący element również Zaczyna się jako 6.
Tak więc 6 jest większa niż 5.
Zostawiamy go, gdzie jest on prawej stronie ściany.
Teraz, przechodząc, 3 jest mniejsza niż 5.
Więc należy go z pierwszym elementem w sam raz na ścianę.
Teraz przeniósł się do jednej ściany.
Teraz, przechodząc do 8.
8 jest większa niż 5, i tak to zostawić.
4 jest mniejsze niż 5, więc to przełącznik.
I na.
>> Za każdym razem powtarzamy proces na lewej i prawej strony tablicy. my
wybrać oś i robić porównań i utworzyć inny poziom w lewo i
prawo subarrays.
To wywołanie rekurencyjne potrwa do dotrzemy do końca, gdy mamy
dzieli się na ogólnej tablicy zaledwie subarrays o długości 1.
Stąd wiemy, że tablica jest posortowana ponieważ każdy element ma co
pewnym momencie było obrotu.
Innymi słowy, dla każdego elementu, numery do lewej są mniejsze
Wartości i wszystkie Liczby rację mają większe wartości.
>> Ta metoda działa bardzo dobrze, jeśli Wartość przegubu jest wybrana
mniej więcej w połowie Zakres wartości listy.
Oznaczałoby to, że po tym, jak poruszać elementy w okolicy, tam o tyle
elementy do lewego czopa jak jest po prawej stronie.
I charakter dziel i zwyciężaj z Algorytm quicksort jest następnie podjąć
pełna zaletą.
Stwarza to czas pracy O (n log n) n, ponieważ mamy do czynienia n minus 1
porównania w każdym pokoleniu i dziennika n bo musimy podzielić listę
log n razy.
Jednakże, w najgorszych przypadkach Algorytm może faktycznie być O (n
kwadratu.) Załóżmy na każdego pokolenia, obrotu tak dzieje się
najmniejsza lub największa numery jesteśmy sortowania.
To oznaczałoby rozbicie listę n razy i podejmowania n minus 1
porównania za każdym razem.
W ten sposób, o N kwadratu.
>> Jak możemy udoskonalić metody?
Dobrym sposobem, aby poprawić metody jest na celu zmniejszenie prawdopodobieństwa, że
czas jest zawsze właściwie o n do kwadratu.
Zapamiętaj ten najgorszy, najgorszy scenariusz może się zdarzyć, gdy tylko
obrotu wybrany jest zawsze najwyższa lub Najniższa wartość w tablicy.
W celu zapewnienia, jest to mniej prawdopodobne, możemy znaleźć pivot przez
wyboru wielu elementów i przyjmując wartość średnią.
>> Nazywam się Mark Grozen-Smith, i jest CS50.
>> Dla uproszczenia załóżmy, że ci, rzeczy są tylko liczby całkowite, ale
wiedzieć, że Quicksert -
Quicksert?
Przepraszam.
>> Tutaj mamy do liczb całkowitych 6, 5, 1, 3, 8, 4, 9.
>> GŁOŚNIK 1: Naprawdę?
>> Głośnik 2: Nie tylko.
>> GŁOŚNIK 1: Naprawdę?