Печатать книгуПечатать книгу

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

Сайт: Профильное обучение
Курс: Інфарматыка. 10 клас (Павышаны ўзровень)
Книга: § 18. Сартаванне аднамернага масіву
Напечатано:: Гость
Дата: Понедельник, 29 Апрель 2024, 11:59

Оглавление

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 с.

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

Давайце ўявім, што перад намі пастаўлена задача расставіць N лікаў па ўзрастанні. Як бы мы яе рашалі?

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

Разгледзім работу дадзенага метаду на масіве a = {9, 6, 0, 2, 7, 3, 1, 5}. Мінімальны элемент на кожным кроку падкрэслены (прыклад 18.4). Колерам вылучаны той элемент, які на бягучым кроку мяняецца месцамі з мінімальным.

Ужыты метад называецца сартаванне выбарам. Назва метаду вызначаецца тым, што на кожным кроку мы знаходзім (выбіраем) мінімальны элемент з яшчэ неадсартаванай часткі масіву (прыклад 18.5).

Фармальнае апісанне алгарытму. На i-м кроку (i = 0, …, n - 1) выконваем:

  1. Выбіраем з элементаў з індэксамі ад i да n–1 мінімальны.
  2. Мяняем месцамі знойдзены мінімальны элемент і элемент a[i]. На i-м месцы аказваецца мінімальны элемент з яшчэ неадсартаванай часткі масіву.
  3. Пасля выканання апошняга кроку ў пазіцыі a[n–1] будзе знаходзіцца самы вялікі элемент масіву.

Палічым колькасць параўнанняў, якія прыйшлося зрабіць для ўпарадкавання масіву. На першым кроку для знаходжання максімальнага элемента неабходна (n – 1) параўнанняў, на другім — (n – 2), на трэцім (n – 3), ..., на апошнім кроку — адно параўнанне. Знойдзем суму: n – 1 + n – 2 + n – 3  ... + 1 = fraction numerator straight n open parentheses straight n space minus space 1 close parentheses over denominator 2 end fraction space equals space fraction numerator straight n squared space minus space straight n over denominator 2 end fraction. Або, іншымі словамі, каля n2 аперацый[1].

Колькасць перастановак элементаў роўна (n – 1). Гэта колькасць выконваецца знешнім цыклам  for.

[1] Больш падрабязна пра  колькасць аперацый, неабходныых для выканання алгарытмаў, гл. у § 23.

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

Прыклад 18.4. Сартаванне масіву метадам выбару:

Прыклад 18.5. Праграма алгарытму сартавання метадам выбару:

#include <iostream>

#include <vector>

#include <cstdlib>

#include <ctime>

 

using namespace std;

 

int main()

{

  srand(time(NULL));

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  cout << "chisla:" << endl;

  for (int i = 0; i < n; i++){

    a[i] = rand() % 100;

    cout << a[i] << " ";

  }

  cout << endl << "sort" << endl;

  for (int k = 0; k < n - 1; k++){

    int nmin = k;

    for (int i = k + 1; i < n; i++)

      if (a[i] < a[nmin])

       nmin = i;

    swap(a[k], a[nmin]);

  }

  for (int i = 0; i < n; i++)

    cout << a[i] << " ";

  cout << endl;

  return 0;

}

Тэсціраванне.

Унутраны цыкл for з’яўляецца не чым іншым, як алгарытмам пошуку мінімальнага элемента сярод элементаў з нумарамі ад k + 1 да n – 1.

Суму колькасці параўнанняў можна атрымаць зыходзячы з таго, што лікі n – 1, n – 2, … 1 утвараюць арыфметычную прагрэсію. Сума элементаў гэтай арыфметычнай прагрэсіі роўна  begin mathsize 16px style fraction numerator n open parentheses n space – space 1 close parentheses over denominator 2 end fraction. end style

18.3. Сартаванне абменам

