[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 павінны быць у правільным месцы, так як гэта
Адзіны элемент пакінулі, і гэта выбар роду.
Давайце зараз аформіць наш алгарытм з некаторымі
псевдокод.
На першай лініі, мы бачым, што нам трэба інтэграваць па
кожны элемент спісу.
За выключэннем апошняга элемента, так як 1 элемент
спіс ужо адсартаваны.
На другой лініі, мы разгледзім першы элемент несортированные
Частка спісу, каб быць мінімальным, як мы зрабілі з нашым
Напрыклад, у нас ёсць што-то для параўнання.
Трэцяя радок пачынаецца другі цыкл, у якім мы перабору
кожны несортированные элемент.
Мы ведаем, што пасля таго як я ітэрацый, адсартаваныя часткі
з нашага спісу павінны мець элементы я ў ім з кожным крокам
віды аднаго элемента.
Такім чынам, першы несортированные элемент павінен знаходзіцца ў становішчы я плюс 1.
На чацвёртай радку, мы параўноўваем бягучы элемент да мінімуму
элемент, які мы бачылі да гэтага часу.
Калі бягучы элемент менш, чым мінімальная
элемент, то мы памятаем, бягучы элемент у якасці новай
Мінімум на лініі пяць.
Нарэшце, на лініі шэсць і сем, мы перастаўляць мінімальнай
элемент з першым элементам несортированные, такім чынам,
дадаць яго ў адсартаваным частка спісу.
Як толькі мы атрымаем алгарытм, важнае пытанне
сябе ў якасці праграмістаў як доўга гэта зойме?
Мы спачатку задаць пытанне, колькі часу спатрэбіцца для гэтага
Алгарытм для працы ў горшым выпадку?
Нагадаем, мы ўяўляем гэты ход
Час з вялікай пазначэнне O.
Для таго, каб вызначыць мінімальны несортированные элемент,
па сутнасці было параўнаць кожны элемент у спісе
любы іншы элемент у спісе.
Інтуітыўна, гэта гучыць як O п квадрат аперацыі.
Гледзячы на ​​нашым псевдокоде, мы таксама маем цыкл укладзены ў
іншы цыкл, які сапраўды гучыць як O
п квадрат аперацыі.
Аднак памятайце, што мы не павінны глядзець на
Увесь спіс пры вызначэнні мінімальнага несортированные элемент?
Як толькі мы ведалі, што 4 быў адсартаваны, напрыклад, мы не
трэба глядзець на гэта зноў.
Ці значыць гэта, ніжняя час працы?
Для нашага спісу даўжыня 6, нам трэба было зрабіць пяць
параўнанняў для першага элемента, чатыры параўнанняў для
Другі элемент, і так далей.
Гэта азначае, што агульная колькасць крокаў з'яўляецца сумай
лікамі ад 1 да даўжыні спісу мінус 1.
Мы можам прадставіць гэта з дапамогай сумавання.
Мы не будзем удавацца ў сумах тут.
Але аказваецца, што гэта сумаванне роўная п раз
N мінус 1 па 2.
Або, што эквівалентна, п квадрат больш за 2 мінусу п над 2.
Калі гаворка ідзе пра асімптатычнай выканання, гэта п квадрат тэрмін
будзе дамінаваць у гэтай п тэрмін.
Такім чынам, выбар сартавання O п квадрат.
Нагадаем, што ў нашым прыкладзе, выбар роду ўсё яшчэ маюць патрэбу ў
праверце нумар, які быў ужо адсартаваны
Неабходна перамяшчаць.
Такім чынам, гэта азначае, што калі мы пабеглі выбар роду на ўжо
адсартаваны спіс, гэта запатрабуе столькі ж крокаў, як гэта
бы пры працы над цалкам несортированный спіс.
Такім чынам, выбар роду мае лепшым выпадку выканання п квадратаў,
якія мы ўяўляем з амега N ў квадраце.
І вось менавіта для выбару роду.
Гэта толькі адзін з многіх алгарытмаў можна
выкарыстоўваць для сартавання спісу.
Мяне клічуць Томі, і гэта CS50.