[За възпроизвеждане на музика] 

Дъг LLOYD: Така сортиране чрез вмъкване е друг алгоритъм можем да използваме, за да сортирате масив. Идеята зад този алгоритъм е да се изгради своя сортиран масив на мястото, пренасочване елементи от Между другото, както и да отидеш, за да направи място. Това е малко по-различен от подбора на сортиране или балон сортиране, например, когато ние сме за коригиране на местата, когато ние правим суапове. 

В този случай това, което сме в действителност прави е плъзгащите елементи над, от пътя. Как действа този алгоритъм работят в Псевдокод? Ами нека просто кажем, че произволно Първият елемент на масива е сортиран. Ние сме го построи на мястото. 

Просто ще отида един елемент в даден момент и го изградим, и така че първото нещо, което виждаме е един елемент масив. И по дефиниция, а един масив се сортира. 

След това ще се повтаря този процес until-- ние ще се повтори след процеса докато всички елементи са подредени. Виж следващия елемент и е сортиран я поставете в сортиран част, чрез прехвърляне на необходимия брой на елементи от пътя. Надяваме се тази визуализация ще ви помогне да видите точно това, което е става с поставяне на сортиране. 

Така че отново, ето ни Цялата сортиран масив, всички елементи, посочено в червено. И нека следвайте стъпки на нашата Псевдокод. Първото нещо, което правим, е, което наричаме Първият елемент на масива, сортирани. Така че ние сме просто ще кажем пет, което сега сортирани. 

След това ще разгледаме в следващия несортиран елемент на масива и ние искаме да вмъкнете, че подредени в частта, чрез прехвърляне на елементи свърши. Така че две е следващата несортирани елемент на масива. Очевидно той принадлежи преди пет, така че това, което ние ще направим е нещо като държи две настрани за секунда, смени пет свърши, а след това поставете две преди пет години, когато да трябва да отида. И сега можем да кажем, че двама се сортира. 

Така че, както виждате, ние сме само доколкото погледна два елемента от масива. Ние не са се запознали с почивка на всички, но ние сме имам тези два елемента сортирани по начин на механизма за превключване. 

Така че ние повторете процеса отново. Виж следващия несортирани елемент, това е едно. Нека да държи настрана, че за секунда, измести всичко свърши, и сложи една където трябва да отидете. 

Отново, все още сме само съм погледна към един, два и пет. Ние не знаем какво друго идва, но ние сме подредени тези три елемента. 

Следваща несортирани елемент е три, така че ние ще го отмени. Ние ще се измести върху това, което ние Трябва да който този път не е всичко, както в предишния два случая, това е само пет. И тогава ние ще се придържаме три, между двете и петимата. 

Six е следващата несортирани елемент на масива. И в действителност шест е по-голяма от пет, така ние дори не е необходимо да се направи всяка смяна. Ние можем само да халс шест точно да края на сортирани част. 

Накрая, е четири Последният елемент е сортиран. Така че ние ще го отмени, смени над елементите, които трябва да се премине през, и след това пуснати четири където му е мястото. А сега погледнете, ние сме сортиране на всички елементи. Забележете с вмъкване сортиране, не сме имали да се върна назад из масива. Отидохме само от другата страна на масива едно и също време, и ние се размърда нещата че вече бяхме срещнали, за за да направи място за новите елементи. 

Така че това, което е най-лошия случай сценарий с вкарване подреди? В най-лошия случай, Масивът е в обратен ред. Трябва да се премине всеки от п елементи до п позиции, всеки път, когато направи вмъкване. Това е много изместване. 

В най-добрия случай, масив е перфектно подредени. И нещо като това, което се е случило с пет и шест в примера, където бихме могли просто да го халс на без да се налага да се направи някоя преместване, щяхме да направим това по същество. 

Ако си представим, че нашата масив е един през шест, щяхме да започнем от обявява един се сортира. Две идва след една, така че ние може просто казват, OK, и едно и две са подредени. Три идва след две така, OK, една и две и три са подредени. 

Ние не се правят суапове, ние сме просто се движат тази произволна линия между сортирани и несортирани като отидем. Както ефективно, както направихме в примера, превръщайки елементи синьо, докато напредваме. Така че това, което е най-лошият време на работа, а след това? Не забравяйте, че ако трябва да се смени всяка от п елементи евентуално н позиции, да се надяваме, че дава една идея, която най-лошия случай Времето за автономна работа Big O на п квадрат. 

Ако матрицата е напълно подредени, всички ние трябва да направим се разгледа всеки един елемент веднъж, а след това сме готови. Така че в най-добрия случай, това е омега от п. 

Аз съм Дъг Лойд. Това е CS50.