Sortiranje niza je zadatak koji je sam po sebi interesantan ali i izuzetno važan jer ima mnogobrojne primene. Na primer, često se podaci sortiraju prilikom rangiranja (na primer, prilikom upisa na fakultet, da bi se odredio redosled kandidata). Pored toga, sortiranje je i izrazito značajna tehnika pretprocesiranja podataka, koja omogućava njihovu efikasniju obradu. Najznačajniji dobitak koji pruža sortiranje je to što je pretraga sortiranog niza neuporedivo brža nego kada niz nije sortiran, o čemu će više reči biti u poglavljima 3.6 i 3.7. U ovom poglavlju razmotrićemo još neke dodatne koristi od sortiranja. Na primer, u sortiranom nizu se elementi koji su bliski po vrednosti nalaze na bliskim pozicijama. Jednaki elementi su međusobno susedni. Ovo omogućava da se obrada duplikata vrši brzo a i da se veoma bliske vrednosti u nizu nalaze brzo. Sortirani niz predstavlja i jednu kanonsku reprezentaciju multiskupa podataka koje sadrži, pa se, na primer, provera da li dva niza sadrže iste elemente može efikasno izvršiti ako se oni najpre sortiraju.
Sortiranje je veoma jednostavna, a toliko korisna tehnika da se često savetuje da se prilikom konstrukcije algoritama pre bilo čega drugoga pokuša sa sortiranjem.
Ako nemamo nikakve posebne pretpostavke o sadržaju nizova, i ako pretpostavimo da se dva elementa niza mogu uporediti i razmeniti u vremenu \(O(1)\), tada se niz može sortirati u vremenu \(O(n\log n)\), gde je \(n\) broj elemenata niza. Postoji nekoliko efikasnih algoritama kojima se ovo može postići i o njima će više reči biti u narednim poglavljima. Biblioteke svih savremenih programskih jezika nude bibliotečke funkcije za efikasno sortiranje, koje implementiraju ove algoritme i niz sortiraju u vremenu \(O(n\log{n})\).
Čest je slučaj da neka obrada nesortiranog niza zahteva vreme \(O(n^2)\) (na primer, potrebno je obraditi sve parove elemenata niza), a da obrada sortiranog niza zahteva vreme \(O(\log{n})\), \(O(n)\) ili \(O(n \log{n})\) i tada se isplati sortirati niz pre obrade. Na primer, prebrojavanje različitih elemenata nesortiranog niza se mora vršiti u vremenu \(O(n^2)\), a sortiranog niza može se izvršiti u vremenu \(O(n)\), te se za prebrojavanje različitih elemenata isplati prvo sortirati niz.
S druge strane, ako neka obrada nesortiranog niza zahteva vreme \(O(n)\), tada se sortiranje ne isplati, čak i ako se obrada sortiranog niza vrši u vremenu \(O(1)\). Na primer, minimum i maksimum nesortiranog niza se mogu odrediti u vremenu \(O(n)\), a sortiranog niza u vremenu \(O(1)\), pa se za pronalaženje minimuma i maksimuma ne isplati sortirati niz (jer je za to potrebno vreme \(O(n\log n)\).
Situacija se menja ako je obradu potrebno izvršiti više puta. Pretpostavimo da je, na primer, za više vrednosti potrebno proveriti da li su sadržane u nizu. Proveru da li je element sadržan u nesortiranom nizu možemo izvršiti u vremenu \(O(n)\), a proveru da li je sadržan u sortiranom nizu u vremenu \(O(\log{n})\) (algoritmom binarne pretrage, prikazanom u poglavlju 3.6). Ako se vrši samo jedan upit tj. ako samo za jedan element proveravamo da li je sadržan u nizu, bolje je izvršiti linearnu pretragu niza u vremenu \(O(n)\), nego najpre sortirati niz u vremenu \(O(n\log{n})\). Međutim, ako se vrši \(k\) upita, tada je bez sortiranja potrebno vreme \(O(kn)\), a sa sortiranjem \(O(n\log{n}) + O(k \log{n})\). Kada je \(k\) reda veličine \(n\) tada se radi o razlici između kvadratnog vremena (u pristupu bez sortiranja) i kvazilinearnog vremena (u pristupu sa sortiranjem), što daje ogromnu razliku za velike vrednosti \(n\).
U nekim problemima nepoželjno je da se tokom neke analize podataka podaci transformišu, jer to može da spreči neke naredne analize podataka. Na primer, ako sortiramo niz, dalje analize u kojima je važan redosled podataka neće biti moguće, jer se gubi informacija o polaznom redosledu. U takvim problemima je pre sortiranja neophodno napraviti kopiju niza.
U nastavku ćemo prikazati nekoliko tipičnih zadataka koji prikazuju kako se primenom sortiranja neki problemi rešavaju efikasnije.
Kao što smo već najavili, sortiranje može pomoći prilikom obrade duplikata u nizu.
Pretpostavimo da su internet adrese predstavljene prirodnim brojevima (IP adrese se, na primer, čuvaju u obliku neoznačenih 32-bitnih brojeva). Pretraživač čuva spisak svih adresa koje je korisnik posetio tokom nekog prethodnog perioda. Korisnik je mnoge adrese posećivao i više puta. Napiši program koji određuje broj različitih adresa koje je korisnik posetio.
Sa standardnog ulaza se unosi broj \(n\) (\(1 \leq n \leq 10^5\)), a zatim i \(n\) prirodnih brojeva (manjih od \(2^{32}\)), svaki u posebnom redu.
Na standardni izlaz ispisati broj različitih adresa koje je korisnik posetio.
8 123456789 234567890 345678901 234567890 456789012 234567890 456789012 234567890
4
Naivan način da se detektuju duplikati se može zasnovati na algoritmu linearne pretrage. Brojaćemo samo one članove niza koji se prvi put pojavljuju (kada se pojavi neki element koji se već pojavio ranije nećemo ga brojati). Proveru da li se element niza na poziciji \(i\) (od nula do \(n-1\)) ranije već pojavio vršićemo tako što ćemo proveriti da li se taj element javlja na nekoj poziciji \(j\) od \(0\) do \(i-1\). To možemo uraditi algoritmom linearne pretrage (linearna pretraga se može vršiti i bibliotečkom funkcijom find).
Ovo rešenje je neefikasno i složenost mu je \(O(n^2)\), gde je \(n\) broj elemenata niza.
// 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;
}Jedan od najčešćih načina uklanjanja duplikata iz niza je zasnovan na sortiranju, jer se nakon sortiranja duplikati nađu jedan do drugog. Sortiranje možemo najbolje uraditi pozivom bibliotečke funkcije. Nakon sortiranja prolazimo redom kroz niz i brojimo prvi element, a zatim i sve elemente koji su različiti od njima prethodnog (to su prva pojavljivanja elemenata u sortiranom nizu).
Složenošću ovog pristupa dominira složenost postupka sortiranja. Prolaz nakon sortiranja je linearne složenosti, a sortiranje se može ostvariti u složenosti \(O(n \log{n})\), gde je \(n\) broj elemenata niza.
// 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;
}Nakon sortiranja bliske vrednosti se nalaze na bliskim pozicijama.
Dva gosta su došla u hotel i žele da odsednu u slobodnim sobama koje su što bliže jedna drugoj, da bi tokom večeri mogli da zajedno rade u jednoj od tih soba. Ako postoji više takvih soba, oni biraju da budu što dalje od recepcije, tj. u sobama sa što većim rednim brojevima, kako im buka ne bi smetala. Napiši program koji određuje brojeve soba koje gosti treba da dobiju, pretpostavljajući da je poznat spisak slobodnih soba u tom trenutku.
U prvoj liniji standardnog ulaza nalazi se broj \(n\) (\(1 \leq n \leq 10^5\)), a zatim se nalaze brojevi slobodnih soba - svi brojevi su različiti, ali je njihov redosled proizvoljan.
Na standardni izlaz ispisati brojeve soba gostiju (prvo manji broj, pa veći), razdvojene jednim razmakom.
7 18 6 25 11 4 1 16
16 18
Zadatak može da se reši naivno tako što se izračunaju rastojanja između svake dve sobe i što se pronađe par sa najmanjim rastojanjima.
Pošto parova ima \(\frac{n(n-1)}{2}\), složenost ovog pristupa je \(O(n^2)\).
Bolje rešenje se može dobiti ako se niz najpre sortira. Naime, najbliži element svakom elementu u sortiranom nizu je jedan od njemu susednih. Dakle, ako broj \(a_i\) učestvuje u paru najbližih soba, onda drugi element tog para može biti ili broj \(a_{i-1}\) koji je neposredno ispred \(a_i\) u sortiranom redosledu ili broj \(a_{i+1}\) koji je neposredno iza njega (naravno, ne postoji element ispred prvog, niti element iza poslednjeg elementa niza). Zato je nakon sortiranja dovoljno proveriti sve razlike između susednih elemenata i odrediti najmanju od njih (ako ima više istih, određujemo poslednju). Za ovo koristimo algoritam određivanja najmanjeg elementa, dok sortiranje možemo najlakše izvršiti bibliotečkom funkcijom.
Sortiranje bibliotečkom funkcijom ima složenost \(O(n \log{n})\) operacija, dok je traženje minimuma složenosti \(O(n)\), tako da je ukupno vreme opisanog postupka \(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;
}Da bi se proverilo da li su multiskupovi elemenata koji se nalaze u dva niza jednaka tj. da li je jedan niz permutacija drugog, možemo upotrebiti sortiranje.
Napiši program koji učitava dva niza brojeva i proverava da li je drugi niz permutacija prvog tj. da li se mogao dobiti od prvog samo promenom redosleda njegovih elemenata.
Sa standardnog ulaza se unose dva niza prirodnih brojeva. Za svaki niz se unosi broj elemenata (najviše \(50000\)), a zatim i elementi razdvojeni po jednim razmakom.
Na standardni izlaz ispiši reč da ako je drugi niz dobijen mešanjem prvog, tj. ne ako nije.
5 1 3 2 4 3 5 4 3 2 3 1
da
Jedan od načina da proverimo da li je jedan niz permutacija drugog je da oba niza dovedemo u neku “kanonsku” formu, a onda da proverimo da li su dobijene kanonske forme jednake. Najjednostavnija kanonska forma se dobija kada se nizovi sortiraju po veličini (na primer, neopadajuće).
Poređenje jednakosti dva vektora se može ostvariti (bibliotečkim) operatorom == (u vremenskoj složenosti \(O(n)\)). Ako bi elementi bili smešteni u nizove, onda bi jednakost bilo potrebno proveriti ili ručno implementiranim poređenjem jednog po jednog elementa (linearnom pretragom bi se ispitivalo da li postoji element koji im se razlikuje) ili bibliotečkom funkcijom equal koja prima iterator na početak i iza kraja prvog niza i na početak drugog niza.
Ako želimo da održimo redosled elemenata u vektorima, pre provere permutacija bismo morali da napravimo kopije, koje ćemo zatim sortirati (ovim se povećava dodatna memorijska složenost).
Nizovi od \(n\) elemenata se bibliotečkom funkcijom porede u vremenu \(O(n\log{n})\), dok se njihova jednakost proverava u vremenu \(O(n)\). Proverom, dakle, dominira vreme sortiranja i algoritam je složenosti \(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;
}U mnogim realnim primenama programiranja se razmatraju intervali. To mogu biti prostorni intervali, ali i vremenski intervali. Na primer, prilikom raspoređivanja časova ili nekih drugih aktivnosti, svaki čas koji se raspoređuje se predstavlja intervalom određenim vremenom početka i vremenom kraja. Intervali mogu biti jednodimenzionalni, dvodimenzionalni (tada su u pitanju pravougaonici), pa i višedimenzionalni. Efikasni algoritmi za obrade intervala se obično dobijaju tako što se intervali obilaze u nekom sortiranom redosledu: to je u jednodimenzionom slučaju obično ili redosled levih krajeva ili redosled desnih krajava, a ponekad se istovremeno razmatraju i sortiraju sve tačke (i levi i desni krajevi). Prikažimo ovo kroz nekoliko zadataka.
Poznat je raspored časova i za svaki čas je poznato vreme početka i završetka. Pretpostavićemo da su časovi intervali oblika \([a, b)\), tj. da čas traje u trenutku svog početka \(a\), a da ne traje više u trenutku svog završetka \(b\). Koliko je učionica potrebno da bi svi časovi mogli da se održe?
Sa standardnog ulaza se učitava broj časova \(n\) (\(1 \leq n \leq 50000\)), a zatim u narednih \(n\) redova vreme početka i vreme završetka svakog časa (merenje je veoma precizno, pa se vreme predstavlja prirodnim brojevima manjim od milijarde), odvojene sa po jednim razmakom.
Na standardni izlaz ispisati maksimalni broj časova koji se održavaju u istom trenutku.
8 3 7 7 8 2 5 6 8 4 6 1 6 4 5 1 2
5
U trenutku 4 raspoređeno je 5 časova.
Direktno rešenje bi podrazumevalo da se održava niz u kome se za svaki trenutak pamti broj časova koji se u tom trenutku održavaju. Pošto ne znamo koliko trenutaka postoji umesto niza možemo upotrebiti mapu (u jeziku C++ možemo upotrebiti unordered_map).
Ako je trenutaka i časova puno, ova metoda će biti veoma neefikasna. Složenost najgoreg slučaja je \(O(n \cdot m)\), gde je \(n\) broj trenutaka, a \(m\) broj časova.
Broj potrebnih učionica se menja samo u trenucima kada neki čas počne ili se završi. Da bi se odredio najveći broj učionica dovoljno je razmotriti samo te karakteristične trenutke. Veoma prirodno je da te karakteristične trenutke obrađujemo hronološki, u rastućem redosledu vremena. Možemo kreirati niz koji sadrži sve karakteristične trenutke (vremena početaka i krajeva časova) i za svaki trenutak beležiti da li je početak ili kraj. Taj niz možemo sortirati i zatim obrađivati redom, izračunavajući za svaki trenutak broj časova koji u tom trenutku traju inkrementalno, na osnovu broja časova u prethodnom karakterističnom trenutku. Ako u nekom vremenskom trenutku više časova počinje ili se završava, broj učionica treba upoređivati sa maksimumom tek kada obradimo sve časove koji su počeli ili su se završili u tom trenutku. To se može postići tako što se obrađuju svi časovi koji su počeli ili su se završili u tom trenutku. Međutim, pošto se sortiranje parova vrši leksikografski (prvo po vremenu, a onda po oznaci \(1\) tj. \(-1\)), svi događaji koji su se desili u istom trenutku sortirani su tako da prvo idu završeci časova (oznaka \(-1\)), pa onda počeci (oznaka \(1\)). Zbog toga će se broj prvo smanjivati, pa onda rasti i neće biti moguće da se dobije pogrešan rezultat zato što su dodati neki časovi pre nego što je konstatovano da su se neki časovi završili.
Ako postoji \(n\) časova, postoji \(2n\) karakterističnih trenutaka za čije je sortiranje potrebno \(O(n\log{n})\) koraka. Nakon sortiranja, niz trenutaka se obrađuje jednim prolaskom kroz niz u linearnom vremenu. Dakle, složenošću dominira sortiranje i složenost ovog rešenja je \(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 pocetak, kraj;
cin >> pocetak >> kraj;
promene.emplace_back(pocetak, 1);
promene.emplace_back(kraj, -1);
}
sort(begin(promene), end(promene));
int trenutnoUcionica = 0;
int maksUcionica = 0;
int i = 0;
while (i < 2*n) {
int trenutak = promene[i].first;
while (i < 2*n && promene[i].first == trenutak)
trenutnoUcionica += promene[i++].second;
if (trenutnoUcionica > maksUcionica)
maksUcionica = trenutnoUcionica;
}
cout << maksUcionica << 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 pocetak, kraj;
cin >> pocetak >> kraj;
promene.emplace_back(pocetak, 1);
promene.emplace_back(kraj, -1);
}
sort(begin(promene), end(promene));
int trenutnoUcionica = 0;
int maksUcionica = 0;
int i = 0;
while (i < 2*n) {
int trenutak = promene[i].first;
while (i < 2*n && promene[i].first == trenutak)
trenutnoUcionica += promene[i++].second;
if (trenutnoUcionica > maksUcionica)
maksUcionica = trenutnoUcionica;
}
cout << maksUcionica << endl;
return 0;
}