Сортирање низа је задатак који је сам по себи интересантан али и изузетно важан јер има многобројне примене. На пример, често се подаци сортирају приликом рангирања (на пример, приликом уписа на факултет, да би се одредио редослед кандидата). Поред тога, сортирање је и изразито значајна техника претпроцесирања података, која омогућава њихову ефикаснију обраду. Најзначајнији добитак који пружа сортирање је то што је претрага сортираног низа неупоредиво бржа него када низ није сортиран, о чему ће више речи бити у поглављима 3.6 и 3.7. У овом поглављу размотрићемо још неке додатне користи од сортирања. На пример, у сортираном низу се елементи који су блиски по вредности налазе на блиским позицијама. Једнаки елементи су међусобно суседни. Ово омогућава да се обрада дупликата врши брзо а и да се веома блиске вредности у низу налазе брзо. Сортирани низ представља и једну канонску репрезентацију мултискупа података које садржи, па се, на пример, провера да ли два низа садрже исте елементе може ефикасно извршити ако се они најпре сортирају.
Сортирање је веома једноставна, а толико корисна техника да се често саветује да се приликом конструкције алгоритама пре било чега другога покуша са сортирањем.
Ако немамо никакве посебне претпоставке о садржају низова, и ако претпоставимо да се два елемента низа могу упоредити и разменити у времену \(O(1)\), тада се низ може сортирати у времену \(O(n\log n)\), где је \(n\) број елемената низа. Постоји неколико ефикасних алгоритама којима се ово може постићи и о њима ће више речи бити у наредним поглављима. Библиотеке свих савремених програмских језика нуде библиотечке функције за ефикасно сортирање, које имплементирају ове алгоритме и низ сортирају у времену \(O(n\log{n})\).
Чест је случај да нека обрада несортираног низа захтева време \(O(n^2)\) (на пример, потребно је обрадити све парове елемената низа), а да обрада сортираног низа захтева време \(O(\log{n})\), \(O(n)\) или \(O(n \log{n})\) и тада се исплати сортирати низ пре обраде. На пример, пребројавање различитих елемената несортираног низа се мора вршити у времену \(O(n^2)\), а сортираног низа може се извршити у времену \(O(n)\), те се за пребројавање различитих елемената исплати прво сортирати низ.
С друге стране, ако нека обрада несортираног низа захтева време \(O(n)\), тада се сортирање не исплати, чак и ако се обрада сортираног низа врши у времену \(O(1)\). На пример, минимум и максимум несортираног низа се могу одредити у времену \(O(n)\), а сортираног низа у времену \(O(1)\), па се за проналажење минимума и максимума не исплати сортирати низ (јер је за то потребно време \(O(n\log n)\).
Ситуација се мења ако је обраду потребно извршити више пута. Претпоставимо да је, на пример, за више вредности потребно проверити да ли су садржане у низу. Проверу да ли је елемент садржан у несортираном низу можемо извршити у времену \(O(n)\), а проверу да ли је садржан у сортираном низу у времену \(O(\log{n})\) (алгоритмом бинарне претраге, приказаном у поглављу 3.6). Ако се врши само један упит тј. ако само за један елемент проверавамо да ли је садржан у низу, боље је извршити линеарну претрагу низа у времену \(O(n)\), него најпре сортирати низ у времену \(O(n\log{n})\). Међутим, ако се врши \(k\) упита, тада је без сортирања потребно време \(O(kn)\), а са сортирањем \(O(n\log{n}) + O(k \log{n})\). Када је \(k\) реда величине \(n\) тада се ради о разлици између квадратног времена (у приступу без сортирања) и квазилинеарног времена (у приступу са сортирањем), што даје огромну разлику за велике вредности \(n\).
У неким проблемима непожељно је да се током неке анализе података подаци трансформишу, јер то може да спречи неке наредне анализе података. На пример, ако сортирамо низ, даље анализе у којима је важан редослед података неће бити могуће, јер се губи информација о полазном редоследу. У таквим проблемима је пре сортирања неопходно направити копију низа.
У наставку ћемо приказати неколико типичних задатака који приказују како се применом сортирања неки проблеми решавају ефикасније.
Као што смо већ најавили, сортирање може помоћи приликом обраде дупликата у низу.
Претпоставимо да су интернет адресе представљене природним бројевима (IP адресе се, на пример, чувају у облику неозначених 32-битних бројева). Претраживач чува списак свих адреса које је корисник посетио током неког претходног периода. Корисник је многе адресе посећивао и више пута. Напиши програм који одређује број различитих адреса које је корисник посетио.
Са стандардног улаза се уноси број \(n\) (\(1 \leq n \leq 10^5\)), а затим и \(n\) природних бројева (мањих од \(2^{32}\)), сваки у посебном реду.
На стандардни излаз исписати број различитих адреса које је корисник посетио.
8 123456789 234567890 345678901 234567890 456789012 234567890 456789012 234567890
4
Наиван начин да се детектују дупликати се може засновати на алгоритму линеарне претраге. Бројаћемо само оне чланове низа који се први пут појављују (када се појави неки елемент који се већ појавио раније нећемо га бројати). Проверу да ли се елемент низа на позицији \(i\) (од нула до \(n-1\)) раније већ појавио вршићемо тако што ћемо проверити да ли се тај елемент јавља на некој позицији \(j\) од \(0\) до \(i-1\). То можемо урадити алгоритмом линеарне претраге (линеарна претрага се може вршити и библиотечком функцијом find).
Ово решење је неефикасно и сложеност му је \(O(n^2)\), где је \(n\) број елемената низа.
// broj razlicitih elemenata niza a
int brojRazlicitih(const vector<unsigned>& a) {
int broj = 0;
// za svaki element niza a
for (int i = 0; i < a.size(); i++) {
// proveravamo da li se a[i] javlja pre pozicije i
bool sadrzi = false;
for (int j = 0; j < i && !sadrzi; j++)
if (a[i] == a[j])
sadrzi = true;
// ako se ne pojavljuje, uracunavamo ga
if (!sadrzi)
broj++;
}
return broj;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// broj razlicitih elemenata niza a
int brojRazlicitih(const vector<unsigned>& a) {
int broj = 0;
// za svaki element niza a
for (int i = 0; i < a.size(); i++) {
// proveravamo da li se a[i] javlja pre pozicije i
bool sadrzi = false;
for (int j = 0; j < i && !sadrzi; j++)
if (a[i] == a[j])
sadrzi = true;
// ako se ne pojavljuje, uracunavamo ga
if (!sadrzi)
broj++;
}
return broj;
}
int main() {
ios_base::sync_with_stdio(false);
// ucitavamo niz
int n;
cin >> n;
vector<unsigned> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << brojRazlicitih(a) << endl;
return 0;
}Један од најчешћих начина уклањања дупликата из низа је заснован на сортирању, јер се након сортирања дупликати нађу један до другог. Сортирање можемо најбоље урадити позивом библиотечке функције. Након сортирања пролазимо редом кроз низ и бројимо први елемент, а затим и све елементе који су различити од њима претходног (то су прва појављивања елемената у сортираном низу).
Сложеношћу овог приступа доминира сложеност поступка сортирања. Пролаз након сортирања је линеарне сложености, а сортирање се може остварити у сложености \(O(n \log{n})\), где је \(n\) број елемената низа.
// broj razlicitih elemenata niza a
int brojRazlicitih(const vector<unsigned>& a) {
// pravimo kopiju, da bi originalni niz ostao nepromenjen
auto as = a;
// sortiramo niz
sort(as.begin(), as.end());
// brojimo prvi element i sve elemente koje su razliciti od
// svojih prethodnika
int broj = 1;
for (int i = 1; i < as.size(); i++)
if (as[i] != as[i-1])
broj++;
return broj;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// broj razlicitih elemenata niza a
int brojRazlicitih(const vector<unsigned>& a) {
// pravimo kopiju, da bi originalni niz ostao nepromenjen
auto as = a;
// sortiramo niz
sort(as.begin(), as.end());
// brojimo prvi element i sve elemente koje su razliciti od
// svojih prethodnika
int broj = 1;
for (int i = 1; i < as.size(); i++)
if (as[i] != as[i-1])
broj++;
return broj;
}
int main() {
ios_base::sync_with_stdio(false);
// ucitavamo niz
int n;
cin >> n;
vector<unsigned> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << brojRazlicitih(a) << endl;
return 0;
}Након сортирања блиске вредности се налазе на блиским позицијама.
Два госта су дошла у хотел и желе да одседну у слободним собама које су што ближе једна другој, да би током вечери могли да заједно раде у једној од тих соба. Ако постоји више таквих соба, они бирају да буду што даље од рецепције, тј. у собама са што већим редним бројевима, како им бука не би сметала. Напиши програм који одређује бројеве соба које гости треба да добију, претпостављајући да је познат списак слободних соба у том тренутку.
У првој линији стандардног улаза налази се број \(n\) (\(1 \leq n \leq 10^5\)), а затим се налазе бројеви слободних соба - сви бројеви су различити, али је њихов редослед произвољан.
На стандардни излаз исписати бројеве соба гостију (прво мањи број, па већи), раздвојене једним размаком.
7 18 6 25 11 4 1 16
16 18
Задатак може да се реши наивно тако што се израчунају растојања између сваке две собе и што се пронађе пар са најмањим растојањима.
Пошто парова има \(\frac{n(n-1)}{2}\), сложеност овог приступа је \(O(n^2)\).
Боље решење се може добити ако се низ најпре сортира. Наиме, најближи елемент сваком елементу у сортираном низу је један од њему суседних. Дакле, ако број \(a_i\) учествује у пару најближих соба, онда други елемент тог пара може бити или број \(a_{i-1}\) који је непосредно испред \(a_i\) у сортираном редоследу или број \(a_{i+1}\) који је непосредно иза њега (наравно, не постоји елемент испред првог, нити елемент иза последњег елемента низа). Зато је након сортирања довољно проверити све разлике између суседних елемената и одредити најмању од њих (ако има више истих, одређујемо последњу). За ово користимо алгоритам одређивања најмањег елемента, док сортирање можемо најлакше извршити библиотечком функцијом.
Сортирање библиотечком функцијом има сложеност \(O(n \log{n})\) операција, док је тражење минимума сложености \(O(n)\), тако да је укупно време описаног поступка \(O(n \log{n})\).
void najblizeSobe(const vector<int>& a,
int& soba1, int& soba2) {
// pravimo duplikat niza koji cemo da sortiramo
auto b = a;
sort(begin(b), end(b));
int min = 1;
for (int i = 2; i < b.size(); i++)
if (b[i] - b[i-1] <= b[min] - b[min-1])
min = i;
soba1 = b[min-1]; soba2 = b[min];
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void najblizeSobe(const vector<int>& a,
int& soba1, int& soba2) {
// pravimo duplikat niza koji cemo da sortiramo
auto b = a;
sort(begin(b), end(b));
int min = 1;
for (int i = 2; i < b.size(); i++)
if (b[i] - b[i-1] <= b[min] - b[min-1])
min = i;
soba1 = b[min-1]; soba2 = b[min];
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int soba1, soba2;
najblizeSobe(a, soba1, soba2);
cout << soba1 << " " << soba2 << endl;
return 0;
}Да би се проверило да ли су мултискупови елемената који се налазе у два низа једнака тј. да ли је један низ пермутација другог, можемо употребити сортирање.
Напиши програм који учитава два низа бројева и проверава да ли је други низ пермутација првог тј. да ли се могао добити од првог само променом редоследа његових елемената.
Са стандардног улаза се уносе два низа природних бројева. За сваки низ се уноси број елемената (највише \(50000\)), а затим и елементи раздвојени по једним размаком.
На стандардни излаз испиши реч da ако је други низ добијен мешањем првог, тј. ne ако није.
5 1 3 2 4 3 5 4 3 2 3 1
da
Један од начина да проверимо да ли је један низ пермутација другог је да оба низа доведемо у неку “канонску” форму, а онда да проверимо да ли су добијене канонске форме једнаке. Најједноставнија канонска форма се добија када се низови сортирају по величини (на пример, неопадајуће).
Поређење једнакости два вектора се може остварити (библиотечким) оператором == (у временској сложености \(O(n)\)). Ако би елементи били смештени у низове, онда би једнакост било потребно проверити или ручно имплементираним поређењем једног по једног елемента (линеарном претрагом би се испитивало да ли постоји елемент који им се разликује) или библиотечком функцијом equal која прима итератор на почетак и иза краја првог низа и на почетак другог низа.
Ако желимо да одржимо редослед елемената у векторима, пре провере пермутација бисмо морали да направимо копије, које ћемо затим сортирати (овим се повећава додатна меморијска сложеност).
Низови од \(n\) елемената се библиотечком функцијом пореде у времену \(O(n\log{n})\), док се њихова једнакост проверава у времену \(O(n)\). Провером, дакле, доминира време сортирања и алгоритам је сложености \(O(n\log{n})\).
bool jePermutacija(vector<int>& a, vector<int>& b) {
if (a.size() != b.size())
return false;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
return a == b;
}#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> ucitajVektor() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
return a;
}
bool jePermutacija(vector<int>& a, vector<int>& b) {
if (a.size() != b.size())
return false;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
return a == b;
}
int main() {
ios_base::sync_with_stdio(false);
vector<int> a = ucitajVektor();
vector<int> b = ucitajVektor();
cout << (jePermutacija(a, b) ? "da" : "ne") << endl;
return 0;
}У многим реалним применама програмирања се разматрају интервали. То могу бити просторни интервали, али и временски интервали. На пример, приликом распоређивања часова или неких других активности, сваки час који се распоређује се представља интервалом одређеним временом почетка и временом краја. Интервали могу бити једнодимензионални, дводимензионални (тада су у питању правоугаоници), па и вишедимензионални. Ефикасни алгоритми за обраде интервала се обично добијају тако што се интервали обилазе у неком сортираном редоследу: то је у једнодимензионом случају обично или редослед левих крајева или редослед десних крајава, а понекад се истовремено разматрају и сортирају све тачке (и леви и десни крајеви). Прикажимо ово кроз неколико задатака.
Познат је распоред часова и за сваки час је познато време почетка и завршетка. Претпоставићемо да су часови интервали облика \([a, b)\), тј. да час траје у тренутку свог почетка \(a\), а да не траје више у тренутку свог завршетка \(b\). Колико је учионица потребно да би сви часови могли да се одрже?
Са стандардног улаза се учитава број часова \(n\) (\(1 \leq n \leq 50000\)), а затим у наредних \(n\) редова време почетка и време завршетка сваког часа (мерење је веома прецизно, па се време представља природним бројевима мањим од милијарде), одвојене са по једним размаком.
На стандардни излаз исписати максимални број часова који се одржавају у истом тренутку.
8 3 7 7 8 2 5 6 8 4 6 1 6 4 5 1 2
5
У тренутку 4 распоређено је 5 часова.
Директно решење би подразумевало да се одржава низ у коме се за сваки тренутак памти број часова који се у том тренутку одржавају. Пошто не знамо колико тренутака постоји уместо низа можемо употребити мапу (у језику C++ можемо употребити unordered_map).
Ако је тренутака и часова пуно, ова метода ће бити веома неефикасна. Сложеност најгорег случаја је \(O(n \cdot m)\), где је \(n\) број тренутака, а \(m\) број часова.
Број потребних учионица се мења само у тренуцима када неки час почне или се заврши. Да би се одредио највећи број учионица довољно је размотрити само те карактеристичне тренутке. Веома природно је да те карактеристичне тренутке обрађујемо хронолошки, у растућем редоследу времена. Можемо креирати низ који садржи све карактеристичне тренутке (времена почетака и крајева часова) и за сваки тренутак бележити да ли је почетак или крај. Тај низ можемо сортирати и затим обрађивати редом, израчунавајући за сваки тренутак број часова који у том тренутку трају инкрементално, на основу броја часова у претходном карактеристичном тренутку. Ако у неком временском тренутку више часова почиње или се завршава, број учионица треба упоређивати са максимумом тек када обрадимо све часове који су почели или су се завршили у том тренутку. То се може решити тако што у унутрашњој петљи обрађујемо све часове који су почели или су се завршили у текућем тренутку.
Међутим, унутрашња петља није потребна. Пошто се сортирање парова ради лексикографски (прво по времену, а онда по ознаци \(1\) тј. \(-1\)), тако да су сви догађаји који су се десили у истом тренутку сортирани тако да прво иду завршеци часова (ознака \(-1\)), па онда почеци (ознака \(1\)), не морамо да имамо унутрашњу петљу, јер ће се број прво смањивати, па онда расти и неће бити могуће да се добије погрешан резултат зато што су додати неки часови пре него што је констатовано да су се неки часови завршили.
Ако постоји \(n\) часова, постоји \(2n\) карактеристичних тренутака за чије је сортирање потребно \(O(n\log{n})\) корака. Након сортирања, низ тренутака се обрађује једним проласком кроз низ у линеарном времену. Дакле, сложеношћу доминира сортирање и сложеност овог решења је \(O(n\log{n})\).
int n;
cin >> n;
// niz karakterističnih trenutaka
vector<pair<int, int>> promene;
promene.reserve(2*n);
for (int i = 0; i < n; i++) {
int dosao, otisao;
cin >> dosao >> otisao;
promene.emplace_back(dosao, 1);
promene.emplace_back(otisao, -1);
}
sort(begin(promene), end(promene));
int trenutnoUcionica = 0;
int maksUcionica = 0;
for (int i = 0; i < 2*n; i++) {
trenutnoUcionica += promene[i].second;
if (trenutnoUcionica > maksUcionica)
maksUcionica = trenutnoUcionica;
}
cout << maksPrisutno << endl;#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
// niz karakterističnih trenutaka
vector<pair<int, int>> promene;
promene.reserve(2*n);
for (int i = 0; i < n; i++) {
int dosao, otisao;
cin >> dosao >> otisao;
promene.emplace_back(dosao, 1);
promene.emplace_back(otisao, -1);
}
sort(begin(promene), end(promene));
int trenutnoUcionica = 0;
int maksUcionica = 0;
for (int i = 0; i < 2*n; i++) {
trenutnoUcionica += promene[i].second;
if (trenutnoUcionica > maksUcionica)
maksUcionica = trenutnoUcionica;
}
cout << maksPrisutno << endl;
return 0;
}