>> [MUZYKI]
DOUG LLOYD: Wybór rodzaju jest algorytm, który, jak można się spodziewać,
sortuje zestaw elementów.
I algorytm wycofywania to zestaw krok po kroku
instrukcji do wykonania zadania.
>> W doborze posortować Podstawowym założeniem jest to,
niesortowanych znaleźć najmniejszy element i dodać go do końca listy sortowane.
Skutecznie co to robi jest budowa sortowaną listę jeden element w określonym czasie.
Złamanie go do Pseudokod możemy stwierdzić tego algorytmu
w następujący sposób, powtórzyć, aż brak elementów nieposortowane pozostać.
Szukaj poprzez nieposortowane Dane znaleźć najmniejszą wartość,
następnie zamienić najmniejszą wartość z Pierwszym elementem nieposortowanej części.
>> To może pomóc w wizualizacji tego, więc rzućmy okiem na to.
Więc to, jak twierdzą, jest nieposortowane tablica i mam
wskazane go przez wskazanie, że wszystkie elementy są w kolorze czerwonym,
nie są one jednak klasyfikowane.
Jest cała nieposortowane część tablicy.
>> Więc chodźmy po schodach Wybór rodzaju sortowania tej tablicy.
Więc jeszcze raz, że my będziemy powtarzać dopóki pozostają żadne elementy nieposortowane.
Będziemy przeszukiwać Dane znaleźć najmniejszą wartość,
a następnie zamienić tę wartość z Pierwszym elementem nieposortowanej części.
>> Teraz znowu cała Tablica jest nieposortowane częścią.
Wszystkie elementy są nieposortowane czerwonych.
Tak więc przeszukiwać i znaleźć najmniejszą wartość.
Zaczynamy na początku, idziemy do końca,
znaleźć najmniejszą wartość jest jeden.
Więc to jest część pierwsza.
A następnie część druga, zamienić tę wartość z pierwszym elementem nieposortowanej części,
lub pierwszy red elementem.
>> W tym przypadku, byłoby pięć, więc zamienić jeden i pięć.
Gdy to zrobimy, możemy wizualnie zobaczyć, że mamy
przeniósł najmniejszy o wartości elementu tablicy, na samym początku.
Skutecznie sortowania ten element.
>> I tak możemy rzeczywiście potwierdzają i stwierdza, że ​​jeden, jest klasyfikowane.
I tak będziemy wskazywać posortowane części z naszej tablicy, kolorując to niebieski.
>> Teraz tylko powtórzyć proces ponownie.
Mamy przeszukać nieposortowanej części tablica znaleźć najmniejszy element.
W tym przypadku, to jest dwa.
>> Możemy zamienić, że z pierwszym elementem nieposortowanej części.
W tym przypadku dwie również dzieje się pierwszym elementem nieposortowanej części.
Tak więc zamienić dwa z siebie, które tak naprawdę pozostawia dwa
gdzie jest, i to jest klasyfikowane.
Kontynuując, możemy przeszukiwać znaleźć najmniejszy element.
To trzy.
Możemy zamienić go z pierwszym Element, który jest pięć lat.
A teraz trzy są sortowane.
>> Mamy przeszukać ponownie, a my znaleźć najmniejszy element jest cztery.
Możemy zamienić go z pierwszym elementem Część nieposortowane, a teraz cztery są sortowane.
>> Uważamy, że pięć jest najmniejszy element.
Możemy zamienić go z pierwszym elementem nieposortowanej części.
I teraz pięć jest posortowana.
>> I wtedy wreszcie, nasze nieposortowane część składa się
z tylko jednego elementu więc przeszukiwać
i okazuje się, że sześć jest Najmniejszy i w rzeczywistości jedynym elementem.
I wtedy możemy stwierdzić, że jest klasyfikowane.
A teraz mamy włączony naszą tablicę przed całkowitym nieposortowane
na czerwono, aby całkowicie klasyfikowane w kolorze niebieskim, za pomocą wyboru rodzaju.
>> Więc co jest najgorszym przypadku tutaj?
Dobrze się najgorszego Sprawa, musimy spojrzeć na
wszystkie elementy tablicy do znaleźć najmniejszą niesegregowanych elementu,
i musimy powtórzyć proces ten n razy.
Raz dla każdego elementu tablicy dlatego, że tylko w tym algorytmie,
jakby jeden element na raz.
>> Jaki jest najlepszy scenariusz?
Cóż, to jest dokładnie to samo, prawda?
Aktualnie mamy do jeszcze krok po kroku każdy element tablicy
W celu potwierdzenia, że ​​jest to, W rzeczywistości, najmniejsze elementem.
>> Tak więc w najgorszym przypadku czas pracy, możemy trzeba powtórzyć proces n razy,
raz dla każdej z n elementów.
A w najlepszym przypadku, musimy zrobić to samo.
>> Więc wracając myślami do naszego Złożoność obliczeniowa przybornik,
jak myślisz, co jest najgorsze Sprawa wykonawcze do wyboru rodzaju?
Jak myślisz, co jest najlepsze Sprawa wykonawcze do wyboru rodzaju?
>> Czy domyślasz Big O n do kwadratu, i Big Omega n do kwadratu?
Byłbyś w prawo.
Są to w rzeczywistości Najgorszy i najlepszy prowadzony przypadku
razy, do wyboru rodzaju.
>> Jestem Doug Lloyd.
To CS50.