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

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.