Проблем националне заставе Холандије
| Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
Проблем националне заставе Холандије је познати проблем у рачунарству, везан за програмирање, који је увео Едсгер Дијкстра. Застава Холандије се састоји из три боје: црвена, плава и бела. Дате су лопте у ове три боје (број лопти није битан), а задатак је поређати лопте тако да су исте боје једне до других, и да су поређане баш у оном редоследу као на застави.
Случај низа уреди
Проблем се може посматрати у смислу промене редоследа елемената низа. Претпоставимо да се сваки од могућих елемената може класификовати у тачно једну од три категорије (дно, средина и врх). На пример, ако су сви елементи у опсегу од 0 до 1, дно се може дефинисати тако да га чине елементи који су у опсегу од 0 до 0.1 (не укључујући 0.1), средину дефинишемо елементима у опсегу од 0.1 до 0.3, док врх чине елементи који су већи од 0.3. (Избор ових вредности илуструје да категорије не морају бити једнаких опсега.) Проблем је, онда, направити низ такав да сви елементи из категорије „дно“ долазе испред (имају индекс мањи од) елемената из средине, који долазе испред елемената са врха. Ово треба постићи тако да се елемент који је убачен у низ, више не помера до краја сортирања.
Један алгоритам је да имамо елементе са врха који се спуштају са врха низа, елементе са дна који се подижу са дна низа, и да задржимо елементе из средине баш изнад елемената са дна. Алгоритам чува индексе следећих локација: тачно испод елемената са врха, тачно изнад елемената са дна и тачно изнад елемената из средине. У сваком кораку, испитује се елемент тачно изнад средине низа. Ако он припада врху, онда га замењујемо са елементом који је тачно испод врха (тј. са елементом који има одговарајући индекс који смо раније сачували). Ако он припада дну, онда га мењамо са елементом који је тачно изнад дна. Ако припада средини, не мењамо ништа. Затим се ажурирају одговарајући индекси. Алгоритам има временску и просторну сложеност О(н).
Користи се алгоритам брзог сортирања (енгл. quicksort) за партиционисање елемената, тако да пивот буде једнак елементима из средине, чиме се избегава касније премештање елемената који су једнаки пивоту.
Пример имплементације у C++ - у:
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;
}
}
}
Пример имплементације у Јави:
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;
}
}