Разгледзім яшчэ адзін метад сартавання, які называецца сартаванне абменам. Назва метаду вызначаецца тым, што алгарытм засноўваецца на абмене месцамі двух элементаў масіву. Мяняюцца месцамі тыя два суседнія элементы ў масіве, якія стаяць «не ў парадку».

Разгледзім яго на прыкладзе таго ж масіву a = {9, 6 0, 2, 7, 3, 1, 5} (прыклад 18.6). Колерам вылучаны той элемент, правей за які праглядаць масіў няма неабходнасці, паколькі элементы, якія стаяць там, ужо адсартаваны.

Фармальнае апісанне алгарытму. На i-м кроку (i = 1, …, n – 1) выконваем:

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

2. Затым параўноўваем другі і трэці, трэці і чацвёрты, ..., i и i + 1, пры неабходнасці мяняючы іх месцамі.

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

Фрагмент праграмы, які змяшчае алгарытм сартавання абменам, прыведзены ў прыклад 18.7.

Лік параўнанняў у дадзеным алгарытме, як і ў алгарытме сартавання выбарам, роўны fraction numerator straight n left parenthesis straight n space – space 1 right parenthesis over denominator 2 end fraction.

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

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

Калі прааналізаваць сартаванне абменам, то можна заўважыць, што самы маленькі лік займае сваё месца за адзін праход па масіве, а самы вялікі перамяшчаецца ў напрамку да свайго месца на адну пазіцыю пры кожным праходзе. Гэта наводзіць на думку чаргаваць напрамак праходаў. Такое сартаванне называецца шэйкер-сартаваннем (шэйкернае сартаванне, сартаванне перамешваннем, кактэйльнае сартаванне). Разгледзім яго работу на тым жа масіве  а = {9, 6 0, 2, 7, 3, 1, 5} (прыклад 18.9, 18.10).

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

Прыклад 18.6. Сартаванне масіву метадам абмену:

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

Замест узняцця самага «лёгкага» элемента можна «тапіць» самы «цяжкі». У гэтым выпадку элементы праглядаюцца спачатку (як у прыкладзе 18.6).

Прыклад 18.7. Фрагмент праграмы сартавання метадам абмену. Увод і вывад такі, як у прыкладзе 18.5.

for (int k = 1; k < n; k++)

  for (int i = 0; i < n-k; i++)

    if (a[i] > a[i + 1])

      swap(a[i], a[i + 1]);

Тэсціраванне.

Прыклад 18.8. Фрагмент праграмы сартавання метадам абмену са спыненнем  пасля таго, калі абмены больш не адбываюцца.

bool p;

int k = n - 1;

do {

  p = false;

  int r = k;

  for (int i = 0; i < r; i++)

    if (a[i] > a[i + 1]){

      swap(a[i], a[i + 1]);

      p = true;

      k = i;

    }

}

while (p);

У прыведзеным фрагменце пераменная p лагічнага тыпу выкарыстоўваецца для вызначэння, былі перастаноўкі ці не, а пераменная k — для захоўвання індэкса апошняга абмену. Пераменная r з’яўляецца мяжой, на якой заканчваецца прагляд.

Прыклад 18.9. Сартаванне масіву шэйкерным сартаваннем (l — левая мяжа прагляду, r — правая):

           

Прыклад 18.10. Фрагмент праграмы шэйкер-сартавання.

bool p;

int j = 0, k = n - 1;

do {

  p = false;

  int r = k;

  for (int i = j; i < r; i++)

    if (a[i] > a[i + 1]){

      swap(a[i], a[i + 1]);

      p = true;

      k = i;

     }

  int l = j;

  for (int i = r - 1; i > l; i--)

    if (a[i - 1] > a[i]){

      swap (a[i - 1], a[i]);

      p = true;

      j = i;

  }

}

while (p);

18.4. Сартаванне простымі ўстаўкамі

