[Powered by Google Translate] TOMMY: Ајде да ги разгледаме во изборот вид, алгоритам
за преземање на листа со броеви и сортирање на нив.
Алгоритам, се сеќавам, е само чекор-по-чекор
постапката за остварување на задачата.
Основната идеја зад селекција вид е да се класификуваат
нашата листа во два дела -
сортирани дел и несортиран дел.
На секој чекор од алгоритмот, голем број се движи од
несортиран дел на подредени дел до крајот на
Целата листа е сортирана.
Значи тука е листа на шест броеви -
23, 42, 4, 16, 8, и 15.
Токму сега целата листа се смета вон едиции.
Иако голем број како 16 веќе може да биде во правилна
локација, нашите алгоритам нема начин да се знае дека до
Целата листа е сортирана.
Па ние ќе се разгледа секој број да се вон едиции додека не се најде
тоа самите себеси.
Ние знаеме дека сакате листата да биде во растечки редослед.
Па ние ќе сакате да се изгради на подредени дел од нашата листа
од лево кон десно, најмалите до најголемите.
Да го направите тоа, ќе треба да се најде на минимум несортиран елемент
и го стави на крајот на подредени дел.
Од оваа листа не е сортирана, единствениот начин да се стори тоа е да
осврнам на секој елемент во несортиран дел, сеќавајќи
кој елемент е најниска и споредување
секој елемент на тоа.
Значи ние прво ќе се погледне на 23.
Ова е прв елемент што сум го видел, па ние ќе се сеќавам
тоа како минимум.
Следна ние ќе се погледне во 42.
42 е поголем од 23, па 23 се уште е на минимум.
Следна е 4, што е помалку од 23, па ние ќе се сеќавам 4
како нов минимум.
Следна е 16, што е поголема од 4, па 4
се уште е на минимум.
8 е поголема од 4 и 15 е поголем од 4, толку 4 мора да биде
најмалиот несортиран елемент.
Па дури и како луѓе што веднаш може да се види дека 4 е
минималните елемент, нашите алгоритам треба да се погледне во
секој несортиран елемент, дури и откако ние Наидовме на 4 -
минимум елемент.
Па сега дека ние Наидовме на минимум елемент, 4, ќе сакате
да ја преместите во решат дел од листата.
Бидејќи ова е првиот чекор, тоа значи дека ние сакаме да се стави 4 на
на почетокот на листата.
Токму сега 23 е на почетокот на листата, па
ајде трампа на 4 и 23.
Така, сега нашата листа изгледа вака.
Ние знаеме дека 4 мора да бидат во завршна локација, затоа што тоа е
и најмалиот елемент и елемент на почетокот
на листата.
Па тоа значи дека ние никогаш не треба да ја преместите повторно.
Значи, да го повторите овој процес за да додадете друг елемент на
подредени дел од листата.
Ние знаеме дека не треба да се погледне на 4, бидејќи тоа е
веќе подредени.
Значи можеме да започне во 42, што ќе се запамети како
минимум елемент.
Значи следниот ние ќе се погледне на 23 што е помалку од 42, па ние
се сеќавам 23 е нов минимум.
Следна ние гледаме на 16 што е помалку од 23, па
16 е нов минимум.
Сега ќе погледнеме во 8 кој е помал од 16, па
8 е новиот минимум.
И конечно 8 е помалку од 15, па знаеме дека 8 е минимум
несортиран елемент.
Па тоа значи дека ние треба да се додаде 8 до подредени
дел од листата.
Токму сега 4 е само подредени елементи, така што сакате да поставите
8 до 4.
Од 42 е првиот елемент во несортиран дел од
листа, ќе сакате да се разменуваат со 42 и 8.
Така, сега нашата листа изгледа вака.
4 и 8 претставуваат подредени дел од листата, и
Останатите броеви претставуваат несортиран
дел од листата.
Значи, да продолжи со друг повторување.
Започнуваме со 23 тоа време, бидејќи ние не треба да се погледне во
4 и 8 повеќе, бидејќи тие го
веќе подредени.
16 е помалку од 23, па ние ќе се сеќавам
16 како нов минимум.
16 е помалку од 42, но 15 е помалку од 16, па 15 мора да биде
минималните несортиран елемент.
Па сега ние сакаме да се разменуваат со 15 и 23 до
ни даде оваа листа.
На подредени дел од Листата се состои од 4, 8 и 15, и
овие елементи се уште се вон едиции.
Но, тоа само така се случува, дека следната несортиран елемент, 16,
веќе подредени.
Сепак, не постои начин за нашите алгоритам да се знае дека 16
е веќе во неговата точна локација, па ние сеуште треба да
повтори точно истиот процес.
Така можеме да видиме дека 16 е помал од 42, и 16 е помал од 23, па
16 мора да биде минимум елемент.
Тоа е невозможно да се разменуваат овој елемент со себе, за да можеме да
едноставно, оставете го на оваа локација.
Значи ние треба уште еден премин на нашите алгоритам.
42 е поголем од 23, па 23 мора да биде
минимум несортиран елемент.
Откако ќе трампа на 23 и 42, ќе се заокружи со нашата конечна
Подредена листа -
4, 8, 15, 16, 23, 42.
Знаеме 42 мора да биде во правилната место, бидејќи тоа е
само елемент лево, и тоа е избор вид.
Ајде сега формализираат нашите алгоритам со некои
pseudocode.
На линија еден, можеме да видиме дека ние треба да се интегрираат во текот
секој елемент од листата.
Освен последниот елемент, бидејќи 1 елемент
Листата е веќе сортирана.
На линија два, сметаме дека првиот елемент на несортиран
дел од листата за да биде минимум, како што направивме со нашите
пример, па ние имаме нешто да се споредуваат со.
Линија три започнува вториот циклус во кој ние iterate во текот
секој несортиран елемент.
Ние знаеме дека откако повторувања, на подредени дел
на нашата листа мора i елементи во него, бидејќи секој чекор
видови еден елемент.
Така, првиот несортиран елемент мора да биде во позиција i плус 1.
On-line четири, ние споредуваат тековниот елемент на минимум
елемент што сум го видел досега.
Ако тековната елемент е помал од минималниот
елемент, тогаш се сеќавам на тековниот елемент како нов
минимум на линија пет.
Конечно, на линии шест и седум, ние трампа на минимум
елемент со првиот несортиран елемент, а со тоа
додавајќи дека на подредени дел од листата.
Откако ќе имаат алгоритам, важно прашање да прашам
себеси како програмери се колку долго не дека се?
Ние прво ќе се постави прашањето колку долго е потребно за оваа
алгоритам да се кандидира во најлош случај?
Сеќавам ние ги претставуваме оваа трка
време со голем О нотација.
Со цел да се утврди минималната несортиран елемент, ние
суштина беше да се споредат секој елемент од листата за да
секој друг елемент во листата.
Интуитивно, ова звучи како О од n квадрат операција.
Гледајќи нашата pseudocode, ние исто така имаат јамка вгнездени внатре
друга телефонска линија, која навистина звучи како О
од n квадрат операција.
Сепак, запомнете дека ние не треба да се погледне во текот на
целата листа при утврдување на минимална несортиран елемент?
Откако знаевме дека 4 е сортирана, на пример, ние не
треба да се погледне во тоа повторно.
Така значи ова пониски трчање време?
За нашата листа на должина 6, ние потребни за да се направи пет
споредби за прв елемент, четири споредби за
вториот елемент, и така натаму.
Тоа значи дека вкупниот број на чекори е збир на
на броеви од 1 до должината на листата минус 1.
Ние може да претставуваат со збир.
Ние не ќе одат во summations тука.
Но излегува дека овој збир е еднаков на n пати
n минус 1 повеќе од 2.
Или еквивалентно, n квадрат над 2 минус n над 2.
Кога зборуваме за асимптотска траење, овој n квадрат рок
ќе доминираат овој n рок.
Значи селекција вид е о од n квадрат.
Потсетиме дека во нашиот пример, селекција вид се уште се потребни за да
проверете дали бројот што веќе сортирана
потребни за да се помести.
Па тоа значи дека ако ние трчаше селекција вид преку веќе
Подредена листа, тоа ќе бара ист број на чекори како што
би, кога работи во текот на еден сосема вон листа.
Значи селекција вид има најдобар случај перформанси од n квадрат,
кои ние ги претставуваме со омега n квадрат.
И тоа е тоа за избор вид.
Само еден од многуте алгоритми што можеме
користат за сортирање на листата.
Моето име е Томи, и ова е cs50.