[Powered by Google Translate] [Insertion Sort]
[Томи MacWilliam] [Харвардския университет]
[Това е CS50.TV]
Нека да погледнем на вмъкване вид алгоритъм за вземане на списък от числа и ги сортира.
Алгоритъм, не забравяйте, е просто стъпка по стъпка процедурата за изпълнение на дадена задача.
Основната идея зад вмъкване вид, е да разделят нашия списък в две части,
подредени част и несортиран част.
>> На всяка стъпка на алгоритъма, се премества номер
от несортиран част на сортират част
, докато накрая на целия списък се сортират.
Ето списъка от шест несортирани числа - 23, 42, 4, 16, 8 и 15.
Тъй като тези номера не всички са във възходящ ред, те несортирани.
Тъй като ние сортиране все още не са започнали, ние ще разгледаме всички шест елемента несортирани част.
>> След като започнете сортиране, ние ще поставим тези сортирани номера в ляво от тях.
Така че, нека започнем с 23, първият елемент в нашия списък.
Ние все още не разполагат с никакви елементи в сортирали част,
така че нека да разгледа 23 за начало и край на сортирали част.
Сега, нашата подредени част има един номер, 23,
и нашата несортирани част има тези пет числа.
Нека сега поставете следващия номер несортирани нашата част, 42, в сортират част.
>> За да направите това, ние ще трябва да се сравни от 42 до 23 - единственият елемент в сортирали част досега.
Четиридесет и две е по-голям от 23, така че може просто да добавите 42 до края
подредени част от списъка. Чудесно!
Сега нашата подредени част има два елемента, и несортирани нашата част има четири елемента.
Така че, нека сега се движат на четири, следващият елемент в несортиран част.
Така че, когато това трябва да бъде поставен в сортират част?
>> Не забравяйте, че ние искаме да се постави този номер в сортират за
така че нашата подредени част остава правилно подредени по всяко време.
Ако ние поставяме от 4 до правото на 42, а след това в нашия списък ще бъде в ред.
Така че, нека да продължи да се движи отдясно-наляво в нашия вид част.
Като се движим, да смени всеки номер за определяне на място, за да направи място за новия номер.
Добре, 4 също е по-малко от 23, така че не можем да го поставите тук.
Нека преминем 23 правото на едно място.
>> Това означава, че ние бихме искали да поставите четири в първия слот в сортират част.
Забележете как това пространство в списъка вече е празна,
защото сме се движи сортирани елементи, както сме ги срещали.
Добре. Така че, ние сме по средата там.
Нека продължим нашия алгоритъм чрез вмъкване на 16 в сортират част.
Sixteen е по-малко от 42, така че нека прехвърли 42 надясно.
Шестнадесет също е по-малко от 23, така че нека да измести този елемент.
>> Сега, 16 години е по-голяма от 4. Така че, изглежда, че ние бихме искали да вкарате 16 между 4 и 23.
Докато се движат през сортират част на списъка от дясно на ляво,
4 е първото число сме виждали, че е по-малък от броя
ние се опитваме да вмъкнете.
Така че, сега можем да вмъкнете 16 в този празен слот,
които, не забравяйте, ние сме създали от движещи се елементи в нещо част
както сме ги срещали.
>> Добре. Сега имаме четири сортирани елемента и два несортирани елементи.
Така че, нека да преминем 8 в сортират част.
Осем е по-малко от 42.
Осем е по-малко от 23.
И 8 е по-малко от 16.
Но 8 е по-голяма от 4.
Така че, ние бихме искали да вмъкнете 8 между 4 и 16.
И сега ние просто трябва още един оставяли елемент да сортирате - 15.
Петнадесет е по-малко от 42,
Петнадесет е по-малко от 23.
И 15 е по-малко от 16.
Но 15 е по-голяма от 8.
>> Така че, тук е мястото, където ние искаме да направим нашата крайна вмъкване.
И сме готови.
Ние не разполагаме с повече елементи в несортиран част,
и нашата подредени част е в правилния ред.
Числата са подредени от най-малките до най-големите.
Така че, нека да разгледаме някои pseudocode, която описва стъпките, които току-що са извършили.
>> На ред 1, можем да видим, че ние ще трябва да обхождане на всеки елемент в списъка
с изключение на първата, тъй като първият елемент в несортиран част просто ще стане
първият елемент в сортират част.
На линии 2 и 3, ние сме следене на нашето място в несортиран част.
Елемент представлява номер, с който в момента се движат в сортират част,
и к представлява нашия индекс в несортиран част.
>> На ред 4, ние сме итерации през подредени част от дясно на ляво.
Искаме да спрем итерации веднъж елемента в ляво на настоящата си позиция
е по-малко от елемент, който ние се опитваме да вмъкнете.
На линия 5, преместване всеки елемент се сблъскваме с едно място в дясно.
По този начин, когато намерим първия елемент, ще имаме свободно пространство, за да вмъкнете в
по-малко от елемент, който ние се движим.
На линия 6, ние сме актуализиране на нашите брояч, за да продължи да се движи наляво през сортират част.
И накрая, по линия 7, ние сме вмъкване на елемент в сортират част на списъка.
>> Ние знаем, че е добре да поставите в позиция J,
защото вече сме преместили елемент, който да бъде използван там един пространството дясно.
Не забравяйте, че ние се движим през подредени част от дясно на ляво,
но ние се движим през несортиран част от ляво на дясно.
Добре. Нека сега да видим колко дълго работи с този алгоритъм взе.
Ще първо да си зададем въпроса колко време е необходимо, за този алгоритъм, за да се движи в най-лошия случай.
Спомнете си, че ние представляваме това време на работа с Big O нотация.
За да се оправи в нашия списък, имахме за обхождане на елементите в несортиран част,
и за всеки от тези елементи, потенциално над всички елементи в сортират част.
Интуитивно, това звучи като O (N ^ 2) експлоатация.
>> Търсите в нашия pseudocode, имаме една линия, вложени в друг цикъл,
, които наистина звучи като O (N ^ 2) експлоатация.
Въпреки това, подредени част от списък не съдържа целия списък до самия край.
Все пак, ние потенциално биха могли да вмъкнете нов елемент в самото начало на подредени част
на всяка итерация на алгоритъма,
което означава, че ние ще трябва да разгледаме всеки елемент в момента подредени част.
Така че, това означава, че ние може потенциално да направи едно сравнение за втори елемент,
две сравнения за третия елемент, и така нататък.
Така, общият брой на стъпките е сумата на числата от 1 до дължината на списъка минус 1.
Ние може да представлява това с сумиране.
>> Ние няма да отидат в summations тук, но се оказва, че това сумиране е равна на
N (N - 1) над 2, което е еквивалентно N ^ 2/2 - N / 2.
Когато говорим за асимптотичната по време на работа,
този N ^ 2 план ще да доминират тази н мандат.
Така че, вмъкване вид е Big O (N ^ 2).
Какво ще стане, ако ние се завтече вмъкване вид на вече сортиран списък.
В този случай, ние просто ще изгради подредени част от ляво на дясно.
Така че, ние ще трябва само по нареждане на стъпките н.
>> Това означава, че включването вид има най-добрия случай изпълнението на N,
, които ние представляваме с Ω (N).
И това е за поставяне вид,
само един от многото алгоритми можем да използваме, за да сортирате списъка.
Моето име е Томи, и това е CS50.
[CS50.TV]
О, ти просто не може да спре, че след като тя започва.
О, ние сме го направили - >> Boom!