Будзем праглядаць элементы масіву a, пачынаючы з другога. Кожны новы элемент a[i] будзем устаўляць на прыдатнае месца ва ўжо ўпарадкаваную частку масіву a[1], ..., a[i–1]. Месца ўстаўкі вызначаецца шляхам параўнання элемента a[i] з упарадкаванымі элементамі a[1], ..., a[i–1].

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

Разгледзім яе работу на масіве а = {9, 6 0, 2, 7, 3, 1, 5} (прыклад 18.11). Колерам вылучаны элементы ўжо адсартаванай часткі.

Формальное описание алгоритма. На i-м шаге (i = 1, …, n – 1) выполняем:

  1.  Бяром першы элемент у неадсартаванай частцы масіву.
  2.  Паслядоўна параўноўваем яго з элементамі ў адсартаванай частцы да таго часу, пакуль не вызначым месца для ўстаўкі.
  3.  Зрушваем элементы ўправа на адзін, вызваляючы месца для ўстаўкі.

Фрагмент праграмы, які змяшчае алгарытм сартавання простымі ўстаўкамі, прыведзены ў  прыклад 18.12.

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

Прыклад 18.11. Сартаванне масіву метадам простых уставак:

Прыклад 18.12. Фрагмент праграмы сартавання простымі ўстаўкамі.

for (int k = 1; k < n; k++) {

  int i = k;

  while (i > 0 && a[i - 1] > a[i]){

    swap(a[i - 1], a[i]);

    i--;

  }

}

У 2000 г. у навуковым выданні Newsletter універсітэта Глазга быў апублікаваны алгарытм пад назвай «Недарэчнае сартаванне»[1]. Аўтар — Хамід Сарбазі-Асад (Hamid Sarbazi-Azad). Крыху пазней галандскі вучоны Дзік Грун (Dick Grune) даследаваў метад падрабязней і пераназваў яго ў «гномава сартаванне». Пад гэтым імем алгарытм цяпер і вядомы. «Гномава сартаванне» заснавана на тэхніцы, якая выкарыстоўваецца звычайным галандскім садовым гномам (нідэрл. tuinkabouter). Гэта метад, якім садовы гном сартуе лінію кветкавых гаршкоў. Па сутнасці, ён глядзіць на наступны і папярэдні садовыя гаршкі: калі яны ў правільным парадку, ён ідзе на адзін гаршчок наперад, інакш мяняе іх месцамі і ідзе на адзін гаршчок назад. Гранічныя ўмовы: калі няма папярэдняга гаршка, ён  ідзе наперад; калі няма наступнага гаршка, ён скончыў.

Прыклад 18.13. Фрагмент праграмы «гномавага сартавання».

while (i < n) {

  if (i == 0 || a[i - 1] <= a[i])

    i++;

  else {

    swap (a[i], a[i-1]);

    i--;

  }

}

[1] Недарэчным сартаваннем звычайна  называюць іншы алгарытм: http://algolab.valemak.com/stupid.

18.5 . Хуткае сартаванне

Разгледзім яшчэ адзін алгарытм сартавання, які з’яўляецца істотным паляпшэннем алгарытму сартавання абменам. Сартаванне абменам з’яўляецца адным з самых неэфектыўных алгарытмаў сартавання. Аднак удасканалены алгарытм дазваляе атрымаць вынік нашмат хутчэй, таму яго вынаходнік Чарльз Хоар назваў гэты алгарытм хуткім сартаваннем (quicksort). Высокая прадукцыйнасць дасягаецца за кошт таго, што адбываецца абмен элементаў на вялікіх адлегласцях.

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

    • не адсартаваныя элементы злева ад апорнага элемента;
    • не адсартаваныя элементы справа ад апорнага элемента.

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

Разгледзім яе работу на тым жа масіве а = {9, 6 0, 2, 7, 3, 1, 5} (прыклад 18.14).

