[MUZYKI] DOUG LLOYD: Tak Sortowanie przez wstawianie jest inny Algorytm możemy użyć do sortowania tablicy. Ideą tego algorytmu jest zbudowanie posortowaną tablicę w miejscu przesunięcie elementów z sposób jak przejść, aby zrobić miejsce. To jest nieco inny od wyboru rodzaju lub bańki sortowania, na przykład, gdy mamy regulację położenia, gdzie robimy swapy. W tym przypadku to, co jesteśmy w rzeczywistości robi to elementy ślizgowe powyżej, z drogi. Jak to algorytm pracy w Pseudokod? Dobrze niech po prostu arbitralnie powiedzieć, że Pierwszy element tablicy jest sortowana. Budujemy go w miejscu. Będziemy iść jeden element na raz i budować, to i tak pierwsze co widzimy Jest to tablica jeden element. A z definicji, jednym element tablicy jest sortowana. Potem powtórzyć ten proces until-- będziemy powtarzać następujący proces dopóki wszystkie elementy są klasyfikowane. Spójrz na następny nieposortowanego elementu i włóż ją do części posortowanej, przez przeniesienie wymaganej liczby z elementami z drogi. Mam nadzieję, że ta wizualizacja pomoże Ci dokładnie zobaczyć, co jest dzieje z Sortowanie przez wstawianie. Więc jeszcze raz, tu jest nasz Cały nieposortowane tablica, wszystkie elementy oznaczone na czerwono. I Prześledźmy etapy naszej Pseudokod. Pierwszą rzeczą, jaką możemy zrobić, jest nazywamy Pierwszy element tablicy, sortowane. Więc jesteśmy po prostu powie pięć, jesteś teraz sortowane. Następnie patrzymy na następny nieposortowane element tablicy i chcemy wstawić, że w sortowanej porcji przez przesunięcie elementów ciągu. Więc dwa to kolejny nieposortowane Element tablicy. Oczywiście należy przed pięć, więc co zrobimy jest rodzajem przytrzymaj dwa bok na chwilę, przesunięcie pięć nad, a następnie włóż dwie przed piątą, gdzie powinien iść. A teraz możemy powiedzieć, że dwa są sortowane. Więc jak widać, mamy tylko do tej pory wyglądała na dwóch elementów macierzy. Nie spojrzał na spoczywać na wszystkich, ale mamy ale te dwa elementy klasyfikowane według sposób z mechanizmem przesuwania. Więc jeszcze raz powtórzyć proces. Spójrz na następny nieposortowane Element, który jest jeden. Załóżmy, że oprócz posiadania przez sekundę, przesunąć wszystko nad i umieścić jeden gdzie powinien iść. Ponownie, wciąż, mamy zawsze tylko spojrzał na jeden, dwa, i pięć. Nie wiemy, co jeszcze przyjdzie, ale my klasyfikowane te trzy elementy. Następny nieposortowane elementem jest trzy, więc będziemy odłóż go na bok. Będziemy zmieniać na co potrzebne do której tym razem to nie wszystko, jak w poprzednim dwa przypadki, to tylko pięć. A potem będziemy trzymać trzy w, między nimi a pięć. Sześć jest kolejnym nieposortowane elementem tablicy. W rzeczywistości six jest większa niż pięć, tak nawet nie trzeba robić żadnych swapping. Możemy po prostu przykleić sześć prawo na Koniec sortowany porcji. Wreszcie, cztery jest Ostatnim elementem nieposortowane. Będziemy więc odłóż go na bok, przesunięcie w elementy musimy przenieść się, a następnie umieścić cztery, gdzie należy. A teraz spójrz, mamy sort wszystkich elementów. Zawiadomienie o wprowadzeniu sortowanie, nie mieliśmy iść tam iz powrotem po tablicy. Udaliśmy się tylko po drugiej stronie tablicy jeden raz, a my przesunięty rzeczy że że już napotkał, w celu aby zrobić miejsce dla nowych elementów. Więc co jest najgorszym przypadku Scenariusz z wstawiania rodzaju? W najgorszym przypadku, Tablica jest w odwrotnej kolejności. Musisz przenieść każdego z n elementów do pozycji n, każdy mamy czas dokonać wkładanie. To dużo przesunięcia. W najlepszym przypadku, Tablica jest doskonale klasyfikowane. I coś w rodzaju tego, co się stało z piątej i szóstej przykład gdzie możemy po prostu przykleić go na bez konieczności wykonywania jakichkolwiek zmianę biegów, my w zasadzie zrobić. Jeśli możesz sobie wyobrazić, że nasze Tablica była jedną z sześciu, chcielibyśmy zacząć od oświadczając, jeden jest posortowana. Dwa przychodzi po jednej więc możemy po prostu powiedzieć: OK, dobrze jeden i dwa są klasyfikowane. Trzy przychodzi po dwóch, tak, OK, jeden i dwa i trzy są klasyfikowane. Nie robisz żadnych swapy, jesteśmy po prostu się to dowolny wiersz między sortowane i niesortowane jak idziemy. Tak skutecznie, jak to zrobiliśmy w tym przykładzie, elementy przygasa, jak postępować. Więc co jest najgorszym przypadku czas pracy, a potem? Pamiętaj, że jeśli mamy do zmiany każdego z elementy n ewentualnie pozycji n, miejmy nadzieję, że daje pomysł, że w najgorszym przypadku czas pracy jest Big O n do kwadratu. Jeśli tablica jest idealnie klasyfikowane, wszystko co musisz zrobić, jest patrzeć na każdego elementu raz, a potem gotowe. Tak więc w najlepszym wypadku, to omega n. Jestem Doug Lloyd. To CS50.