[Powered by Google Translate] [Устаўка Сартаванне] [Tommy MacWilliam] [Гарвардскі універсітэт] [Гэта CS50.TV] Давайце зірнем на сартаванне ўстаўкамі, алгарытм прыняцця спіс лікаў і сартаванне іх. Алгарытм, памятаеце, гэта проста крок за крокам працэдуры для выканання задачы. Асноўная ідэя сартавання устаўкай, складаецца ў падзеле нашага спісу на дзве часткі, Сартаваць часткі і несортированные частку. 

На кожным кроку алгарытму, ліку перамяшчаецца ад несортированные часткі да адсартаваныя частка пакуль у рэшце рэшт ўвесь спіс будзе адсартаваны. Вось спіс з шасці несортированные нумары - 23, 42, 4, 16, 8 і 15. Паколькі гэтыя лічбы не ўсё ў парадку, яны адсартаваныя. Так як мы яшчэ не пачалі сартавання тым не менш, мы будзем разглядаць усе шасці элементаў нашых несортированные частку. 

Як толькі мы пачынаем сартаванне, мы змесцім гэтыя спарадкаваныя нумары злева ад іх. Такім чынам, давайце пачнем з 23, першы элемент у нашым спісе. У нас няма ніякіх элементаў у нашых сартуюцца частка ўсё ж, так што давайце проста разгледзім 23, каб быць у пачатку і канцы нашага адсартаваныя частку. Цяпер нашы адсартаваныя частка мае адно лік, 23, і нашы несортированные частка мае гэтыя пяць лікаў. Давайце зараз ўставіць наступны нумар у нашым несортированные частка, 42, у адсартаваныя частку. 

Каб зрабіць гэта, нам трэба параўнаць з 42 да 23 - адзіны элемент у нашых сартуюцца частка да гэтага часу. Сорак два больш, чым 23, таму мы можам проста дадаць 42 да канца з адсартаваных частка спісу. Выдатна! Цяпер нашы адсартаваныя частка складаецца з двух элементаў, і нашы несортированные частка складаецца з чатырох элементаў. Такім чынам, давайце пяройдзем да 4, то наступны элемент у несортированный частку. Так, дзе гэта павінна быць змешчана ў адсартаваныя частка? 

Памятаеце, мы хочам змясціць гэты лік у пэўным парадку такім чынам, нашы адсартаваныя частка застаецца правільна адсартаваны ва ўсе часы. Калі мы змесцім 4 направа з 42, то наш спіс будзе ў парадку. Такім чынам, давайце працягваць рухацца справа-злева ў наш род частку. Паколькі мы рухаемся, давайце перакласці кожны нумар ўніз месца, каб вызваліць месца для новага нумара. Добра, 4 таксама менш, чым 23, таму мы не можам змясціць яго і тут. Давайце пяройдзем на 23 правую адным месцы. 

Гэта азначае, што мы хацелі б размясціць 4 у першы слот ў адсартаваныя часткі. Звярніце ўвагу, як гэта месца ў спісе было ўжо пуста, таму што мы рухаліся адсартаваныя элементы ўніз, як мы сутыкнуліся з імі. Добра. Такім чынам, мы ўжо на паўдарозе. Давайце працягнем наш алгарытм, уставіўшы 16 ст адсартаваныя частку. Шаснаццаць менш, чым 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. 

Такім чынам, вось дзе мы хочам, каб наша канчатковая ўстаўкі. І мы зрабілі. У нас больш няма элементаў у несортированный частка, і нашы адсартаваныя частка знаходзіцца ў правільным парадку. Нумары ўпарадкаваны ад найменшага да найбольшага. Такім чынам, давайце зірнем на некаторыя псевдокод, які апісвае крокі, якія мы толькі што выканалі. 

