Сартаванне зліццём: апісанне працы алгарытму і адрозненняў ад іншых відаў парадкавання дадзеных

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

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

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

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

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

- пры неабходнасці выкарыстання носьбіта інфармацыі, арыентаванай на паслядоўны доступ;

- калі зручна выкарыстоўваць зменную даўжыню запісаў.

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

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