§ 20. Выкарыстанне бібліятэчных функцый для сартавання і пошуку даных

20.2. Сартаванне

Для сартавання элементаў вектара выкарыстоўваецца функцыя sort, якая мае два параметры: межы дыяпазону, які сартуецца.

Калі ў якасці меж дыяпазону выкарыстоўваць стандартныя ітэратары begin() і end(), то элементы вектара будуць адсартаваны ў парадку ўзрастання. Калі выкарыстоўваць ітэратары rbegin() і rend(), то элементы будуць адсартаваны ў парадку спадання. Пры гэтым вектар павінен складацца з элементаў, для якіх вызначаны аперацыі параўнання: цэлых ці рэчаісных лікаў, сімвалаў, радкоў.

Калі вектар складаецца з элементаў, для якіх не вызначана паняцце парадку (структур ці іншых вектараў), то для іх сартавання неабходны трэці параметр  — функцыя-кампаратар, якая задае адносіны парадку для элементаў.

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

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

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

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

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

  1. Увод зыходных даных. Даныя згенерыруем выпадковым чынам.
  2. Будзем выкарыстоўваць функцыю sort. Паколькі сартаваць элементы трэба па спаданні, то будзем выкарыстоўваць адваротныя ітэратары rbegin() і rend().
  3. Вывад выніку.

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

Для сартавання ў парадку спадання можна выкарыстаць стандартны кампаратар, які задае парадак — большае раней за меншае:

sort(v.begin(), v.end(), greater<int>());

Акрамя кампаратара greater, могуць выкарыстоўвацца кампаратары: less (менш), equal_to (роўна), not_equal_to (не роўна), less_equal (менш або роўна), greater_equal(больш або роўна). Гэтыя кампаратары асацыяваны з тыпам свайго параметра, для якога павінны быць вызначаны аперацыі параўнання. Па змоўчанні працуе кампаратар less, які можна прапускаць.

Прыклад 20.4. На плоскасці зададзены сваімі каардынатамі n пунктаў. Размясціць пункты ў парадку ўзрастання іх абсцыс. Знайсці ўсе пары суседніх пунктаў, абсцысы якіх знаходзяцца на адлегласці не менш за l адна ад адной.

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

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

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

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

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

У рэалізацыі Стандартнай бібліятэкі шаблонаў (STL) у C++ для рэалізацыі сартавання выкарыстоўваецца падыход Дэвіда Мюсера. У 1997 г. ён прапанаваў выкарыстоўваць інтраспектыўнае сартаванне (Introsort). Гэта камбінаваны алгарытм сартавання, які выкарыстоўвае хуткае сартаванне і пераключаецца на пірамідальнае[1] сартаванне, калі глыбіня рэкурсіі перавысіць лагарыфм ад ліку элементаў, што сартуюцца. У хуткім сартаванні выбар апорнага элемента робіцца як медыяны з трох. Калі колькасць элементаў становіцца меншай за 16, ужываецца алгарытм сартавання простымі ўстаўкамі. Такім чынам, функцыя sort аб’ядноўвае ў сабе тры алгарытмы сартавання: хуткае, пірамідальнае і сартаванне простымі ўстаўкамі. Функцыя гарантавана выкарыстоўвае каля  аперацый параўнанняў і абменаў.

Прыклад 20.3.

V. Праграма:

#include <iostream>

#include <vector>

#include <cstdlib>

#include <ctime>

#include <algorithm>

 

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;

  sort(a.rbegin(), a.rend());

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

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

  cout << endl;

  return 0;

}

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

Прыклад 20.4.

V. Праграма:

#include <iostream>

#include <cmath>

#include <vector>

#include <algorithm>

 

using namespace std;

 

struct tchk

{

  double x, y;

};

 

bool comp(tchk a, tchk b)

{

  return (a.x < b.x ||

      (a.x == b.x && a.y < b.y));

}

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <tchk> t(n);

  cout << "koordinaty tochek" << endl;

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

    cin >> t[i].x >> t[i].y;

  /// сартаванне

  sort(t.begin(), t.end(), comp);

  cout << "sort" << endl;

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

    cout << "(" << t[i].x << "," 

        << t[i].y << ")" << " ";

  cout << endl;

  double l;

  cout << "l = ";

  cin >> l;

  ///пошук

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

    if (abs(t[i].x - t[i + 1].x) >= l){

      cout << "(" << t[i].x << ",";

      cout << t[i].y << ")" << '\t';

      cout << "(" << t[i + 1].x ;

      cout << ","<< t[i + 1].y;

      cout << ")" << endl;

    }

  return 0;

}

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


[1] Пірамідальнае сартаванне выкарыстоўвае бінарнае сартавальнае дрэва для захоўвання даных. Пачытаць пра яго можна тут: Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн., 3-е издание. — М.: «Вильямс», 2013.