[Музички] Даг LLOYD: Добро, така меур вид е алгоритам можете да го користите да се најде решение е збир на елементи. Ајде да ги разгледаме во тоа како таа работи. 

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

Како го правиме тоа? Добро во pseudocode код, може да се каже, ајде постави трампа спротивност со не-нулта вредност. Ќе видиме зошто го правиме тоа во една секунда. А потоа се повторува на следниве процесот до шанкот трампа е 0, или додека ние не правиме никакви свопови на сите. 

Ресетирате трампа спротивни 0 ако тоа не е веќе 0. Потоа да се погледне во секој соседен пар од елементи. Ако овие два елементи се не е во ред, ги трампа, и додадете 1 до шалтер трампа. Ако сте размислување за ова пред да се визуелизира, забележи дека ова ќе се движи пониско ценети елементи од лево и високо ценети елементи на правото, ефикасно да се прави она што ние сакаме да го направи тоа, кој е се движи оние групи на елементите на тој начин. Ајде да се визуелизира како оваа Може да се погледне за користење на нашата низа дека ние се користи за тестирање на овие алгоритми. Имаме несортиран низа овде, повторно, означена со сите елементи да се биде во црвена боја. И јас во собата ми трампа контра на нула вредност. Јас произволно одбрав негативни 1-- тоа не е 0. Ние сакаме да се повтори овој процес до шанкот трампа е 0. Ова е причината зошто јас во собата ми трампа спротивно на некои не-нулта вредност, бидејќи во спротивно на swap противвредност ќе биде 0. Ние дури и не ќе започне процесот на алгоритмот. Значи, повторно, чекорите are-- ресетирате бројачот за размена на 0, а потоа погледнете во секој соседни пар, а ако тие се на ред, ги трампа, и додадете 1 на шалтер трампа. Значи, да се започне овој процес. Така првото нешто што го правиме е ние во собата на шалтер трампа на 0, а потоа и да се свртиме во секој соседен пар. 

Па ние прво почнете да барате во 5 и 2. Гледаме дека тие се надвор од порачате и да можеме да ги трампа. И се додаваат 1 до шанкот трампа. Па сега нашите трампа контра е 1, и 2 и 5 се вклучи. Сега ние се повторува процесот повторно. 

Ние гледаме на следниот соседен пар, 5 и 1-- тие се, исто така, на ред, па ние да ги разменуваат и да додадете 1 до шанкот трампа. Потоа ќе погледнеме во 5 и 3. Тие се на ред, па ние се разменуваат нив и ние додадете 1 до шалтер трампа. Потоа ќе погледнеме во 5 и 6. Тие се во ред, па ние всушност не треба да се разменуваат ништо тоа време. Потоа ќе погледнеме во 6 и 4. Тие се, исто така, на ред, па ние се разменуваат нив и ние додадете 1 до шалтер трампа. 

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

Па сега можеме да се изјасни дека тоа е сортирана, и во иднина iterations-- минува низ низа again-- ние не треба да се разгледа 6 повеќе. Ние само треба да се разгледа на несортиран елементи кога ние сме во потрага на соседните парови. Па ние имаат завршено еден поминат низ меур вид. Па сега ние се вратиме на прашањето, Повторете се додека шалтер трампа е 0. И контра трампа е 4, па ние ќе да ги повторува овој процес повторно. 

Ние ќе треба да го ресетирате бројачот за размена на 0, и се погледне во секој соседен пар. За да можеме да започнат со 2 и 1-- тие се на ред, за да можеме да ги трампа и се додаваат 1 до шанкот трампа. 2 и 3, тие се во ред. Ние не треба да се направи нешто. 3 и 5 се во ред. Ние не треба да се направи нешто таму. 

5 и 4, тие се надвор на ред, и така ние треба да ги разменуваат и да додадете 1 до шанкот трампа. И сега ние се пресели 5, следниот најголемиот елемент, до крајот на несортиран дел. Па сега можеме да го наречеме дека дел од подредени дел. 

Сега сте во потрага по екран и веројатно може да се каже, како може јас, дека низата е сортирана во моментов. Но, ние не може да докаже дека сеуште. Ние немаме гаранција дека тоа се подредени. Но, ова е местото каде што на swap противвредност ќе влезе во игра. 

Значи ние сме завршиле помине. Противвредност трампа е 2. Па ние ќе треба да се повтори овој процес повторно, Повторете се додека шалтер трампа е 0. Ресетирање на бројачите трампа на 0. Па ние ќе го ресетирате. 

Сега гледам на секој соседен пар. Тоа е во ред, 1 и 2. 2 и 3 се во ред. 3 и 4 се во ред. Па во овој момент, известување ќе завршиме гледа во секој соседен пар, но контра своп се уште е 0. 

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

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

Значи она што значи тоа? Значи, што е најлошото сценарио балон за вид, а она што е најдобро сценарио за меур вид? Ми го погоди ова? Во најлош случај ќе мора да iterate во сите n елементи n пати. Па најлош случај е N на квадрат. 

Ако низата е совршено сортирани иако, само мора да се погледне во секој на елементите еднаш. И ако контра своп се уште е 0, може да се каже оваа низа е сортирана. И така во најдобар случај, ова е всушност подобра од селекцијата sort-- тоа е омега на n. 

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