[Музички] 

Даг LLOYD: Значи вметнување вид е уште еден алгоритам може да се користат за да се најде решение за низа. Идејата зад овој алгоритам е да се изгради на вашата низа сортирани во место, менувањето на елементи од начинот како да одиш, да се направи простор. Ова е малку различен од селекцијата вид или меурот вид, на пример, каде што ние сме прилагодување на локации, каде што ние сме прави свопови. 

Во овој случај, она што ние сме, всушност, прави е лизгачки елементи завршена, надвор од патот. Како го прави ова алгоритам работат во pseudocode? Па ајде да се произволно да се каже дека Првиот елемент од низата е сортирана. Ја градиме во место. 

И ние ќе одиме еден елемент во исто време и го изгради, па првото нешто што го гледаме е еден елемент низа. И по дефиниција, еден елемент на низата се подредени. 

Тогаш ние ќе го повторите овој процес until-- ние ќе повторам следните процес додека сите на елементите се подредени. Погледнете на следниот несортиран елемент и вметнете ја во сортирани дел, со менувањето на потребниот број на елементите од патот. Се надеваме дека оваа визуелизација ќе ви помогне да се види точно она што е случува со вметнување вид. 

Значи, повторно, тука е нашата целиот несортиран низа, сите елементи наведени во црвено. И ајде да ги следат чекори на нашата pseudocode. Првото нешто што го правиме, е што ние го нарекуваме Првиот елемент на низата, подредени. Значи ние сме само ќе речеме пет, сте сега се подредени. 

Потоа гледаме на следниот несортиран елемент од низата и сакаме да го внесете тој во подредени дел, со менувањето елементи завршена. Па две е следниот несортиран елемент од низата. Јасно е дека тоа му припаѓа пред пет, па она што сте ќе се направи е вид на одржат две настрана за една секунда, префрли пет над, а потоа вметнете две пред пет, каде да треба да оди. И сега можеме да кажеме дека две се подредени. 

Па како што можете да видите, ние сме само досега гледаше во два елементи на низата. Ние не го видовме одмор на сите, но ние сме добив овие два елементи подредени по начин на механизмот за менување. 

Значи ние се повторува процесот повторно. Погледнете на следниот несортиран елемент, тоа е еден. Ајде да се одржи тоа настрана за една секунда, префрлат се што во текот, и стави една каде треба да одам. 

Повторно, сепак, ние сме само некогаш гледаше во еден, два и пет. Не знаеме што друго е што доаѓаат, но ние сме подредени тие три елементи. 

Следниот несортиран елемент е три, па ние ќе го настрана. Ние ќе ја префрлат врз она што ние треба да се, овој пат не е сè како и во претходниот два случаи, тоа е само на пет. А потоа ние ќе се држиме во три, помеѓу две и пет. 

Шест е следниот несортиран елемент на низата. И всушност шест е поголем од пет, па ние дури и не треба да се направи било Замена на. Можеме само тактика шест право да крајот на подредени дел. 

И на крај, четири е последните несортиран елемент. Па ние ќе го постави настрана, се префрли во текот елементите што треба да се префрли во текот, и потоа го ставаат четири каде што припаѓа. И сега изгледа, ние сме вид на сите елементи. Известување со вметнување вид, немавме да се оди напред и назад низ низа. Отидовме само низ низа едно време, и ние се префрли работи што ние би веќе се сретнал, со цел да се направи простор за нови елементи. 

Значи, што е најлош случај сценариото со вметнување вид? Во најлош случај, низа е во обратен редослед. Ќе мора да се префрлат секој од n елементи до n позиции, секој пат кога ние направи вметнување. Тоа е многу на менувањето. 

Во најдобар случај, Низа е совршено подредени. И вид на како што се случи со пет и шест во примерот, каде што би можеле само да го тактика на без да се направи било менувањето, ние би суштина го направите тоа. 

Ако се замисли дека нашата низа беше еден преку шест, ние ќе започнете со означување е сортирана. Две доаѓа по еден, па ние само може да велат, во ред, и еден и два се подредени. Три доаѓа по две, така, во ред, еден и два и три се подредени. 

Ние не сме се прави размена, ние сме само се движи оваа произволна линија помеѓу сортирани и несортиран како што ние одиме. Толку ефикасно како што го направивме во примерот, вртење елементи сини, како да продолжиме. Значи, што е најлош случај траење, тогаш? Запомни, ако ние треба да се сврти секој од на n елементи евентуално n позиции, се надевам дека ви дава една идеја која најлош случај траење е Биг О од n квадрат. 

Ако низата е совршено подредени, сите ние треба да направите се погледне во секој елемент еднаш, а потоа сме подготвени. Значи во најдобар случај, тоа е омега на n. 

Јас сум Даг Лојд. Ова е CS50.