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