Фармальнае апісанне алгарытму:

  1. Завядзём два паказальнікі: левы і правы, якія дазволяць перамяшчацца па элементах масіву з пачатку і з канца.
  2.  У якасці апорнага элемента выберам элемент, які стаіць на сярэднім месцы.
  3.  Злева ад апорнага элемента знойдзем не меншы, а справа — не большы, чым апорны, і памяняем іх месцамі.
  4.  Абмен элементаў выконваем, пакуль паказальнік з левай часткі не стане большым за паказальнік з правай часткі.
  5.  Рэкурсіўна апрацоўваем 2 часткі масіву: ад пачатку да значэння правага паказальніка і ад значэння левага паказальніка да канца

Рэкурсіўная функцыя хуткага сартавання прыведзена ў прыкладзе 18.15.

У горшым выпадку алгарытм патрабуе каля n2 аперацый параўнання і столькі ж перастановак элементаў у масіве. Аднак такія выпадкі сустракаюцца нячаста (прыклад 18.16). У сярэднім, калі пры кожным рэкурсіўным выкліку масіў дзеліцца на дзве амаль роўныя часткі, то колькасць патрэбных аперацый будзе парадку nk, дзе значэнне k вызначаецца з роўнасці 2k = n. Значэнне k таксама вызначае памер дадатковай памяці для захоўвання стэка рэкурсіўных выклікаў.

Прыклад 18.14. Хуткае сартаванне. Першы праход па масіве.

Пераменныя i і j — індэксы элементаў, якія падлягаюць абмену. Спачатку i = l = 0, j = r = 7 (пераменныяl і r — левая і правая межы апрацоўваемай часткі масіву). У канцы i = 3, j = 2 (i > j), таму абмены больш не выконваюцца. Далей функцыя працуе на падмасівах з межамі [0, 2] і [3,7].

Далейшыя этапы работы алгарытму:

   

Прыклад 18.15. Функцыя хуткага сартавання.

void quicksort(vector <int> &d, int l, int r) {

  int pivot = d[(l + r) / 2];

  int i = l, j = r;

  while (i <= j) {

    while (d[i] < pivot)

      i++;

    while (d[j] > pivot)

      j--;

    if (i <= j) {

      swap (d[i], d[j]);

      i++;

      j--;

    }

  }

  if (l < j)

    quicksort(d, l, j);

  if (i < r)

    quicksort(d, i, r);

}

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

Прыклад 18.16. Прыклады сітуацый, калі хуткае сартаванне не эфектыўнае:

  • калі яно ўжываецца для сартавання ўжо адсартаваных масіваў;
  • калі пасля абменаў атрымліваецца, што адзін з падмасіваў для новага рэкурсіўнага выкліку складаецца з аднаго элемента, а іншы — з n – 1 элемента;
  • калі колькасць элементаў малая (n < 32).

Рэкурсіўныя выклікі з’яўляюцца затратнымі аперацыямі, і для невялікіх масіваў іх колькасць будзе блізай да колькасці элементаў. Таму ў выпадку невялікіх аб’ёмаў даных  выкарыстоўваюць нерэкурсіўныя метады сартавання, напрыклад сартаванне ўстаўкамі ці выбарам.

*У матэматыцы для вызначэння ліку  k(2k = n) карыстаюцца функцыяй  log[2]. Алгарытм хуткага сартавання ў сярэднім выкарыстоўвае каля nlogn  параўнанняў і абменаў[3], а таксама каля logn  дадатковай памяці.

[1] Медыянай трох розных значэнняў будзе тое, якое  не роўна ні мінімальнаму, ні максімальнаму. Напрыклад, для значэнняў 3, 100 і 25 медыянай будзе 25.

[2] Калі 2k = n, то log2n = k.

[3] Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн., 3-е издание. — М.: «Вильямс», 2013. 

18.6. Выкарыстанне функцыі параўнання

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

Функцыю для параўнання двух аб’ектаў называюць кампаратарам (ад англ. compare — параўнаць).

