[Powered by Google Translate] [Sort dodany] [Tommy MacWilliam] [Harvard University] [To jest CS50.TV] Rzućmy okiem na sortowanie wstawiania, algorytm podejmowania listę numerów i sortowania ich. Algorytm, pamiętasz, to po prostu krok po kroku procedurę realizacji zadania. Podstawową ideą rodzaju wstawiania, jest podzielenie naszej listy na dwie części, posortowane część i unsorted porcję. 

Na każdym etapie algorytmu numer przeniesiony z nieposortowanych części do sortowanie części aż w końcu cała lista jest posortowana. Oto lista sześciu nieposortowanych liczb - 23, 42, 4, 16, 8, i 15. Ponieważ numery te nie są w porządku rosnącym, są one sortowane. Ponieważ nie zaczęli jeszcze sortowania, będziemy rozpatrywać wszystkie sześć elementów naszej niesortowanych porcję. 

Kiedy rozpocząć sortowanie, umieścimy te posortowane numery do lewej tych. Więc zacznijmy od 23, pierwszy element w naszej liście. Nie mamy żadnych elementów w naszym sortowanie części jeszcze więc niech po prostu uważają 23 za początek i koniec naszej sortowanie części. Teraz nasza posortowane część ma jeden numer, 23, i nasz unsorted część ma te pięć numerów. Zróbmy teraz wstawić następny numer naszego nieposortowanych części, 42, do sortowanie części. 

Aby to zrobić, musimy porównać 42 do 23 - jedyny element w naszej sortowanie części tak daleko. Czterdziestu dwóch jest większy niż 23, dzięki czemu można po prostu dołączyć do końca 42 sortowanie z części listy. Great! Teraz nasz posortowane część ma dwa elementy, a nasze unsorted część ma cztery elementy. Więc, teraz przenieść się do 4, następny element w nieposortowanych porcji. Tak więc, w tym, gdzie powinna być umieszczona w sortowanie części? 

Pamiętaj, że chcesz umieścić ten numer w uporządkowanej kolejności więc nasz posortowane część pozostaje prawidłowo posortowane w każdym czasie. Jeśli to 4 na prawo od 42, to nasza lista będzie w porządku. No to kontynuować ruch od prawej do lewej w naszej części sortowania. Jak iść, niech przesunąć każdą liczbę w dół w miejscu, aby zrobić miejsce na nowy numer. Okay, 4 jest mniejsza niż 23, więc nie jesteśmy w stanie umieścić go tutaj, albo. Przejdźmy do 23 prawo o jedno miejsce. 

Oznacza to, że chcielibyśmy, aby umieścić 4 do pierwszego gniazda w sortowanie części. Zauważ, jak to miejsce na liście było już puste, ponieważ byliśmy w ruchu sortowanie elementów w dół jak już napotkał je. Dobrze. Tak, jesteśmy w połowie drogi. Kontynuujmy nasz algorytm wkładając 16 do sortowanie części. Szesnaście jest mniejsza niż 42, to powiedzmy 42 do przesunięcia w prawo. Sixteen jest również mniejsza niż 23, więc niech także przesunąć ten element. 

Teraz, 16 jest większy niż 4. Tak, wygląda na to, chcemy wstawić 16 między 4 i 23. Podczas przenoszenia przez sortowanie części listy, z prawej do lewej, 4 jest pierwszy numer widzimy, że jest mniejsza niż liczba chcemy wstawić. Tak, teraz możemy włożyć 16 do tego pustego gniazda, które, pamiętaj, stworzyliśmy przez poruszających elementów w części sortowania ponad jak już napotkał je. 

Dobrze. Teraz mamy cztery posortowane elementy i dwa nieposortowane elementy. Więc przejdźmy do 8 do sortowanie części. Osiem jest mniej niż 42. Osiem jest mniejsza niż 23. I 8 jest mniejsza niż 16. 8, ale jest większe niż 4. Więc chcielibyśmy włożyć 8 między 4 i 16. A teraz mamy tylko jeden element w lewo sort - 15. Piętnaście jest mniejsza niż 42, Piętnaście jest mniejsza niż 23. I 15 jest mniejsza niż 16. Ale 15 jest większa niż 8. 

