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

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