[Гуляе музыка] Даг Lloyd: Сартаваць Выбар з'яўляецца алгарытм, які, як вы маглі б чакаць, сартуе набор элементаў. І алгарытм водгук гэта крок за крокам набор інструкцый для выканання задачы. 

Пры выбары сартаваць Асноўная ідэя гэта, знайсці найменшае малокомплектных элемент і дадаць яго ў канцы адсартаваныя спісу. Эфектыўна, што гэта робіць зборкі адсартаваны спіс, адзін элемент за адзін раз. Парушэнне яго да псевдокоде мы маглі б сцвярджаць, гэты алгарытм як след, не паўтараць гэта, пакуль няма малокомплектных элементы застаюцца. Пошук праз малокомплектных дадзеныя, каб знайсці найменшае значэнне, Затым памяняць найменшае значэнне з Першы элемент неотсортированной часткі. 

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

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

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

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

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

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

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

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

Мы лічым, што гэта пяць найменшы элемент. Мы памяняць яго з першым элемент неотсортированной часткі. А цяпер пяць сартуецца. 

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

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

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

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

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

Вы здагадаліся Big O н квадрат, і Вялікі Амега п квадраце? Вы былі б правы. Тыя, у самай справе, у горшым выпадку і лепшы выпадак выканання раз, для выбару роду. 

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