Задатак можемо решити помоћу само једног пролаза кроз низ и то “у месту” тј. без коришћења помоћног низа. Алгоритам у наставку познат је под називом “Холандска застава тробојка” (енгл. Dutch national flag) и приписује се чувеном информатичару Дајкстри (енгл. Edsger W. Dijkstra).
Одржаваћемо три променљиве \(l\), \(d\) и \(i\) и током петље наметнућемо да важи \(0 \leq l \leq i \leq d \leq n\) и да важе следећи услови.
Дакле, одржавамо распоред <<<<===???>>>, где су са < обележени елементи прве групе, са = елементи друге, са ? елементи треће групе, а са > елементи четврте групе.
Да би инваријанта важила пре уласка у петљу, јасно је да мора да важи да је \(i = 0\) и \(d=n\) (јер су сви елементи из интервала \([i, d) = [0, n)\) неиспитани). Такође, да бисмо били сигурни да су у интервалу \([0, l)\) сви елементи мањи од \(A\), тај интервал мора бити празан и мора да важи да је \(l=0\). Након овакве иницијализације и интервал \([l, i) = [0, 0)\) и интервал \([d, n) = [n, n)\) је празан, па задовољава наметнути услов.
Петља ће се извршавати док год има неиспитаних елемената, а то је док је \(i < d\). Размотримо како треба да изгледа тело петље, да би услови били одржани.
Ако је елемент на позицији \(i\) мањи од броја \(A\) тада ћемо га заменити са елементом на позицији \(l\) (првим елементом из интервала \([A, B]\)), након чега можемо увећати и \(i\) и \(l\).
У супротном, ако је елемент на позицији \(i\) мањи или једнак од \(B\) он припада интервалу \([A, B]\) и већ је на свом допуштеном месту, па само можемо увећати вредност \(i\).
У супротном елемент је већи од \(B\) и тада можемо смањити вредност \(d\) и разменити елемент на позицији \(i\) са елементом на (умањеној) позицији \(d\), не мењајући вредност \(i\) (да би се елемент који је управо доведен на позицију \(i\) могао испитати у наредној итерацији).
На крају петље важи да је \(i=d\). Уз остале наметнуте услове тврђење одатле следи (елементи из интервала позиција \([0, l)\) су мањи од \(A\), елементи из интервала позиција \([l, i) = [l, d)\) су између \(A\) и \(B\), интервал непрегледаних елемената \([i, d)\) је празан, док су елементи из интервала \([d, n)\) већи од \(B\)). Дакле, низ је разбијен на надовезане сегменте \([0, l)\), \([l, d)\) и \([d, n)\) и у сваком сегменту се налазе одговарајући елементи.
Пример. Размотримо рад алгоритма на једном примеру. Нека је \(A=4\), \(B=7\) и нека низ има садржај 5 1 8 6 3 9 4 2. У наставку ћемо приказати стање низа током извођења алгоритма.
l d 5 1 8 6 3 9 4 2 i l d 5 1 8 6 3 9 4 2 i l d 1 5 8 6 3 9 4 2 i l d 1 5 2 6 3 9 4 8 i l d 1 2 5 6 3 9 4 8 i l d 1 2 5 6 3 9 4 8 i l d 1 2 3 6 5 9 4 8 i l d 1 2 3 6 5 4 9 8 i l d 1 2 3 6 5 4 9 8 i
Сложеност. У сваком кораку петље се или увећава i или смањује d, док се не сусретну, што се дешава у \(n\) корака. Сложеност овог приступа је, дакле, \(O(n)\).
U narednom apletu možete proveriti svoje razumevanje ovog algoritma.
✖
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// funkcija ucitava elemente u vektor
vector<int> unosNiza() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
return a;
}
// funkcija organizuje elemente vektora tako da se prvo nalaze elementi
// za koje vazi da su iz intervala (-Inf, A), nakon toga dolaze
// elementi iz intervala [A, B], i nakon toga elementi iz intervala
// (B, Inf)
void podelaNiza(vector<int>& niz, int A, int B) {
// - u intervalu pozicija [0, l) su elementi iz intervala (-Inf, A)
// - u intervalu pozicija [l, i) su elementi iz intervala [A, B]
// - u intervalu pozicija [i, d) su jos neispitani elementi
// - u intervalu pozicija [d, n) su elementi iz intervala (B, Inf)
int l = 0, i = 0, d = niz.size();
// dok god postoje neispitani elementi
while (i < d) {
if (niz[i] < A)
// menjamo tekuci element sa prvim elementom iz intervala [A, B]
swap (niz[i++], niz[l++]);
else if (niz[i] <= B)
// tekuci element ostaje na svom mestu
i++;
else
// menjamo tekuci element sa poslednjim neispitanim
swap(niz[i], niz[--d]);
}
}
// ispis elemenata vektora na standardni izlaz
void ispisNiza(const vector<int>& a, int A, int B) {
int i = 0;
// ispisujemo elemente iz intervala (-Inf, A)
while (i < a.size() && a[i] < A)
cout << a[i++] << " ";
cout << endl;
// ispisujemo elemente iz intervala [A, B]
while (i < a.size() && a[i] <= B)
cout << a[i++] << " ";
cout << endl;
// ispisujemo elemente iz intervala (B, +Inf)
while (i < a.size())
cout << a[i++] << " ";
cout << endl;
}
int main() {
// ucitavamo elemente niza
vector<int> a = unosNiza();
// ucitavamo interval [A, B]
int A, B;
cin >> A >> B;
// reorganizujemo elemente po intervalima (-inf, A), [A, B] i [B, inf)
podelaNiza(a, A, B);
// ispisujemo elemente niza
ispisNiza(a, A, B);
return 0;
}