У радку 1, мы бачым, што нам трэба для перабору кожнага элемента ў спісе акрамя першай, так як першы элемент у несортированный частка проста стануць Першы элемент у адсартаваныя часткі. У радках 2 i 3, мы адсочваем наша цяперашняе месца ў несортированный частку. Элемент уяўляе сабой лік мы ў цяперашні час рухаецца ў адсартаваныя частка, і J ўяўляе наш індэкс ў несортированный частку. 

У радку 4 мы перабору адсартаваныя частка справа налева. Мы хочам спыніць ітэрацыю раз элемент злева ад нашай бягучай пазіцыі менш, чым элемент, які мы спрабуем ўставіць. У радку 5 мы перакладаючы кожны элемент мы сутыкаемся адной прасторы з правага боку. Такім чынам, мы будзем мець свабодную прастору для ўстаўкі ў калі мы знаходзім першы элемент менш, чым элемент мы рухаемся. У радку 6, мы абнаўляем лічыльнік працягваць рухацца налева праз адсартаваныя частку. Нарэшце, у радку 7, мы ўстаўка элемента ў адсартаваны частка спісу. 

Мы ведаем, што гэта нармальна для ўстаўкі ў пазіцыю J, таму што мы ўжо пераехалі элемент, які выкарыстоўваецца, каб быць там адно месца направа. Памятаеце, што мы рухаемся праз адсартаваныя частка справа налева, але мы рухаемся праз несортированные частка злева направа. Добра. Давайце цяпер зірнем на тое, як доўга працуе, што алгарытм ўзяў. Мы спачатку задаць пытанне, колькі часу спатрэбіцца для гэтага алгарытму для працы ў горшым выпадку. Нагадаем, што мы ўяўляем гэты час працы з вялікай пазначэнне O. Для таго, каб разабрацца наш спіс, мы былі для перабору элементаў у несортированный частка, і для кожнага з гэтых элементаў, патэнцыйна над усімі элементамі ў адсартаваныя часткі. Інтуітыўна, гэта гучыць як O (N ^ 2) аперацый. 

Гледзячы на ​​нашым псевдокоде, у нас ёсць цыкл ўкладзены ў іншай цыкл, які, сапраўды, гучыць як O (N ^ 2) аперацый. Тым не менш, адсартаваныя частка спісу не ўтрымліваюць ўвесь спіс да самага канца. Тым не менш, мы патэнцыйна маглі б ўставіць новы элемент у самым пачатку Сартаваць частка на кожнай ітэрацыі алгарытму, Гэта азначае, што мы павінны глядзець на кожны элемент у цяперашні час у адсартаваныя часткі. Такім чынам, гэта азначае, што мы патэнцыйна маглі б зрабіць адно параўнанне для другога элемента, 2 параўнання для трэцяга элемента, і гэтак далей. Такім чынам, агульная колькасць крокаў з'яўляецца сума лікаў ад 1 да даўжыні спісу мінус 1. Мы можам прадставіць гэта з дапамогай сумавання. 

Мы не будзем удавацца ў сумах тут, але аказваецца, што гэта сумаванне роўна (П - 1) больш за 2, што эквівалентна п ^ 2/2 - п / 2. Калі гаворка ідзе пра асімптатычнай выканання, гэта п ^ 2 тэрміну будзе дамінаваць у гэтай п тэрмін. Такім чынам, уключэнне сартавання Big O (N ^ 2). Што, калі мы пабеглі сартавання устаўкай ва ўжо адсартаваны спіс. У гэтым выпадку, мы б проста стварыць адсартаваны частка злева направа. Такім чынам, мы будзем толькі трэба парадку п крокаў. 

Гэта азначае, што сартаванне устаўкай мае лепшым выпадку выканання п, якія мы ўяўляем з Ω (N). І вось менавіта для сартавання устаўкай, толькі адна з многіх алгарытмаў можна выкарыстоўваць для сартавання спісу. Мяне клічуць Томі, і гэта CS50. [CS50.TV] О, вы проста не можаце спыніцца, што як толькі ён пачынаецца. Так, мы зрабілі гэта - >> Boom!