Папулярныя метады групоўкі элементаў масіва: сартаванне ўстаўкамі і з дапамогай ключа

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

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

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

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

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

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

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