[Powered by Google Translate] TOMMY: Chcę spojrzeć na rodzaj karnetu, algorytm
podejmowania listę numerów i sortowania ich.
Algorytm, pamiętasz, to po prostu krok po kroku
Procedura realizacji zadania.
Podstawową ideą rodzaju selekcji jest podzielenie
Nasza lista jest na dwie części -
posortowane część i unsorted porcję.
Na każdym etapie algorytmu numer przeniesiony z
unsorted część do sortowanie części, aż w końcu
Cała lista jest posortowana.
Więc oto lista sześciu liczb -
23, 42, 4, 16, 8, i 15.
Teraz cała lista jest uważany nieposortowane.
Nawet jeśli ilość jak 16 maja być już w odpowiedniej
lokalizacja, nasz algorytm nie ma możliwości dowiedzenia się, że do
Cała lista jest posortowana.
Więc będziemy rozpatrywać każdy numer do sortowania aż sortować
to sami.
My wiemy, że lista ma być w porządku rosnącym.
Więc chcemy budować posortowaną część naszej listy
od lewej do prawej, od najmniejszych do największych.
Aby to zrobić, musimy znaleźć minimalną niesortowanych elementu
i umieścić na końcu części sortowanie.
Ponieważ ta lista nie jest posortowana, jedynym sposobem na to jest do
patrzeć na każdy element w nieposortowanych części, pamiętając
który to element jest najniższą i porównanie
każdy element do tego.
Więc najpierw spojrzeć na 23.
Jest to pierwszy element widzieliśmy, więc będziemy pamiętać
jest jak najmniej.
Dalej przyjrzymy 42.
42 jest większy niż 23, to 23 jest nadal minimalna.
Dalej jest 4 co jest mniej niż 23, więc musimy pamiętać, 4
jako nowego minimum.
Dalej jest 16, który jest większy niż 4, SO 4
pozostaje minimalna.
8 jest większa niż 4, i 15 jest większy niż 4, tak, 4 są
Najmniejszy unsorted element.
Dlatego, mimo że jako ludzie możemy od razu zauważyć, że 4 jest
Minimalny element, nasz algorytm musi spojrzeć na
każdy unsorted element, nawet po znalazłeś 4 -
Minimalny element.
Więc teraz, że odkryliśmy minimalny element, 4, my chcemy
, aby przenieść go do sortowanie części listy.
Ponieważ jest to pierwszy krok, to znaczy, że chcesz umieścić 4 na
początek listy.
23 jest teraz na początku na liście, to
Wymieńmy się 4 i 23.
Więc teraz nasza lista wygląda tak.
Wiadomo, że 4 są w miejscu docelowym, ponieważ
jak najmniejszy element i element w początku
wykazu.
Więc oznacza to, że nie zawsze trzeba przenieść go ponownie.
Więc powtórzyć ten proces, aby dodać kolejny element do
posortowane część listy.
Wiemy, że nie musimy patrzeć na 4, ponieważ jest to
już posortowane.
Tak więc możemy rozpocząć na 42, które będziemy pamiętać jako
Minimalny element.
Więc następnym będziemy patrzeć na 23, która jest mniejsza niż 42, więc mamy
Pamiętam 23 jest nowym minimum.
Dalej widzimy 16, która jest mniejsza niż 23, więc
16 to nowe minimum.
Teraz patrzymy na 8, który jest mniej niż 16, więc
8 jest nowe minimum.
I w końcu 8 jest mniejsza niż 15, to wiadomo, że jest co najmniej 8
unsorted element.
To znaczy, że powinniśmy dodać 8 do posortowane
część listy.
Teraz 4 jest jedynym posortowane element, więc chcemy, aby umieścić
8 obok 4.
Od 42 jest pierwszym elementem w nieposortowanych części
lista, będziemy chcieli, aby zamienić 42 i 8.
Więc teraz nasza lista wygląda tak.
4 i 8 przedstawiają część sortowane na liście, a
Pozostałe numery reprezentują unsorted
część listy.
Więc nadal z innym iteracji.
Zaczynamy 23 ten czas, ponieważ nie musimy patrzeć na
4 i 8 więcej, bo już
już posortowane.
16 jest mniejsza niż 23, więc będziemy pamiętać
16 jako nowe minimum.
16 jest mniejsza niż 42, 15, ale jest mniejsza niż 16, 15 musi być więc
minimum unsorted element.
Więc teraz chcemy zamienić 15 i 23 do
dać nam tę listę.
Posortowane część listy składa się z 4, 8 i 15, a
elementy te są jeszcze nieposortowane.
Ale tak się składa, że ​​następny unsorted element, 16,
jest już posortowana.
Jednakże, nie ma mowy, dla naszego algorytmu wiedzieć, że 16
jest już w odpowiednim miejscu, więc musimy jeszcze
powtórzyć dokładnie ten sam proces.
Widzimy zatem, że 16 jest mniejsza niż 42, i 16, jest mniejsza niż 23, to
16 musi być minimalna elementem.
To niemożliwe, aby zamienić ten element, z samym sobą, więc możemy
po prostu zostawić go w tym miejscu.
Musimy więc jeszcze jeden karnet naszego algorytmu.
42 jest większy niż 23, 23 musi być więc
minimum unsorted element.
Kiedy zamienić 23 i 42, ale kończy się z naszym ostatnim
posortowane list -
4, 8, 15, 16, 23, 42.
Wiemy, 42 musi być w odpowiednim miejscu, ponieważ jest to
Jedynym elementem, w lewo, a to rodzaj selekcji.
Zróbmy teraz sformalizować nasz algorytm z niektórymi
pseudokod.
Na pierwszej linii, widzimy, że musimy zintegrować ponad
każdy element listy.
Wyjątkiem ostatniego elementu, od 1 element
lista jest już posortowana.
Na drugiej linii, uważamy pierwszy element unsorted
część listy jest minimum, jak to zrobiliśmy z naszym
przykładem, więc mamy coś do porównania do.
Trzecia linijka rozpoczyna drugą pętlę, w której iteracji
każdy unsorted element.
Wiemy, że po I iteracji, posortowane część
naszej liście musi ja w nim elementy od każdego kroku
sortuje jeden element.
Tak więc pierwszym elementem unsorted musi być w pozycji I plus 1.
W linii cztery, porównana z elementem do minimum
Element, który widzieliśmy do tej pory.
Jeśli obecny jest elementem mniejszych od
element, a następnie pamiętać bieżący element jak nowy
minimum w wierszu piątym.
Wreszcie, na liniach sześć i siedem, zamienimy minimum
elementu z pierwszym elementem niesegregowanych, co
dodanie go do części sortowanie listy.
Gdy już mamy algorytm, istotne pytanie
siebie jako programistów jest jak długo to potrwa?
Zaczniemy zadawać sobie pytanie, jak długo trzeba czekać na to
Algorytm do uruchomienia w najgorszym przypadku?
Przypominam, że reprezentujemy ten bieg
razem z wielkim notacji O.
W celu określenia minimalnego niesortowanych elementu, że
zasadniczo miał porównać każdy element w liście do
każdy inny element na liście.
Intuicyjnie, to brzmi jak O n kwadratu operacji.
Patrząc na Pseudokod, mamy także pętlę zagnieżdżone
inna pętla, która rzeczywiście brzmi jak O
n kwadratu operacji.
Należy jednak pamiętać, że nie należy patrzeć na
Cała lista przy określaniu minimalnego niesortowanych element?
Po wiedział, że 4 sortowano, na przykład, nie
trzeba spojrzeć na nią ponownie.
Więc robi to obniżyć czas pracy?
Na naszej liście długości 6, musieliśmy zrobić pięć
porównania dla pierwszego elementu, cztery dla porównania
drugi element, i tak dalej.
To oznacza, że ​​całkowita liczba stopni jest suma
liczby całkowite od 1 do długości listy minus 1..
Możemy reprezentować to z sumowaniu.
Nie pójdziemy do podsumowań tutaj.
Ale okazuje się, że to podsumowanie jest równy n razy
n minus 1 na 2.
Lub równoważnie, n do kwadratu przez 2 minus n nad 2.
Kiedy mówimy o asymptotycznej wykonywania, to n squared termin
ma zamiar zdominować tę n kadencję.
Wybór jest więc rodzajem O n kwadratu.
Przypomnijmy, że w naszym przykładzie, sort wybór nadal potrzebne do
sprawdzić, czy numer, który został już posortowane
musiał zostać przeniesiony.
Więc to oznacza, że ​​jeśli prowadził rodzaj wyboru ponad już
sortowana lista, wymagałoby to taką samą liczbę kroków, jak to
by podczas pracy nad liście całkowicie nieposortowanych.
Więc wybór sort ma najlepszą wydajność przypadku n kwadratu,
które stanowią o omega n kwadratu.
I to za rodzaj selekcji.
To tylko jeden z wielu algorytmów możemy
użyć, aby posortować listę.
Nazywam się Tommy, i to jest CS50.