Постоји неколико начина да се низ “у месту” трансформише само једним проласком кроз низ (ти приступи имају линеарну временску сложеност). Приказаћемо неколико могућности, све засноване на техници два показивача.
Претпоставићемо да су у сваком кораку петље познати индекси \(l\) и \(d\) тако да су елементи низа груписани тако да су:
Инваријанта је, дакле, да је распоред елемената у низу облика ppp???nnn, где су l и d позиција првог тј. последњег непознатог елемента (обележеног упитником).
На почетку иницијализујемо \(l\) на нулу, а \(d\) на \(n-1\) (тада су интервали \([0, l)\) и \((d, n)\) празни, а сви елементи у интервалу \([l, d] = [0, n-1]\) су још непрегледани). Петљу у приниципу извршавамо док још има непрегледаних елемената тј. док је \(l \leq d\), међутим, у овом задатку можемо је завршити и корак раније. Петља се извршава док је \(l < d\) и завршава када је \(l=d\), јер какав год да је тај последњи непрегледани елемент на позицији \(l=d\), он ће се моћи припојити или левом или десном делу низа и неће бити потребе премештати га.
У телу петље радимо следеће:
Прво испитујемо да ли је елемент на позицији \(l\) паран и ако јесте, онда само увећавамо вредност \(l\) за 1.
У супротном, проверавамо да ли је елемент на позицији \(d\) непаран и ако јесте, онда само умањујемо вредност \(d\) за 1.
На крају, ако ниједна од претходне две провере није успела, знамо да је елемент на позицији \(l\) непаран, а елемент на позицији \(d\) паран, размењујемо их, увећавамо \(l\) за 1 и умањујемо \(d\) за 1.
Када се петља заврши, елементи су у жељеном редоследу.
Пример. Прикажимо рад алгоритма на једном примеру.
l d 3 8 7 4 5 1 6 2 l d 2 8 7 4 5 1 6 3 l d 2 8 7 4 5 1 6 3 l d 2 8 6 4 5 1 7 3 l d 2 8 6 4 5 1 7 3 ld 2 8 6 4 5 1 7 3
Имплементација се може направити на следећи начин.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// ubrzavamo ucitavanje i ispis
ios_base::sync_with_stdio(false);
// ucitavamo niz
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// odrzavamo uslov
// [0, l) - parni
// (d, n) - neparni
// [l, d] - nepoznati
// u pocetku su svi nepoznati
int l = 0, d = n-1;
// dok jos ima nepoznatih elemenata
while (l < d) {
// ako je na mestu l paran, ostavljamo ga na svom mestu i pomeramo
// se na naredni element
if (a[l] % 2 == 0)
l++;
// ako je na mestu d neparan, ostavljamo ga na svom mestu i
// pomeramo se na prethodni element
else if (a[d] % 2 != 0)
d--;
else
// na mestu l je neparan, a na mestu d je paran broj, pa ih
// razmenjujemo i pomeramo se po oba kraja
swap(a[l++], a[d--]);
}
// ispisujemo rezultat
for (int i = 0; i < n; i++)
cout << a[i] << endl;
}Сложеност. Променљива l се увећава, а променљива d се умањује све док се не сусретну, што се догађа у тачно \(n\) корака, па је укупна сложеност алгоритма \(O(n)\).
Доказ коректности. Докажимо и формално коректност претходног алгоритма. Током извршавања важи раније описана инваријанта, а важи и да је \(0 \leq l \leq d + 1 \leq n\).
Иницијализацијом вредности \(l\) на нулу, а вредности \(d\) на \(n-1\) постижемо да су ови услови на почетку задовољени (јер су сви елементи у интервалу \([l, d] = [0, n-1]\) још непрегледани).
У телу петље радимо следеће:
Прво испитујемо да ли је елемент на позицији \(l\) паран и ако јесте, онда само увећавамо вредност \(l\) за 1 чиме наметнута инваријанта остаје да важи. Заиста, парни су били сви елементи из интервала \([0, l)\), паран је и елемент на позицији \(l\), па су парни сви елементи из интервала \([0, l] = [0, l')\), где је \(l'=l+1\), нова вредност променљиве \(l\). Пошто је \(d'=d\), елементи на позицијама из интервала \((d', n)\) су непарни.
У супротном, проверавамо да ли је елемент на позицији \(d\) непаран и ако јесте, онда само умањујемо вредност \(d\) за 1 чиме наметнута инваријанта опет остају на снази (аргументација је слична оној у претходном случају).
На крају, ако ниједна од претходне две провере није успела, знамо да је елемент на позицији \(l\) непаран, а елемент на позицији \(d\) паран, размењујемо их, увећавамо \(l\) за 1 и умањујемо \(d\) за 1 чиме инваријанта остаје да важи. Заиста, важи да је \(l'=l+1\) и \(d'=d-1\). Сви елементи из интервала позиција \([0, l)\) су парни, а паран је елемент на позицији \(l\) (јер је разменом паран елемент са позиције \(d\) доведен на позицију \(l\)). Зато су парни сви елементи у интервалу \([0, l')\). Слично, пошто су сви елементи у интервалу позиција \((d, n)\) били непарни, а пошто је након размене непарни елемент са позиције \(l\) доведен на позицију \(d\), непарни су и сви елементи из интевала \((d', n)\).
Када се петља заврши, распоред је коректан. Наиме, пошто на крају петље услов \(l < d\) није испуњен, а пошто је \(l \leq d + 1\), тада је \(l=d\) или је \(l=d+1\).
Ако је \(l=d+1\), знамо да је низ разбијен на сегмент парних елемената на позицијама \([0, l)\) и непарних на позицијама \((d, n) = [d+1, n) = [l, n)\).
Размотримо случај \(l=d\).
Ако је елемент на позицији \(l\) паран, пошто су на основу инваријанте парни и сви елементи на позицијама \([0, l)\), знамо да ће парни бити сви елементи на позицијама \([0, l]\), док ће елементи на позицијама \((d, n) = [l+1, n)\) бити непарни.
Слично, ако је елемент на позицији \(l\) непаран, тада су парни сви елементи на позицијама \([0, l)\), а непарни су сви елементи на позицијама \([l, n)\) (јер на основу инваријанте знамо да су још непарни и елементи на позицијама \((d, n) = (l, n)\)).
У оба случаја је, дакле, постигнут жељени распоред елемената.
Приметимо да смо прекидом петље када је \(l=d\), уштедели једну итерацију петље (што није нарочито значајно), али смо закомпликовали доказ коректности, па се природно поставља питање колико је та оптимизација имала смисла.
У овом решењу инваријанта је мало другачија. Памтимо индекс \(k\) и текући индекс \(i\) и претпостављамо да су
Дакле, намећемо инваријанту да је распоред облика pppnnn???, где је \(i\) позиција првог непознатог, а \(k\) позиција првог непарног елемената.
Размотримо како да из инваријанте закључимо како треба иницијализовати променљиве. Пошто су сви елементи из интервала \([i, n)\) непрегледани, променљиву \(i\) морамо инцијализовати на 0. Пошто су сви елементи из интервала \([0, k)\) парни, а \([k, i)\) непарни, и \(k\) морамо поставити на \(0\).
Инваријанта јасно диктира и услов петље. Наиме, петља се извршава док још има непрегледаних елемената тј. док је \(i < n\). У сваком кораку петље \(i\) се увећава за 1 (користимо класичну бројачку петљу for по променљивој \(i\)), чиме се сужава интервал непрегледаних елемената.
Размотримо како треба да изгледа тело петље да би инваријанта остала испуњена.
Ако је елемент на текућој позицији \(i\) паран, онда га размењујемо са првим непарним елементом, а то је елемент на позицији \(k\). Изузетак је случај када је \(k=i\), када заправо не долази до размене (елемент се мења сам са собом). У оба случаја се \(k\) увећава за 1.
У супротном, елемент на позицији \(i\) је непаран он остаје на свом месту и у телу петље није потребно ништа урадити (грану else у коду није потребно наводити).
Пример. Прикажимо рад алгоритма на једном примеру.
k n 3 8 7 4 5 1 6 2 i k n 3 8 7 4 5 1 6 2 i k n 8 3 7 4 5 1 6 2 i k n 8 3 7 4 5 1 6 2 i k n 8 4 7 3 5 1 6 2 i k n 8 4 7 3 5 1 6 2 i k n 8 4 7 3 5 1 6 2 i k n 8 4 6 3 5 1 7 2 i k n 8 4 6 2 5 1 7 3 i
Имплементација се може направити на следећи начин.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// ubrzavamo ucitavanje i ispis
ios_base::sync_with_stdio(false);
// ucitavamo elemente niza
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// odrzavamo uslov
// [0, k) - parni
// [k, i) - neparni
// [i, n) - nepoznati
// u pocetku su svi elementi nepoznati
int k = 0;
for (int i = 0; i < n; i++)
// ako je element paran razmenjujemo ga sa prvim neparnim
if (a[i] % 2 == 0)
swap(a[i], a[k++]);
// a ako je neparan, ne pomeramo ga
// ispisujemo rezultat
for (int i = 0; i < n; i++)
cout << a[i] << endl;
}Сложеност. У програму се користи класична бројачка петља for која се завршава у \(n\) корака, па је укупна сложеност алгоритма \(O(n)\).
Доказ коректности. Докажимо и формално коректност претходног поступка. Уз описану инваријанту важи и да је \(0 \leq k \leq i \leq n\).
Пошто је на почетку \(i=k=0\), важи да су сви елементи у интервалу \([i, n) = [0, n)\) непрегледани. Интервали \([0, k) = [k, i) = [0, 0)\) су празни, па задовољавају услове, а тривијално важи и да је \(0 \leq k \leq i \leq n\).
У телу петље се врше следеће акције.
Ако је елемент на текућој позицији \(i\) паран, онда га размењујемо са првим непарним елементом, а то је елемент на позицији \(k\). Изузетак је случај када је \(k=i\), када заправо не долази до размене (елемент се мења сам са собом). У оба случаја се \(k\) увећава за 1. Дакле, на основу инваријанте знамо да су елементи на позицијама \([0, k)\) парни, да је након размене елемент на позицији \(k\) паран, па су парни и сви елементи на позицијама \([0, k') = [0, k+1)\). Елементи на позицијама \([k', i') = [k+1, i+1)\) су непарни. Наиме, ако је \(k=i\), овај интервал је празан, а ако је \(k < i\), тада је пре размене елемент на позицији \(k\) био непаран (јер на основу инваријанте знамо да су сви елементи на позицијама \([k, i)\) били непарни, па самим тим и елемент на позицији \(k\), који је сада доведен на позицију \(i\)).
У супротном, елемент на позицији \(i\) је непаран он остаје на свом месту. Пошто се у телу петље не дешава ништа, а након петље се бројач i увећава, важи \(k'=k\) и \(i'=i+1\), а инваријанта прилично очигледно остаје на снази (јер је \([k', i') = [k, i]\), елементи на позицијама \([k, i)\) су непарни, а непаран је и елемент на позицији \(i\)).
По завршетку петље услов \(i < n\) није испуњен, па пошто на основу инваријанте важи \(0 \leq k \leq i \leq n\), важи да је \(i = n\). Зато је интервал непознатих \([i, n)\) празан, сви елементи из интервала \([0, k)\) су парни, из интервала \([k, i) = [k, n)\) су непарни и постигнут је тражени распоред.
Заустављање се једноставно доказује јер се у сваком кораку сужава интервал непознатих \([i, n)\).