Хуткая сартаванне як метад праграмавання

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

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

Хуткая сартаванне вельмі распаўсюджана, яе можна сустрэць усюды. На яе аснове рэалізаваны метад TList.Sort, які існуе ва ўсіх версіях (за выключэннем 1) Delphi, функцыя бібліятэкі часу, выдаткаванага на выкананне, qsort ў C ++.

Асноўны прынцып працы можна сфармуляваць як "падзяляй і ўладар". Адбываецца разбітыя спісу на дзве групы і сартаванне выконваецца для кожнай часткі сама па сабе. Адсюль вынікае, што большая ўвага патрабуецца надаваць працэсу падзелу, падчас якога адбываецца наступнае: вызначаецца базавы элемент і ўжо адносна яго перастаўляецца ўвесь спіс. Лявей выбудоўваецца група кандыдатаў, значэння якіх менш, правей пераносяцца ўсе іншыя. Атрымліваецца, што асноўны элемент у адсартаваным спісе размешчаны на сваім законным месцы. Далейшы этап - гэта выклік рэкурсыўнай функцыі сартавання для абодвух бакоў элементаў адносна базавага. Заканчваецца працэс працы толькі тады, калі спіс будзе ўтрымліваць толькі адзін элемент, гэта значыць будзе адсартаваныя. Такім чынам, каб асвоіць такую функцыю праграмавання, як хуткая сартаванне, трэба ведаць працу алгарытмаў ніжэйшага ўзроўню: а) выбар базавага элемента; б) найбольш эфектыўная перастаноўка спісу для атрымання двух набораў з меншымі і вялікімі значэннямі.

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

Пасля таго, як з выбарам вызначыліся, можна пераходзіць да працы алгарытму разбіцця. Гэта так званыя ўнутраныя цыклы хуткай сартавання. Усё будуецца на двух быстроработающих азначніках: першы пойдзе па элементах злева направа, другі, наадварот, справа налева. Пачынаецца аперацыя выканання справа: індэкс ідзе па спісе і параўноўвае ўсе значэння з асноўным. Цыкл лічыцца завершаным, калі знаходзіцца элемент меншы або роўны базаваму. Гэта значыць адбываецца параўнанне і памяншаецца значэнне індэкса. З левага боку праца скончана пры знаходжанні большага ці роўнага значэння. І тут значэнне пры параўнанні павялічваецца.

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