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

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);