>> [За възпроизвеждане на музика]
>> Дъг LLOYD: Така сортиране чрез вмъкване е друг алгоритъм можем да използваме, за да сортирате масив.
Идеята зад този алгоритъм е да се изгради своя сортиран масив
на мястото, пренасочване елементи от Между другото, както и да отидеш, за да направи място.
Това е малко по-различен от подбора на сортиране или балон
сортиране, например, когато ние сме за коригиране на местата,
когато ние правим суапове.
>> В този случай това, което сме в действителност прави е плъзгащите елементи
над, от пътя.
Как действа този алгоритъм работят в Псевдокод?
Ами нека просто кажем, че произволно Първият елемент на масива е сортиран.
Ние сме го построи на мястото.
>> Просто ще отида един елемент в даден момент и го изградим, и така че първото нещо, което виждаме
е един елемент масив.
И по дефиниция, а един масив се сортира.
>> След това ще се повтаря този процес until-- ние ще се повтори след процеса
докато всички елементи са подредени.
Виж следващия елемент и е сортиран я поставете в сортиран част,
чрез прехвърляне на необходимия брой на елементи от пътя.
Надяваме се тази визуализация ще ви помогне да видите точно това, което е
става с поставяне на сортиране.
>> Така че отново, ето ни Цялата сортиран масив,
всички елементи, посочено в червено.
И нека следвайте стъпки на нашата Псевдокод.
Първото нещо, което правим, е, което наричаме Първият елемент на масива, сортирани.
Така че ние сме просто ще кажем пет, което сега сортирани.
>> След това ще разгледаме в следващия несортиран елемент на масива
и ние искаме да вмъкнете, че подредени в частта,
чрез прехвърляне на елементи свърши.
Така че две е следващата несортирани елемент на масива.
Очевидно той принадлежи преди пет, така че това, което ние ще направим
е нещо като държи две настрани за секунда, смени пет свърши, а след това поставете две
преди пет години, когато да трябва да отида.
И сега можем да кажем, че двама се сортира.
>> Така че, както виждате, ние сме само доколкото погледна два елемента от масива.
Ние не са се запознали с почивка на всички, но ние сме
имам тези два елемента сортирани по начин на механизма за превключване.
>> Така че ние повторете процеса отново.
Виж следващия несортирани елемент, това е едно.
Нека да държи настрана, че за секунда, измести всичко свърши, и сложи една
където трябва да отидете.
>> Отново, все още сме само съм погледна към един, два и пет.
Ние не знаем какво друго идва, но ние сме подредени тези три елемента.
>> Следваща несортирани елемент е три, така че ние ще го отмени.
Ние ще се измести върху това, което ние Трябва да който този път
не е всичко, както в предишния два случая, това е само пет.
И тогава ние ще се придържаме три, между двете и петимата.
>> Six е следващата несортирани елемент на масива.
И в действителност шест е по-голяма от пет, така ние дори не е необходимо да се направи всяка смяна.
Ние можем само да халс шест точно да края на сортирани част.
>> Накрая, е четири Последният елемент е сортиран.
Така че ние ще го отмени, смени над елементите, които трябва да се премине през,
и след това пуснати четири където му е мястото.
А сега погледнете, ние сме сортиране на всички елементи.
Забележете с вмъкване сортиране, не сме имали
да се върна назад из масива.
Отидохме само от другата страна на масива едно и също време, и ние се размърда нещата
че вече бяхме срещнали, за за да направи място за новите елементи.
>> Така че това, което е най-лошия случай сценарий с вкарване подреди?
В най-лошия случай, Масивът е в обратен ред.
Трябва да се премине всеки от п елементи до п позиции, всеки път, когато
направи вмъкване.
Това е много изместване.
>> В най-добрия случай, масив е перфектно подредени.
И нещо като това, което се е случило с пет и шест в примера,
където бихме могли просто да го халс на без да се налага да се направи някоя преместване,
щяхме да направим това по същество.
>> Ако си представим, че нашата масив е един през шест,
щяхме да започнем от обявява един се сортира.
Две идва след една, така че ние може просто казват, OK, и едно и две са подредени.
Три идва след две така, OK, една и две и три са подредени.
>> Ние не се правят суапове, ние сме просто се движат тази произволна линия
между сортирани и несортирани като отидем.
Както ефективно, както направихме в примера, превръщайки елементи синьо, докато напредваме.
Така че това, което е най-лошият време на работа, а след това?
Не забравяйте, че ако трябва да се смени всяка от п елементи евентуално н позиции,
да се надяваме, че дава една идея, която най-лошия случай
Времето за автономна работа Big O на п квадрат.
>> Ако матрицата е напълно подредени, всички ние трябва да направим
се разгледа всеки един елемент веднъж, а след това сме готови.
Така че в най-добрия случай, това е омега от п.
>> Аз съм Дъг Лойд.
Това е CS50.