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