Tak, o to, gdzie chcemy, aby nasz końcowy wstawiania. I gotowe. Nie mamy więcej elementów w nieposortowanych porcji i nasz posortowane część znajduje się w prawidłowej kolejności. Liczby są sortowane od najmniejszego do największego. Więc, rzućmy okiem na niektóre Pseudokod opisującym kroki właśnie ruchu. 

W linii 1, widzimy, że musimy iterować każdy element na liście z wyjątkiem pierwszego, od pierwszego elementu w niesegregowanych części po prostu się Pierwszy element w posortowanej części. Na liniach 2 i 3, jesteśmy śledzenia naszego miejsca w nieposortowanych porcji. Element reprezentuje liczbę jesteśmy obecnie porusza się w sortowanie części, oraz j reprezentuje nasz indeks w nieposortowanych porcji. 

W linii 4, jesteśmy iteracja posortowanej części od prawej do lewej. Chcemy zatrzymać Iterowanie raz elementu z lewej naszej aktualnej pozycji jest mniejsza niż element staramy się wstawić. W linii 5, mamy przesunięcie każdy element możemy spotkać o jedno miejsce w prawo. W ten sposób będziemy mieć wolną przestrzeń, aby wstawić do kiedy znajdziemy pierwszy element mniej niż element jesteśmy w ruchu. W linii 6, my aktualizujemy nasze licznik nadal poruszać w lewo przez sortowanie części. Wreszcie, w linii 7 mamy wstawienie elementu do sortowanie części listy. 

Wiemy, że to jest w porządku, aby wstawić do j pozycji, bo my już przeniesiony element, które było tam jedno miejsce w prawo. Pamiętaj, że idziemy przez sortowanie części od prawej do lewej, ale idziemy przez nieposortowanych części od lewej do prawej. Dobrze. Spróbujmy teraz przyjrzeć się, jak długo działa, że ​​algorytm wziął. Zaczniemy zadawać sobie pytanie, jak długo trwa ten algorytm, aby uruchomić w najgorszym przypadku. Przypomnijmy, że reprezentujemy ten czas pracy z Big notacji O. W celu uporządkowania naszej listy, mieliśmy do iteracyjnego elementy w nieposortowanych porcji i dla każdego z tych elementów, potencjalnie ponad wszystkich elementów w posortowanej części. Intuicyjnie, to brzmi jak (n ^ 2) O pracy. 

Patrząc na Pseudokod mamy pętlę zagnieżdżona w innej pętli które rzeczywiście brzmi jak (n ^ 2) O pracy. Jednak posortowane część listy nie zawierają całą listę, aż do samego końca. Mimo, że można potencjalnie wstawić nowy element na samym początku części sortowanie na każdej iteracji algorytmu, co oznacza, że ​​musimy patrzeć na każdy element aktualnie w sortowanie części. Tak, to znaczy, moglibyśmy potencjalnie wykonać jedno porównanie do drugiego elementu, dwa porównania dla trzeciego elementu, i tak dalej. Tak więc, całkowita ilość stopni jest suma liczb od 1 do długości listy minus 1.. Możemy reprezentować to z sumowaniu. 

Nie pójdziemy do podsumowań, ale to okazuje się, że to podsumowanie jest równa N (N - 1) w ciągu 2, co odpowiada n ^ 2/2 - n / 2. Kiedy mówimy o asymptotycznej wykonywania, to n ^ 2 termin będzie dominować ten n kadencję. Tak więc, w pewnym sensie wstawiania jest Big O (n ^ 2). Co zrobić, jeśli zabrakło sortowanie wstawiania na już posortowanej listy. W tym przypadku, będziemy po prostu budować posortowaną część od lewej do prawej. Tak, to musimy tylko na zlecenie n kroków. 

Oznacza to, że rodzaj wstawiania ma najlepsze case wydajność n które stanowią w Ω (n). I to na sortowanie wstawiania tylko jeden z wielu algorytmów możemy użyć, aby posortować listę. Nazywam się Tommy, i to jest CS50. [CS50.TV] Oh, po prostu nie mogę przestać, że po uruchomieniu. Oh, to zrobiliśmy - Boom! >>