Сартаванне выбарам

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

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

1. Сартаванне выбарам і іншымі спосабамі ўжываецца вельмі шырока.
2. Яе алгарытм часта выкарыстоўваюць без асаблівай на тое патрэбы.
3. Для вырашэння пастаўленых задач прымяняецца недасканалая мадэль.

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

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

Сартаванне выбарам, пра якую пойдзе гаворка, адносіцца да ўнутранай. Менавіта на ёй трэба спыніцца больш падрабязна, бо такі спосаб апрацоўкі дазваляе выконваць сартаванне больш гнутка і выгадна. Ўсе яе метады дзеляцца на 4 асноўныя групы:

1. Сартаванне ўстаўкамі.
2. Апрацоўка дадзеных падлікам.
3. Абменны працэс.
4. Сартаванне выбарам.

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

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

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