Алгарытмы сартавання як яны ёсць

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

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

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

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

Разгледзім першы варыянт алгарытму сартавання масіва метадам бурбалкі. Слоўны алгарытм сартавання масіва, які мае ідэнтыфікатар mas і які складаецца з N элементаў, выглядае наступным чынам:

1. Змясціць на месца першага элемента (mas [1]) найбольшы элемент масіва. Для гэтага будзем параўноўваць яго па чарзе з усімі астатнімі элементамі (mas [2], mas [3] ... mas [N]). Калі апынецца, што які-небудзь з пакінутых элементаў больш mas [1], то патрабуецца памяняць іх месцамі (праз дадатковую зменную buf).

2. Выключыўшы з разгляду элемент mas [1], паўтарыць пункт 1 для элемента mas [2].

3. Гэтыя дзеянні паўтараць для ўсіх элементаў, акрамя апошняга.

Рэалізацыя алгарытму сартавання бурбалкай на мове праграмавання Паскаль:

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

Прывядзём рэалізацыю гэтага алгарытму сартавання для мовы праграмавання Паскаль:

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