>> МАРК GROZEN-Сміт: Прывітанне, я Марк Grozen-Сміт, і гэта Quicksort.
Гэтак жа, як сартаванне ўстаўкамі і бурбалка сартаваць, хуткай сартавання з'яўляецца алгарытмам
сартаванне спісу або масіў рэчаў.
Для прастаты выкажам здагадку, што тыя, рэчы проста цэлыя лікі, але
ведаем, што хуткая сартаванне работ па больш, чым проста лічбы.
Хуткі старт крыху больш складана чым устаўка або бурбалка, але гэта
таксама значна больш эфектыўным у большасці выпадкаў.
Пачакай секунду.
Ён толькі што сказаў "найбольш выпадкі, "ня" ўсё "?
Цікава, што не.
Не ўсе выпадкі аднолькавыя.
Не хвалюйцеся пра гэта падрабязна, калі вам не бачыў вялікі абазначэння O пакуль няма, але
Хуткая сартаванне з'яўляецца Аб (п квадрат) Алгарытм у горшым выпадку, гэтак жа, як
ўстаўкі або пузырьковый сартавання.
Аднак, як правіла, дзейнічае значна больш як стары аналагавы алгарытму м.
Чаму?
Мы вернемся да гэтага пазней.
Але цяпер, давайце проста даведацца як хуткая сартаванне працуе.
>> Так што давайце ісці праз Quicksorting гэта масіў цэлых ад найменшага
да велічыні.
Тут у нас ёсць цэлыя лікі 6, 5, 1, 3, 8, 4, 7, 9 і 2.
Па-першае, мы выбіраем канчатковы элемент гэты масіў - у гэтым выпадку, два -
і назваць гэта "Стрыжань". Далей, мы пачынаюць глядзець на дзве рэчы -
адзін, самы нізкі паказчык, які я буду называць як заставацца справа ад
сцяна, і, два, самы левы элемент, што я назваў "ток
элемент ". Тое, што мы збіраемся зрабіць, гэта Паглядзець усе іншыя элементы, іншыя
чым стрыжань, і паставіць усе элементы менш, чым павароту да
злева ад сцяны, і ўсе тыя больш, чым павароту да
Права сцяне.
Тады, нарэшце, мы будзем апускаць стрыжань Права на той сцяне, каб пакласці яго паміж
ўсе лікі менш, чым і ўсе лікі больш.
>> Так давайце зробім гэта.
Вазьміце 2, паставіць сцяну на пачынаецца, і выклікаць "бягучы 6
элемент ". Такім чынам, мы хочам паглядзець на наш бягучы элемент, 6.
І так як гэта больш, чым 2, мы пакідаем яго там, каб
Права сцяне.
Затым мы пяройдзем да глядзець на 5, як нашы бягучы элемент і паглядзець, што гэта
, Зноў жа, больш цэнтральнага, таму мы пакінуць яго там, дзе ён знаходзіцца справа
боку сцяны.
Мы ідзем далей.
Наш бягучы элемент зараз 1, і - о.
Цяпер Гэта адрозніваецца.
Бягучы элемент зараз менш, чым стрыжань, таму мы хочам, каб пакласці яго
злева ад сцяны.
Каб зрабіць гэта, давайце проста пераключыцца бягучы элемент з найменшай індэксам
седзячы толькі направа сцяны.
Цяпер мы пераходзім да сцяны да аднаго індэкса так што 1 знаходзіцца злева
бок сцены цяпер.
>> Пачакайце.
Я проста пераблытаў элементы на Правая частка сцяны, ці не так?
Не хвалюйцеся.
Гэта нармальна.
Адзінае, што мы клапоцімся пра зараз з'яўляецца тое, што ўсе гэтыя элементы ў
Права сцяне буйней чым павароту.
Няма рэальны парадак не мяркуецца яшчэ.
>> Цяпер вернемся да сартаванні.
Таму мы працягваем глядзець на Астатнія элементы.
І ў гэтым выпадку, мы бачым, што ёсць ніякія іншыя элементы менш, чым
стрыжань, таму мы пакінем іх усё на правая бок сцяны.
Нарэшце, мы дабіраемся да бягучага элемента і бачу, што з'яўляецца стрыжнем.
Цяпер, што азначае, што ў нас ёсць два раздзелы масіва, першы з якіх
невялікі па восі і на левай баку сцены, а другі
больш, чым павароту да Правая частка сцяны.
Мы хочам пакласці вядучы элемент паміж два, і тады мы будзем ведаць,
што стрыжань знаходзіцца ў сваім праве Канчатковы адсартаваны месца.
Так мы пераходзім першы элемент на Правая частка сцяны з шарнірам,
і мы ведаем, што стрыжань'S у правільным становішчы.
>> Затым мы паўтарыць гэты працэс для подмассивы злева і справа ад восі павароту.
Так як апошняе подмассив толькі адзін элемент даўжынёй, мы ведаем, што ўжо
адсартаваны таму як вы можаце быць з замовіць, калі вы толькі адзін элемент?
Для правага боку подмассива, мы бачыць, што стрыжань знаходзіцца ў 5, і сцяной
толькі злева ад 6.
І бягучы элемент таксама пачынаецца як 6.
Так 6 больш, чым 5.
Мы пакідаем яго там, дзе ён знаходзіцца на Правая частка сцяны.
Цяпер, рухаючыся па 3 менш 5.
Такім чынам, мы ўключыць яго з першым элементам раз з сцяны.
Зараз, я пераехаў у сцяну да аднаго.
Зараз пераходзім да 8.
8 больш, чым 5, і таму мы пакінем яго.
4 менш 5, таму мы ўключыць яго.
А на.
>> Кожны раз, калі мы паўтараем працэс на левая і правая боку масіва. мы
выбраць стрыжань і рабіць параўнання і стварыць яшчэ адзін узровень налева і
правы подмассивы.
Гэта рэкурсіўны выклік будзе працягвацца да мы дасягаем канца, калі мы
дзеліцца на агульную масіў у за ўсё подмассивы даўжыні 1.
Адтуль, мы ведаем, што масіў адсартаваны таму што кожны элемент мае, па меншай
некаторая кропка, быў стрыжань.
Іншымі словамі, для кожнага элемента, усе лічбы злева з'яўляюцца найменшай
каштоўнасці і ўсе лікі да Права мець вялікія значэння.
>> Гэты метад працуе вельмі добра, калі Каштоўнасць павароту абранага з'яўляецца
прыкладна ў сярэдзіне дыяпазон значэнняў спіс.
Гэта азначае, што, пасля таго, як мы рухаемся элементы вакол, каля, як многія
элементы злева ад восі павароту як ёсць направа.
І падзяляй і ўладар характар Алгарытм хуткай сартавання, прымаецца
поўны перавага.
Гэта стварае час працы O (п § п,) п, так што мы павінны зрабіць н мінус 1
параўнання на кожным пакаленні і часопіс н, таму што мы павінны падзяліць спіс
увайсці п раз.
Тым не менш, у горшых выпадках гэта Алгарытм можа быць на самой справе O (п
у квадраце.) Хай на кожным пакаленні, стрыжань проста так здараецца,
маленькі ці самы вялікі з Нумары мы сартавання.
Гэта азначала б, ламаючы спіс п раз і рашэнняў п мінус 1
параўнання кожны раз.
Такім чынам, аб н у квадраце.
>> Як мы можам палепшыць метад?
Адзін добры спосаб палепшыць метад з'яўляецца каб скараціць верагоднасць таго, што
час працы ад батарэй калі-небудзь фактычна аб н у квадраце.
Запомніце гэты горшы, найгоршы сцэнар можа адбыцца толькі, калі
стрыжань выбралі заўсёды самая высокая або нізкае значэнне ў масіве.
Каб забяспечыць гэта наўрад ці адбудзецца, мы можам знайсці кропку апоры на
выбары некалькіх элементаў і прымаючы значэнне медыяны.
>> Мяне завуць Марк Grozen-Сміт, і гэта CS50.
>> Для прастаты выкажам здагадку, што тыя, рэчы проста цэлыя лікі, але
ведаць, што QUICKSERT -
QUICKSERT?
Выбачайце.
>> Тут у нас ёсць цэлыя лікі 6, 5, 1, 3, 8, 4, 9.
>> Выступоўца 1: У самай справе?
>> СПІКЕР 2: Не спыняцца на дасягнутым.
>> Выступоўца 1: У самай справе?