Функцыя-кампаратар залежыць ад двух параметраў і вяртае лагічнае значэнне. Тып параметраў функцыі павінен супадаць з тыпам элементаў у масіве. Функцыя павінна вяртаць значэнне true для двух значэнняў, якія знаходзяцца «ў парадку», і false ў адваротным выпадку.

Прыклад 18.17. Дадзены лінейны масіў з цэлых лікаў. Напісаць праграму сартавання масіву так, каб усе цотныя лікі стаялі ў пачатку масіву, а няцотныя — у канцы. Даныя згенерыраваць выпадковым чынам.

Этапы выканання задання

I. Зыходныя даныя: пераменныя n — колькасць лікаў у масіве, a — масіў.

II.  Вынік: адсартаваны масіў а.

III. Алгарытм рашэння задачы.

  1. Увод зыходных даных. Элементы масіву згенерыраваны выпадковым чынам.
  2. Для рашэння задачы будзем выкарыстоўваць алгарытм сартавання абменам.
  3. Створым кампаратар (функцыю параўнання), якая будзе параўноўваць лікі па астачах ад дзялення на 2.
  4. Будзем мяняць элементы месцамі, калі яны размешчаны «не ў парадку».
  5. Вывад выніку.

IV. Апісанне пераменных: n – int, a –  vector<int>.

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

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

Прыклад 18.19. Дадзены лінейны масіў са слоў. Напісаць праграму сартавання масіву так, каб словы размяшчаліся ў парадку спадання колькасці літар «а» ў слове. Даныя прачытаць з файла.

Этапы выканання задання

I. Зыходныя даныя: пераменныя n — колькасць слоў у масіве, a — масіў.

II. Вынік: адсартаваны масіў  а.

III. Алгарытм рашэння задачы.

  1. Увод зыходных даных.
  2. Для рашэння задачы будзем выкарыстоўваць алгарытм сартавання выбарам.
  3. Створым кампаратар (функцыю параўнання), які будзе параўноўваць словы па колькасці літар «а» ў слове.
  4. Таксама створым функцыю, якая будзе вызначаць колькасць літар «а» ў слове.
  5. Вывад выніку.

IV. Апісанне пераменных: n – int, a –  vector<string>.

Прыклад 18.20. У тэкставым файле input.txt захоўваецца інфармацыя пра студэнтаў. Для кожнага студэнта паказаны яго прозвішча, горад, з якога ён прыехаў, і тры лікі — балы за ЦТ, з якімі ён паступіў у ВНУ. Адсартаваць спіс студэнтаў у парадку спадання сумарнага бала за ЦТ. Вывесці прозвішча, горад і сумарны бал.

Этапы выканання задання

 I. Зыходныя даныя: пераменныя n — колькасць запісаў пра студэнтаў, a — масіў структур.

 II. Вынік: адсартаваны масіў а.

III. Алгарытм рашэння задачы.

  1. Увод зыходных даных.
  2. У апісанні структуры, акрамя палёў, паказаных ва ўмове задачы, дабавім поле «сума», у якой запішам сумарны бал (апісанне структуры было разабрана ў прыкладзе 17.8).
  3. Для рашэння задачы будзем выкарыстоўваць алгарытм сартавання простымі ўстаўкамі.
  4. Створым кампаратар (функцыю параўнання), якая будзе параўноўваць дзве структуры па полі сумы балаў.
  5. Вывад выніку.
IV. Апісанне пераменных:: n – int, a –  vector<student>.

Кампаратар — гэта адносіны парадку. Як функцыя ён павінен задавальняць аксіёмы адносінаў парадку:

  • функцыя з’яўляецца дэтэрмінаванай: comp(a,b) для канкрэтных a і b заўсёды вяртае адзін і той жа вынік;
  • функцыя валодае ўласцівасцю транзітыўнасці: comp(a,b) && comp(b,c) абазначае тое ж самае, што comp(a,c) (у самым простым выпадку, калі a < b і b < c, то a < c);
  • функцыя валодае ўласцівасцю антысіметрычнасці: omp(a,b) &&  comp(b,a) абазначае, што а = b.

