[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.