Problem nacionalne zastave Holandije
| Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
Problem nacionalne zastave Holandije je poznati problem u računarstvu, vezan za programiranje, koji je uveo Edsger Dijkstra. Zastava Holandije se sastoji iz tri boje: crvena, plava i bela. Date su lopte u ove tri boje (broj lopti nije bitan), a zadatak je poređati lopte tako da su iste boje jedne do drugih, i da su poređane baš u onom redosledu kao na zastavi.
Slučaj niza уреди
Problem se može posmatrati u smislu promene redosleda elemenata niza. Pretpostavimo da se svaki od mogućih elemenata može klasifikovati u tačno jednu od tri kategorije (dno, sredina i vrh). Na primer, ako su svi elementi u opsegu od 0 do 1, dno se može definisati tako da ga čine elementi koji su u opsegu od 0 do 0.1 (ne uključujući 0.1), sredinu definišemo elementima u opsegu od 0.1 do 0.3, dok vrh čine elementi koji su veći od 0.3. (Izbor ovih vrednosti ilustruje da kategorije ne moraju biti jednakih opsega.) Problem je, onda, napraviti niz takav da svi elementi iz kategorije „dno“ dolaze ispred (imaju indeks manji od) elemenata iz sredine, koji dolaze ispred elemenata sa vrha. Ovo treba postići tako da se element koji je ubačen u niz, više ne pomera do kraja sortiranja.
Jedan algoritam je da imamo elemente sa vrha koji se spuštaju sa vrha niza, elemente sa dna koji se podižu sa dna niza, i da zadržimo elemente iz sredine baš iznad elemenata sa dna. Algoritam čuva indekse sledećih lokacija: tačno ispod elemenata sa vrha, tačno iznad elemenata sa dna i tačno iznad elemenata iz sredine. U svakom koraku, ispituje se element tačno iznad sredine niza. Ako on pripada vrhu, onda ga zamenjujemo sa elementom koji je tačno ispod vrha (tj. sa elementom koji ima odgovarajući indeks koji smo ranije sačuvali). Ako on pripada dnu, onda ga menjamo sa elementom koji je tačno iznad dna. Ako pripada sredini, ne menjamo ništa. Zatim se ažuriraju odgovarajući indeksi. Algoritam ima vremensku i prostornu složenost O(n).
Koristi se algoritam brzog sortiranja (енгл. quicksort) za particionisanje elemenata, tako da pivot bude jednak elementima iz sredine, čime se izbegava kasnije premeštanje elemenata koji su jednaki pivotu.
Primer implementacije u C++ - u:
void threeWayPartition(int data[], int size, int low, int high) {
int p = -1;
int q = size;
for (int i = 0; i < q;) {
if (data[i] == low) {
swap(data[i], data[++p]);
++i;
} else if (data[i] >= high) {
swap(data[i], data[--q]);
} else {
++i;
}
}
}
Primer implementacije u Javi:
public class DutchNationalFlag {
public static void dutchFlagSort(int[] arr, int p, int k) {
int p_index = 0;
int k_index = arr.length - 1;
for (int i = 0; i <= k_index;) {
if (arr[i] == p) {
swap(arr, i, p_index);
p_index++;
i++;
}
else if (arr[i] >= k) {
swap(arr, i, k_index);
k_index--;
}
else {
i++;
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}