Прыклад 18.17.

V. Праграма:

#include <iostream>

#include <vector>

#include <cstdlib>

#include <ctime>

 

bool comp(int x, int y)

{

  return (x % 2 < y % 2);

}

 

using namespace std;

 

int main()

{

  srand(time(NULL));

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  cout << "chisla:" << endl;

  for (int i = 0; i < n; i++){

    a[i] = rand() % 100;

    cout << a[i] << " ";

  }

  cout << endl << "sort" << endl;

  for (int k = 1; k < n; k++)

    for (int i = 0; i < n - k; i++)

      if (!comp(a[i], a[i + 1]))

       swap(a[i], a[i + 1]);

  for (int i = 0; i < n; i++)

    cout << a[i] << " ";

  cout << endl;

  return 0;

}

VI. Тэсціраванне.

Прыклад 18.18. Фрагмент праграмы:

int i = 0, j = n - 1;

while (i <= j) {

  while (a[i] % 2 == 0)

    i++;

  while (a[j] % 2)

    j--;

  if (i <= j) {

    swap (a[i], a[j]);

    i++;

    j--;

  }

}

Прыклад 18.19.

 V. Праграма:

#include <iostream>

#include <vector>

#include <string>

#include <fstream>

#include <windows.h>

 

using namespace std;

using namespace std::__cxx11;

 

int kol_a(string s)

{

  int k = 0;

  for (int i = 0; i < s.length(); i++)

    if (s[i] == 'а' || s[i] == 'А')

      k++;

  return k;

}

 

bool comp(string x, string y)

{

  return (kol_a(x) > kol_a(y));

}

 

int main()

{

  SetConsoleCP(1251);

  SetConsoleOutputCP(1251);

  ifstream fin("input.txt");

  ofstream fout("output.txt");

  int n;

  fin >> n;

  fin.ignore();

  vector <string> a(n);

  for (int i = 0; i < n; i++)

    fin >> a[i];

  for (int k = 0; k < n - 1; k++){

    int nmax = k;

    for (int i = k + 1; i < n; i++)

      if (comp (a[i], a[nmax]))

       nmax = i;

    swap(a[k], a[nmax]);

  }

  for (int i = 0; i < n; i++)

    fout << a[i] << endl;

  return 0;

}

 V. Тэсціраванне. У тэкставы файл запісаны словы з пункта  18.1.

      

Прыклад 18.20.

 V.  Фрагмент праграмы (функцыю vvod і бібліятэкі, што падключаюцца, гл. у прыкладзе 17.8):

struct student

{

  string fam, gorod;

  vector <int> otm = vector<int>(3);

  int summa;

};

…

bool comp(student x, student y)

{

  return (x.summa > y.summa);

}

 

int main()

