§ 18. Сартаванне аднамернага масіву

18.1. Паняцце сартавання масіву

Сартаваннем называецца працэс упарадкавання паслядоўнасці элементаў па якой-небудзь прымеце.

З сартаваннем вы ўжо сутыкаліся пры рабоце з электроннымі табліцамі. Там можна было ўпарадкаваць лікавыя значэнні ў парадку ўзрастання ці спадання, а радковыя — у алфавітным (ці адваротным алфавітнаму) парадку  (прыклад 18.1).

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

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

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

Часта сярод элементаў паслядоўнасці, якая сартуецца, могуць аказацца роўныя па значэнні элементы. У гэтым выпадку прынята гаварыць пра парадак неспадання (неўзрастання). У агульным выпадку элементы могуць быць не роўныя па значэнні, але лічыцца роўнымі адносна функцыі параўнання  (прыклад 18.2).

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

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

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

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

Ніжэй разглядаюцца метады сартавання лінейнага масіву па ўзрастанні (неспаданні). Сартаванне па спаданні (неўзрастанні) выконваецца аналагічна. Сартаванне з выкарыстаннем функцыі параўнання будзе паказана ў канцы параграфа.

Прыклад 18.1. Сартаванне ў электроннай табліцы.

Па назве краіны, у алфавітным парадку (узрастанне) Па плошчы, у парадку спадання

          

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

Першыя прататыпы сучасных метадаў сартавання з’явіліся ўжо ў XIX ст., калі былі вынайдзены сартавальныя машыны. Першая такая машына была вынайдзена Германам Холерытам (1860—1929). Устройства называлася табулятар, патэнт на яго быў атрыманы ў 1884 г. Затым на працягу пяці гадоў Г. Холерыт запатэнтаваў перфаратар, сартаванне і перфакарту. Табулятар выкарыстоўваўся для апрацоўкі даных перапісу насельніцтва ў ЗША ў 1890 г.

              

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

Створаная Г. Холерытам у 1896 г. фірма Tabulating Machine Company па вытворчасці лічыльна-аналітычных машын з часам злілася з іншымі кампаніямі ў адну, якая з 1924 г. называецца International Business Machines (IBM). Да 1921 г. Холерыт заставаўся кансультантам гэтай фірмы.

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

РРабота сартавальнай машыны Г. Холерыта засноўвалася на метадах паразраднага сартавання.

Іншыя вядомыя метады сартаванняў з'явіліся з развіццём ЭВМ. Па некаторых крыніцах[1], менавіта праграма сартавання стала першай праграмай для вылічальных машын. Некаторыя канструктары ЭВМ, у прыватнасці распрацоўшчыкі EDVAC, называлі задачу сартавання даных найбольш характэрнай нелікавай задачай для вылічальных машын. У 1945 г. Джон фон Нэйман для тэсціравання шэрага каманд для EDVAC распрацаваў праграмы сартавання метадам зліцця. У тым жа годзе нямецкі інжынер Конрад Цузе распрацаваў праграму для сартавання метадам простых уставак.

У 1959 г. быў распрацаваны метад Шэла, у 1962 г. з'явіўся алгарытм хуткага сартавання Хоара. Узнікшыя пазней алгарытмы шмат у чым з'яўляліся варыяцыямі ўжо вядомых метадаў.

Адной з апошніх распрацовак з'яўляецца алгарытм Timsort — гібрыдны алгарытм сартавання, які спалучае сартаванне ўстаўкамі і сартаванне зліццём. Апублікаваны ў 2002 г. Цімам Петэрсам (амерыканскі распрацоўшчык ПЗ, зрабіў вялікі ўклад у мову праграміравання Python). У наш час Timsort з’яўляецца стандартным алгарытмам сартавання ў Python і інш. Асноўная ідэя алгарытму ў тым, што ў рэальным свеце масівы даных, якія сартуюцца, часта змяшчаюць у сабе ўпарадкаваныя падмасівы. На такіх даных Timsort істотна больш хуткі  шмат за якія алгарытмы сартавання



[1] Дональд Е. Кнут. Искусство программирования. Т. 3. Сортировка и поиск. М: ООО «И. Д. Вильямс», 2018. — 832 с.