[Гуляе музыка] 

Даг Lloyd: Так ўстаўкі сартавання іншы Алгарытм можна выкарыстоўваць для сартавання масіва. Ідэя гэтага алгарытму гэта, каб пабудаваць свой адсартаваны масіў ў месцы, пераступаючы элементы з спосаб, як вы ідзяце, каб вызваліць месца. Гэта крыху адрозніваецца ад выбару роду або бурбалкі роду, напрыклад, дзе мы рэгулявання месцазнаходжання, дзе мы робім свопы. 

У гэтым выпадку тое, што мы на самай справе робіце рассоўныя элементы больш, зь шляху. Як гэта алгарытм працаваць у псевдокоде? Ну давайце проста адвольна сказаць, што Першы элемент масіва сартуецца. Мы будуем яе на месцы. 

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

Тады мы будзем паўтараць гэты працэс until-- мы будзем паўтараць наступную працэдуру пакуль усё элементы не сартуюцца. Паглядзіце на наступны малокомплектных элемента і устаўце яго ў адсартаваным часткі, шляхам зруху неабходную колькасць элементаў з шляху. Спадзяюся, гэтая візуалізацыя дапаможа вам убачыць менавіта тое, што адбываецца з ўстаўкі роду. 

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

Затым мы разгледзім на наступным малокомплектных элемент масіва і мы хочам, каб ўставіць, што у частцы Сартаваць, зрушваючы элементы старэй. Так два гэта наступны малокомплектных элемент масіва. Відавочна, ён належыць да пяць, так што мы збіраемся зрабіць з'яўляецца свайго роду правядзе два ў бок на секунду, перакласці пяць над, а затым устаўце два да пяці, дзе павінны ісці. І зараз мы можам сказаць, што два сартуецца. 

Такім чынам, як вы бачыце, мы толькі пакуль паглядзеў на двух элементаў масіва. Мы не глядзелі на адпачынак на ўсіх, але мы атрымаў гэтыя два элемента сартуюцца па Спосаб механізму пераключэння. 

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

Зноў жа, да гэтага часу, мы толькі калі-небудзь паглядзеў на адзін, два і пяць. Мы не ведаем, што яшчэ ідзе, але мы сартуюцца гэтыя тры элемента. 

Наступная малокомплектных элемент тры, так што мы будзем ўсталёўваць яго ў бок. Мы паступова ссоўваць тое, што мы трэба, які, на гэты раз гэта яшчэ не ўсё, як і ў папярэднім два выпадкі, гэта проста пяць. І тады мы будзем прытрымлівацца тры ў, паміж двума і пяццю. 

Шэсць з'яўляецца наступным малокомплектных элемент да масіву. І на самай справе шасці больш пяці, так мы нават не трэба рабіць якія-небудзь замены. Мы можам проста лавіраваць шэсць права на канец адсартаваныя часткі. 

Нарэшце, чатыры з'яўляецца Апошняе малокомплектных элемент. Такім чынам, мы будзем ўсталёўваць яго ў бок, перайсці па элементы, якія мы павінны перанесці на працягу, а затым пакласці чатыры, дзе яна належыць. А цяпер паглядзіце, мы накшталт з усіх элементаў. Звярніце ўвагу, з увядзеннем сартаваць, у нас не было каб ісці наперад і назад праз масіў. Мы толькі пайшлі праз масіў адзін час, і мы перайшлі рэчы што мы ўжо сутыкаліся ў парадак каб вызваліць месца для новых элементаў. 

Так што ў горшым выпадку Сцэнар з ўстаўкі роду? У горшым выпадку, масіў у зваротным парадку. Вы павінны перайсці кожнага з п элементаў да н пазіцый, кожны раз, калі мы зрабіць ўстаўку. Гэта шмат мяняецца. 

У лепшым выпадку, Масіў выдатна адсартаваныя. І накшталт як тое, што адбылося з пяццю і шасцю у прыкладзе, дзе мы маглі б проста лавіраваць яе на без таго, каб зрабіць любы зрух, мы, па сутнасці, што рабіць. 

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

Мы не робім ніякіх свопы, мы проста перасоўванне гэтую адвольную лінію паміж сартуюцца і малокомплектных, як мы ідзем. Як эфектыўна, як мы гэта рабілі ў прыкладзе, паварочваючы элементы сіні, як мы далей. Так што ў горшым выпадку выканання, то? Памятаеце, што калі ў нас ёсць перакласці кожны з рускія элементы, магчыма, N пазіцый, мы спадзяемся, што дае вам ідэя, што ў горшым выпадку выканання з'яўляецца Вялікі Аб п квадраце. 

Калі масіў выдатна сартаваць, усё, што мы павінны зрабіць, гэта паглядзець на кожнага элемента адзін раз, а затым мы зрабілі. Такім чынам, у лепшым выпадку, гэта амега п. 

Я Дуг Лойд. Гэта CS50.