{

  SetConsoleCP(1251);

  SetConsoleOutputCP(1251);

  vector <student> a;

  vvod (a);

  ofstream fout ("output.txt");

  for (int k = 1; k < a.size(); k++){

    int i = k;

    while (i > 0 && 

        !comp(a[i - 1], a[i])){

      swap(a[i - 1], a[i]);

      i--;

    }

  }

  for (int i = 0; i < a.size(); i++){

    fout << a[i].fam << '\t';

    fout << a[i].gorod << '\t';

    fout << a[i].summa << endl;

  }

  return 0;

}

     VI. Тэсціраванне. Выкарыстоўваецца тэкставы файл з прыкладу 17.8.

    Пытанні к параграфу

    1. На якіх прынцыпах заснавана сартаванне выбарам?

    2. На якіх прынцыпах заснавана сартаванне абменам?

    3. У чым сутнасць сартавання простымі ўстаўкамі?

    4. За якую колькасць аперацый параўнання будзе адсартаваны масіў, калі выкарыстоўваць сартаванне абменам?

    5. Колькі перастановак будзе зроблена для ўпарадкавання масіву, калі выкарыстоўваць сартаванне выбарам?

    6. У чым перавага алгарытму хуткага сартавання?

    7. Якія недахопы ёсць у алгарытму хуткага сартавання?

    Практыкаванні

        

    1. Дадзены лінейны масіў (вектар) з цэлых лікаў. Напісаць праграму сартавання масіву. Даныя згенерыраваць выпадковым чынам.

      1. Так, каб усе кратныя тром стаялі ў пачатку масіву, а не кратныя ў канцы.
      2. У парадку ўзрастання сумы лічбаў ліку.
      3. У парядку спадання колькасці дзельнікаў ліку.

    2. Дадзены лінейны масіў (вектар) са слоў. Напісаць праграму сартавання масіву. Даныя чытаць з файла.

      1. Па колькасці літар у слове, у парадку ўзрастання.
      2. Па колькасці зычных літар у слове, у парадку спадання.
      3. Па колькасці розных літар у слове, у парадку ўзрастання.

    3. Дадзены лінейны масіў (вектар) са структур. Напісаць праграму сартавання масіву. Даныя чытаць з файла. Можна выкарыстоўваць файлы, створаныя для практыкавання 6 пасля § 17.

    1. У файле захоўваюцца: назва краіны, сталіца, плошча (тыс. км2) і колькасць насельніцтва (млн чал.).

    Беларусь    Мінск         208       9.41

    Расія       Масква        17075     143.3

    ЗША         Вашынгтон     9373      310.2

    Канада      Атава         9985      34.2

    Францыя     Парыж         547       65.4

    І г.д.

    Адсартаваць даныя ў парадку ўзрастання плошчы.

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

    Samsung      WW65K52E69S       2400      6.5

    Bosch        WLT24440OE        2300      7

    Haier        HW70-BP12758S     1900      7

    LG           F12M7NDS0         1700      6

    И т.д.

    Адсартаваць даныя ў алфавітным парадку па назве вытворцы.

    3. У файле захоўваюцца: назва возера, вобласць, у якой яно размешчана, яго аб’ем (млн м3), плошча (км2), максімальная глыбіня (м) і празрыстасць (м).

    Нарач     Мінская       710      79.6     24.8     7.4

    Снуды     Віцебская     107      22       16.5     6.6

    Рычы      Віцебская     131.5    12.9     51.9     5.5

    Свіцязь   Гродзенская   7.76     25.2     15       5.2

    І г.д.

    Адсартаваць даныя ў парадку спадання празрыстасці.

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

    Для вымярэння часу можна выкарыстоўваць  int t1 = clock(); з бібліятэкі  ctime, (выдае час у мілісекундах). Час замяраць да пачатку работы алгарытму і пасля заканчэння работы алгарытму (розніца — час работы алгарытму).

    Для выканання работы кіравацца наступным планам (для кожнага алгарытму):

      1. Згенерыраваць тэкставы файл з 20 000 цэлых лікаў (дыяпазон лікаў: –10000..10000).
      2. Змераць і запісаць час работы праграм для атрыманага файла.
      3. Згенерыраваць тэкставы файл з 20 000 цэлых лікаў (дыяпазон лікаў: –100..100).
      4. Змераць і запісаць час работы праграм.
      5. Павялічыць колькасць элементаў у пунктах 1 і 3 у два разы (да 40 000). Як зменіцца час выканання праграмы?
      6. Пункты 1—5 выканаць 10 разоў.
      7. Адсартаваць у адваротным парадку ўжо адсартаваны масіў для:

    7.1. 20000цэлых лікаў (дыяпазон лікаў –10000..10000). 
    7.2.  20000 цэлых лікаў (дыяпазон лікаў –100..100);
    7.3. 40000 цэлых лікаў (дыяпазон лікаў –10000..10000;
    7.4. 40000 цэлых лікаў (дыяпазон лікаў –100..100).

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

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