Niderlandiya bayrog’i masalasi asosida saralash
![tekshiriladi. Agar u yuqori qismga tegishli bo'lsa, biz uni yuqoridan pastroqdagi
element bilan almashtiramiz (ya'ni, biz avval saqlangan tegishli indeksga ega
bo'lgan element bilan). Agar u pastki qismga tegishli bo'lsa, biz uni pastki qismdan
yuqorida joylashgan element bilan almashtiramiz. Agar u o'rtaga tegishli bo'lsa, biz
hech narsani o'zgartirmaymiz. Keyin tegishli indekslar yangilanadi. Algoritm vaqt
va makon murakkabligi O(n)ga ega.
Tez tartiblash algoritmi qo'llaniladi . Quicksort elementlarni aylanma
o rtadagi elementlarga teng bo lishi uchun qismlarga bo lish uchun, bu esaʻ ʻ ʻ
keyinchalik burilishga teng bo lgan elementlarni siljitishning oldini oladi.
ʻ
1.2.Niderlandiya bayrog’i muammosi.
C++ Niderlandiya milliy bayrog'i muammosi.Gollandiya milliy bayrog'i (DNF)
muammosi Edsger Dijkstra tomonidan taklif qilingan eng mashhur dasturlash
muammolaridan biridir. Gollandiya bayroq algoritmi (DFA) massivlar uchun eng
asosiy va muhim algoritmlardan biridir. U chiziqli vaqt murakkabligida 3 ta
raqamdan iborat massivni ajratish uchun ishlatiladi.DFA uchun eng yomon vaqt
murakkabligi O(n) va algoritm uchun fazoviy murakkablik O(1) dir. Niderlandiya
bayrog'i uchta rangdan iborat: oq, qizil va ko'k. Vazifa oq, qizil va ko'k rangli
to'plarni tasodifiy tartibga solishdir, shunda bir xil rangdagi to'plar bir-biriga
joylashtiriladi. Nolga asoslangan massiv indeksatsiyasini nazarda tutuvchi uch
tomonlama bo linish uchun quyidagi psevdokod Dijkstraning o zi tomonidan taklif
ʻ ʻ
qilingan. [2] U i ≤ j ≤ k invariantini saqlab, uchta i , j va k indekslaridan
foydalanadi .
0 dan (lekin shu jumladan emas) i gacha bo'lgan yozuvlar o'rtadan kichik
qiymatlardir ,
i dan (lekin shu jumladan emas) j gacha bo'lgan yozuvlar mid ga teng
qiymatlardir ,
j dan (shu jumladan) k gacha yozuvlar hali tartiblanmagan qiymatlar va
k + 1 dan massivning oxirigacha bo'lgan yozuvlar o'rtadan kattaroq qiymatlardir .
Eslatma: ushbu algoritm uchta noyob elementga ega bo'lgan massivda amalga
oshirilishi mumkin.
procedure three-way-partition(A : array of values, mid : value):
i ← 0
j ← 0
k ← size of A - 1
while j <= k:
if A[j] < mid:
swap A[i] and A[j]
i ← i + 1
j ← j + 1
else if A[j] > mid:
swap A[j] and A[k]
k ← k - 1](/data/documents/1def6a15-99a4-4256-b351-6ac86b36b030/page_4.png)
![else:
j ← j + 1
1.3.Niderlandiya bayrog’i algoritmi.
Gollandiyalik bayroq algoritmi (DFA) massivlar uchun eng asosiy va muhim
algoritmlardan biridir. U chiziqli vaqt murakkabligida 3 ta raqamdan iborat
massivni ajratish uchun ishlatiladi.DFA uchun eng yomon vaqt murakkabligi O(n)
va algoritm uchun fazoviy murakkablik O(1) dir. Muammo bayonoti quyidagicha:
Sizga 0, 1 va 2 dan iborat massiv taqdim etiladi. Vazifa barcha raqamlarni bir-
biriga ajratadigan funktsiyani yozishdir. Buyurtma har qanday bo'lishi mumkin.
Faraz qilaylik, taqdim etilgan A massivi
A = [1, 2, 0, 1, 2, 0, 1, 2, 0]
va kutilgan natija
A = [2, 2, 2, 0, 0, 0, 1” , 1, 1]
Muammoni hal qilish uchun birinchi navbatda buyurtmani tanlashimiz
kerak. Bu misol uchun 2,1,0 ni tanlaymiz. Endi biz massivning uch xil indeksini
ko'rsatuvchi
3 ta ko'rsatkichga ega bo'lishimiz kerak, ya'ni start, end va P .Boshlanish o'rta
elementning birinchi indeksini, ya'ni bu erda 0 ni bildiradi . End o'rta elementning
oxirgi indeksini bildiradi va P ko'rsatkichi massivni aylanib o'tish uchun ishlatiladi.
P belgisi End ga teng bo'lmaganda tsikl ishlaydi . P harakatlanayotganda, agar P 2
ga duch kelsa, u uni start bilan almashtiradi va startni oshiradi. Xuddi shunday,
agar P 1 ga duch kelsa, u uni oxiri va kamaytiruvchi uchi bilan almashtiradi
C++ dasturlash tilida qisqacha dasturyiy qism
public class DutchFlagAlgorithm {
public int[] dutchFlagAlgorithm(int[] inputArray, int size) {
int start = 0;
int p = 0;
int end = size - 1;
int temp;
while (p < end) {
if (inputArray[p] == 2) {
temp = inputArray[p];
inputArray[p] = inputArray[start];
inputArray[start] = temp;
start++;
p++;
} else if (inputArray[p] == 0) {
p++;
} else {
temp = inputArray[p];](/data/documents/1def6a15-99a4-4256-b351-6ac86b36b030/page_5.png)
![inputArray[p] = inputArray[end];
inputArray[end] = temp;
end--;
}
}
return inputArray;
}
}
Eslatma: ushbu algoritm uchta noyob elementga ega bo'lgan massivda amalga
oshirilishi mumkin.](/data/documents/1def6a15-99a4-4256-b351-6ac86b36b030/page_6.png)
![II Bob. Niderlandiya bayrog’i masalasini algoritmlar orqali saralash
2.1.QuikSort(Niderlandiya davlat bayrog’i).
Oddiy QuickSort algoritmida biz elementni pivot sifatida tanlaymiz,
massivni pivot atrofida ajratamiz va pivotning chap va o'ng tomonidagi pastki
qatorlar uchun takrorlaymiz.
Ko'p ortiqcha elementlarga ega massivni ko'rib chiqamizs. Masalan, {1, 4, 2,
4, 2, 4, 1, 2, 4, 1, 2, 2, 2, 2, 4, 1, 4, 4, 4}. Agar Simple Tezkor saralashda pivot
sifatida 4 tanlansa, biz faqat bitta 4 ni tuzatamiz va qolgan hodisalarni rekursiv
qayta ishlaymiz.3 usulli Tez tartiblash g‘oyasi pivotning barcha hodisalarini qayta
ishlashdan iborat bo‘lib, Gollandiya milliy bayrog‘i algoritmiga asoslangan.
3 Way QuickSort-da arr[l..r] massivi
3 qismga bo'linadi:
a) arr[l..i] elementlar pivotdan kichik.
b) pivotga teng arr[i+1..j-1] elementlar.
c) arr[j..r] elementlar pivotdan katta.
Quyida yuqoridagi algoritmni amalga oshirish dasturini ko’rsatilgan.
// 3 tomonlama tez saralash .C++ dasturida
#include <bits/stdc++.h>
using namespace std;
/* bu funksiya massivni 3 qismga ajratadi
a) a[l..i] pivotdan kichikroq bo’lgan barcha elementlarni o’z ichiga oladi
b) a[i+1..j-1] pivotni barcha hodisalarinin o’z ichiga oladi
c) a[j..r] pivotdan kattaroq barcha elementlarni o’z ichiga oladi*/
void partition(int a[], int l, int r, int& i, int& j)
{
i = l - 1, j = r;
int p = l - 1, q = r;
int v = a[r];
while (true) {
//chapdan kataroq birinchi elementni olamiz.
//yoki v ga teng.Bu sikl albatta bo’ladi.
//v oxirgi element sifatida tugating.
while (a[++i] < v);
//O’ngdan kichikroq bo’lgan birinchi elementni toping
// yoki v ga teng
while (v < a[--j])
if (j == l)
break;
// Agar i va j kesishgan bo’lsa quyidagi funksiya bajariladi](/data/documents/1def6a15-99a4-4256-b351-6ac86b36b030/page_7.png)
![if (i >= j)
break;
// Swap shunday qilib chapga ketadi
//kataroq bo’lsa o’nga
swap(a[i], a[j]);
// pivotning chap ko’rinishini birxil joyga o’tkazish
//masivning boshi va p yordamida hisoblashni davom etiring
if (a[i] == v) {
p++;
swap(a[p], a[i]);
}
// pivotning bir xilo’nga ko’rinishini oxirigacha o’tkazish
//massiv va q yordamida hisoblashni davom etirish
if (a[j] == v) {
q--;
swap(a[j], a[q]);
}
}
// Asosiy elementni to’g’ri indeksga o’tqazing
swap(a[i], a[r]);
// Barcha chapdagi bir xil elementlarni boshidan siljitish
j = i - 1;
for (int k = l; k < p; k++, j--)
swap(a[k], a[j]);
// Barcha chapdagi bir xil elementlarni boshidan ko’chirish
// arr[i] ga ulashgan
i = i + 1;
for (int k = r - 1; k > q; k--, i++)
swap(a[i], a[k]);
}
// 3-tomonlama bo’limga asoslangan tezkor tartiblash void quicksort(int a[],
int l, int r)
void quicksort(int a[], int l, int r)
{
if (r <= l)
return;
int i, j;
quicksort(a, l, j);](/data/documents/1def6a15-99a4-4256-b351-6ac86b36b030/page_8.png)
![quicksort(a, i, r);
}
// masivni chop etish uchun funksiya
void printarr(int a[], int n)
{
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
}
// Asosiy funksiya
int main()
{
int a[] = { 4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4 };
int size = sizeof(a) / sizeof(int);
// Funksiya chaqiruvchi
printarr(a, size);
quicksort(a, 0, size - 1);
printarr(a, size);
return 0;
}
Dasturning natijasi
4 9 4 4 1 9 4 4 9 4 4 1 4
1 1 4 4 4 4 4 4 4 4 9 9 9
Dasturning vaqt murakabligi: O(N * log(N))
Bu erda "N" - berilgan massiv/ro'yxatdagi elementlar soni
Tezkor saralash funksiyasiga qilingan rekursiv qo'ng'iroqlarning o'rtacha
soni log N dir va funksiya har safar chaqirilganda biz O(N) vaqtini talab qiladigan
berilgan massiv/ro'yxat bo'ylab o'tamiz. Shunday qilib, umumiy vaqt murakkabligi
O (N * log (N)).
Kosmik murakkablik: O(log N)
Bu erda "N" - berilgan massiv/ro'yxatdagi elementlar soni.
2.2.Ko’rsatkich yondashuvi
Pointer yondashuvidan foydalanib, 0s, 1s va 2s massivini tartiblash:
Ushbu yondashuv quyidagi fikrga asoslanadi:’
Muammo "massivdagi 0 va 1 larni ajratish" ga o'xshaydi .
Muammo uchta rang bilan qo'yildi;
bu erda "0", "1" va "2".
Massiv to'rt qismga bo'lingan:
arr[1] to arr[past – 1]
arr[past] to arr[o rtasi – 1]ʻ](/data/documents/1def6a15-99a4-4256-b351-6ac86b36b030/page_9.png)
![arr[o’rta] to arr[yuqori – 1]
arr[yuqori] to arr[n]
Agar i element 0 bo'lsa, elementni past diapazonga almashtiring.
Xuddi shunday, agar element 1 bo'lsa, uni avvalgidek saqlang.
Agar element 2 bo'lsa, uni yuqori diapazondagi element bilan almashtiring.
Tasvir:
arr[] = {0, 1, 2, 0, 1, 2}
lo = 0, o'rta = 0, salom = 5
1-qadam: arr[o’rta] == 0
almashtirish(arr[lo],arr[o’rta])
lo = lo + 1 = 1
o'rta = o'rta + 1 = 1
arr[] = {0, 1, 2, 0, 1, 2}
1–rasm
2-qadam: arr[o’rta] == 1
o'rta = o'rta + 1 = 2
arr[] = {0, 1, 2, 0, 1, 2}
2–rasm
3-qadam: arr[o’rta] == 2](/data/documents/1def6a15-99a4-4256-b351-6ac86b36b030/page_10.png)
![almashtirish(arr[o’rta],arr[salom])
salom = salom – 1 = 4
arr[] = {0, 1, 2, 0, 1, 2}
3–rasm
4-qadam: arr[o’rta] == 2
almashtirish(arr[o’rta],arr[salom])
salom = salom – 1 = 3
arr[] = {0, 1, 1, 0, 2, 2}
4–rasm
5-qadam: arr[o’rta] == 1
o'rta = o'rta + 1 = 3
arr[] = {0, 1, 1, 0, 2, 2}
5–rasm
6-qadam: arr[o’rta] == 0
almashtirish(arr[lo],arr[o’rta])
lo = lo + 1 = 2](/data/documents/1def6a15-99a4-4256-b351-6ac86b36b030/page_11.png)
![o'rta = o'rta + 1 = 4
arr[] = {0, 0, 1, 1, 2, 2}
6–rasm
Demak arr[]={0,0,1,1,2,2}
Berilgan muammoni hal qilish uchun quyidagi amallarni bajaring:Uchta
indeksni past = 1, o'rta = 1 va yuqori = N saqlang va to'rtta diapazon mavjud: 1 dan
pastgacha (diapazon 0 ni o'z ichiga oladi), pastdan o'rtaga (diapazon 1 ni o'z ichiga
oladi), o'rtadan yuqoriga (noma'lum elementlarni o'z ichiga olgan diapazon) ) va N
gacha baland (2 ni o'z ichiga olgan diapazon).
Massivni boshidan oxirigacha aylantiring va o'rtasi balanddan kamroq.
(Loop hisoblagichi i)
Agar element 0 bo'lsa, elementni pastki indeksdagi element bilan
almashtiring va past = past + 1 va o'rta = o'rta + 1 ni yangilang
Agar element 1 bo'lsa, o'rta = o'rta + 1 ni yangilang
Agar element 2 bo'lsa, elementni yuqori indeksdagi element bilan
almashtiring va yuqori = yuqori - 1 ni yangilang va i = i - 1 ni yangilang.
Almashtirilgan element qayta ishlanmagani uchun
Massivni chop eting.
C++ dasturida masivni saralash
0, 1 va 2 bilan bita o’tish
#include <bits/stdc++.h>
using namespace std;
// kirish massivini saralash funksiyasi
//massiv qabul qilinadi
// qiymatlarga ega bo’lish{0, 1, 2}
void sort012(int a[], int arr_size)
{
int lo = 0;
int hi = arr_size - 1;
int mid = 0;
// barca iteratorlarga qadar takrorlash va
// tartiblash
while (mid <= hi) {
switch (a[mid]) {
// Agar element 0 bo’lsa](/data/documents/1def6a15-99a4-4256-b351-6ac86b36b030/page_12.png)
![case 0:
swap(a[lo++], a[mid++]);
break;
// Agar element 1 bo’lsa .
case 1:
mid++;
break;
// Agar element 2 bo’lsa
case 2:
swap(a[mid], a[hi--]);
break;
}
}
}
// Masivnbi chob etish funksiyasi;
void printArray(int arr[], int arr_size)
{
// har bir elementni takrorlash va chop etish
for (int i = 0; i < arr_size; i++)
cout << arr[i] << " ";
}
// Asosiy funksiya
int main()
{
int arr[] = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
sort012(arr, n);
printArray(arr, n);
return 0;
}
Dasturn natijasi: 0 0 0 0 0 1 1 1 1 1 2 2
Vaqtning murakkabligi: O(n), massivdan faqat bitta o'tish kerak.
Kosmik murakkablik: O (1), qo'shimcha joy talab qilinmaydi.
2.3.Niderlandiya bayrog’i muammosi
Ushbu muammoni massivda ko'rib chiqamiz ; 0, 1 va 2 massivlarni chiziqli
vaqtda hech qanday ortiqcha joysiz saralashdir. Massiv faqat bir marta o'tganligi
sababli, quyida keltirilgan algoritmning vaqt murakkabligi O(n).
Quyidagi kodda kirish massivini saralash uchun uchta indeks ishlatiladi
(ya'ni, low, high, mid) – past ,yuqori,o’rta
C++ tilida kodi:
#include<iostream >
using namespace std;](/data/documents/1def6a15-99a4-4256-b351-6ac86b36b030/page_13.png)
![void DNFS(int arr[], int arr_size)
{
int low = 0;
int high = arr_size - 1;
int mid = 0;
while (mid <= high)
{
switch (arr[mid])
{
case 0:
swap(arr[low], arr[mid]);
break;
case 1:
mid++;
break;
case 2:
swap(arr[mid], arr[high--]);
break;
}
}
}
void printArray(int arr[], int arr_size)
{
for (int i = 0; i < arr_size; i++)
cout << arr[i] << " ";
}
int main()
{
int arr[] = {0,0,1,2,0,1,2};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Array before running the algorithm: ";
printArray(arr, n);
DNFS(arr, n);
cout << "\nArray after DNFS algorithm: ";](/data/documents/1def6a15-99a4-4256-b351-6ac86b36b030/page_14.png)
![ILOVALAR.
1. // 3 tomonlama tez saralash .C++ dasturid
#include <bits/stdc++.h>
using namespace std;
/* bu funksiya massivni 3 qismga ajratadi
a) a[l..i] pivotdan kichikroq bo’lgan barcha elementlarni o’z ichiga oladi
b) a[i+1..j-1] pivotni barcha hodisalarinin o’z ichiga oladi
c) a[j..r] pivotdan kattaroq barcha elementlarni o’z ichiga oladi*/
void partition(int a[], int l, int r, int& i, int& j)
{
i = l - 1, j = r;
int p = l - 1, q = r;
int v = a[r];
while (true) {
//chapdan kataroq birinchi elementni olamiz.
//yoki v ga teng.Bu sikl albatta bo’ladi.
//v oxirgi element sifatida tugating.
while (a[++i] < v);
//O’ngdan kichikroq bo’lgan birinchi elementni toping
// yoki v ga teng
while (v < a[--j])
if (j == l)
break;
// Agar i va j kesishgan bo’lsa quyidagi funksiya bajariladi
if (i >= j)
break;
// Swap shunday qilib chapga ketadi
//kataroq bo’lsa o’nga
swap(a[i], a[j]);
// pivotning chap ko’rinishini birxil joyga o’tkazish
//masivning boshi va p yordamida hisoblashni davom etiring
if (a[i] == v) {
p++;
swap(a[p], a[i]);
}
// pivotning bir xilo’nga ko’rinishini oxirigacha o’tkazish
//massiv va q yordamida hisoblashni davom etirish
if (a[j] == v) {
q--;
swap(a[j], a[q]);
}
}
// Asosiy elementni to’g’ri indeksga o’tqazing
swap(a[i], a[r]);](/data/documents/1def6a15-99a4-4256-b351-6ac86b36b030/page_18.png)
![// Barcha chapdagi bir xil elementlarni boshidan siljitish
j = i - 1;
for (int k = l; k < p; k++, j--)
swap(a[k], a[j]);
// Barcha chapdagi bir xil elementlarni boshidan ko’chirish
// arr[i] ga ulashgan
i = i + 1;
for (int k = r - 1; k > q; k--, i++)
swap(a[i], a[k]);
}
2. // 3-tomonlama bo’limga asoslangan tezkor tartiblash
void quicksort(int a[], int l, int r)
void quicksort(int a[], int l, int r)
{
if (r <= l)
return;
int i, j;
quicksort(a, l, j);
quicksort(a, i, r);
}
// masivni chop etish uchun funksiya
void printarr(int a[], int n)
{
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
}
// Asosiy funksiya
int main()
{
int a[] = { 4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4 };
int size = sizeof(a) / sizeof(int);
// Funksiya chaqiruvchi
printarr(a, size);
quicksort(a, 0, size - 1);
printarr(a, size);
return 0;
}
Dasturning natijasi
4 9 4 4 1 9 4 4 9 4 4 1 4
1 1 4 4 4 4 4 4 4 4 9 9 9](/data/documents/1def6a15-99a4-4256-b351-6ac86b36b030/page_19.png)
![Dasturning vaqt murakabligi: O(N * log(N))
Bu erda "N" - berilgan massiv/ro'yxatdagi elementlar soni
3. #include<iostream>
Using namespace std;
public class DutchFlagAlgorithm {
public int[] dutchFlagAlgorithm(int[] inputArray, int size) {
int start = 0;
int p = 0;
int end = size - 1;
int temp;
while (p < end) {
if (inputArray[p] == 2) {
temp = inputArray[p];
inputArray[p] = inputArray[start];
inputArray[start] = temp;
start++;
p++;
} else if (inputArray[p] == 0) {
p++;
} else {
temp = inputArray[p];
inputArray[p] = inputArray[end];
inputArray[end] = temp;
end--;
}
}
return inputArray;
}
}](/data/documents/1def6a15-99a4-4256-b351-6ac86b36b030/page_20.png)
Mavzu: “Niderlandiya bayrog’i masalasi asosida saralash” MUNDARIJA KIRISH ............................................................................................................ 2 I Bob. Niderlandiya bayrog’i masalasi ............................................................ 3 1.1 Niderlandiya bayrog’ini saralash ......................................................... 3 1.2.Niderlandiya bayrog’i muammosi. ...................................................... 4 1.3.Niderlandiya bayrog’i algoritmi. ......................................................... 5 II Bob. Niderlandiya bayrog’i masalasini algoritmlar orqali saralash ............ 7 2.1.QuikSort(Niderlandiya davlat bayrog’i). ............................................ 7 2.2.Ko’rsatkich yondashuvi ....................................................................... 9 2.3.Niderlandiya bayrog’i muammosi ..................................................... 13 XULOSA ................................................................................................. 16 ADABIYOTLAR RO’YXATI ................................................................ 17 ILOVALAR. ............................................................................................ 18
KIRISH Hozirgi zamonaviy texnologiyalar davrida axborot texnologiyalariga bo’lgan talabning ortib borishi natijasida, axborotlarni tartiblash , saralash va qayta tartiblash algoritmlari ham rivojlanib bormoqda Saralash algoritimlar ichida bayroqlar masalasi ham keltirib o’tilgan. Bayroq masalasi yechish algoritmi ko’p dasturlarda keng qo’llaniladi. Biz Niderlandiya bayrog’i masalasini saralash algoritmini kelib chiqishi haqda o’raganamiz. Niderlandiya bayrog’i saralash algoritmi Amerika bayrog’i bayrog’ning saralash algoritmining sodaroq ko’rinishidir. Niderlandiyaning davlat bayrog'i muammosi Edsger Dijkstra tomonidan kiritilgan dasturlash bilan bog'liq bo'lgan kompyuterda taniqli muammodir .Bunday muamolarni yechish saralash algoritmining loyhalash uchun qiziqish uyg’otadi Niderlandiya bayrog'i uchta rangdan iborat: qizil, ko'k va oq. To'plar ushbu uchta rangda berilgan (to'plar soni muhim emas) va vazifa to'plarni bir-birining yonida bir xil rangda bo'lishi va ular xuddi shu tartibda joylashganligi uchun joylashtirishdir.
I Bob. Niderlandiya bayrog’i masalasi 1.1 Niderlandiya bayrog’ini saralash Nniderlandiya bayrog'ini saralash :: Nniderlandiya bayrog'ini saralash "Amerika bayrog'i " turining soddaroq versiyasi (ixtiyoriy raqamlar o'rniga uchta raqam). Ikki rangli bayroq algoritmi Nniderlandiya isbatan soddalashtirilgan versiyadir. Bu odatiy ma'noda tartiblash emas, balki raqamlarni uchta raqamga taqsimlovchi algoritm: eng kam ahamiyatli raqam - shartli 0, o'rta raqam - shartli 1 va eng muhim raqam - shartli 2. Massiv tugmalariga uchta ko'rsatgich o'rnatilgan. Massivning boshida past va o'rta raqamlarga, oxirida - yuqoriga ko'rsatgichlar mavjud.Keyin massivning elementlari chapdan o'ngga qaraladi. Agar keyingi element eng kam ahamiyatli bitga to'g'ri kelsa, past tartibli ko'rsatgich bir pozitsiya o'ngga siljiydi. Agar keyingi element o'rta raqamga to'g'ri keladigan bo'lsa, u holda almashish o'rta raqam uchun ko'rsatgich tomonidan ko'rsatilgan raqam bilan amalga oshiriladi va o'rta raqamning o'zi bir pozitsiya o'ngga siljiydi. Agar keyingi element eng muhim raqamga to'g'ri keladigan bo'lsa, u holda almashish eng muhim raqamlar uchun ko'rsatgich tomonidan ko'rsatilgan raqam bilan amalga oshiriladi va eng muhim raqamning ko'rsatgichining o'zi bir pozitsiya chapga siljiydi. Niderlandiyaning davlat bayrog'i muammosi Edsger Dijkstra tomonidan kiritilgan dasturlash bilan bog'liq bo'lgan kompyuterda taniqli muammodir . Niderlandiya bayrog'i uchta rangdan iborat: qizil, ko'k va oq. To'plar ushbu uchta rangda berilgan (to'plar soni muhim emas) va vazifa to'plarni bir-birining yonida bir xil rangda bo'lishi va ular xuddi shu tartibda joylashganligi uchun joylashtirishdir. Muammoni massiv elementlarining tartibini o'zgartirish nuqtai nazaridan ko'rish mumkin . Mumkin bo'lgan elementlarning har birini uchta toifadan biriga (pastki, o'rta va yuqori) tasniflash mumkin deb taxmin qiling. Misol uchun, agar barcha elementlar 0 dan 1 gacha bo'lgan oraliqda bo'lsa, pastki qismi 0 dan 0,1 gacha bo'lgan elementlar bilan aniqlanishi mumkin (0,1 dan tashqari), o'rtasi 0,1 dan 1 gacha bo'lgan oraliqdagi elementlar bilan belgilanadi. 0,3, yuqori qismi esa 0,3 dan katta bo'lgan elementlardir. (Ushbu qiymatlarning tanlanishi toifalar teng diapazonda bo lishi shart emasligini ko rsatadi.) Demak, muammo “pastki”ʻ ʻ toifadagi barcha elementlardan oldin keladigan massiv yaratishdir (indeks quyidagidan kichik bo lishi kerak). ) yuqoridagi elementlardan oldin keladigan ʻ o'rtadagi elementlar. Bunga shunday erishish kerakki, massivga kiritilgan element tartiblash oxirigacha boshqa joyga ko'chirilmaydi. Algoritmlardan biri - massivning yuqori qismidan pastga tushadigan yuqori elementlarga, massivning pastki qismidan ko'tariladigan pastki elementlarga ega bo'lish va o'rta elementlarni faqat pastki elementlardan yuqorida tutishdir. Algoritm quyidagi joylarning indekslarini saqlaydi : yuqoridagi elementlardan aniq pastda, pastdan elementlardan yuqorida va o'rtadagi elementlardan to'liq yuqorida. Har bir qadamda massivning o'rtasidan to'liq yuqorida joylashgan element
tekshiriladi. Agar u yuqori qismga tegishli bo'lsa, biz uni yuqoridan pastroqdagi element bilan almashtiramiz (ya'ni, biz avval saqlangan tegishli indeksga ega bo'lgan element bilan). Agar u pastki qismga tegishli bo'lsa, biz uni pastki qismdan yuqorida joylashgan element bilan almashtiramiz. Agar u o'rtaga tegishli bo'lsa, biz hech narsani o'zgartirmaymiz. Keyin tegishli indekslar yangilanadi. Algoritm vaqt va makon murakkabligi O(n)ga ega. Tez tartiblash algoritmi qo'llaniladi . Quicksort elementlarni aylanma o rtadagi elementlarga teng bo lishi uchun qismlarga bo lish uchun, bu esaʻ ʻ ʻ keyinchalik burilishga teng bo lgan elementlarni siljitishning oldini oladi. ʻ 1.2.Niderlandiya bayrog’i muammosi. C++ Niderlandiya milliy bayrog'i muammosi.Gollandiya milliy bayrog'i (DNF) muammosi Edsger Dijkstra tomonidan taklif qilingan eng mashhur dasturlash muammolaridan biridir. Gollandiya bayroq algoritmi (DFA) massivlar uchun eng asosiy va muhim algoritmlardan biridir. U chiziqli vaqt murakkabligida 3 ta raqamdan iborat massivni ajratish uchun ishlatiladi.DFA uchun eng yomon vaqt murakkabligi O(n) va algoritm uchun fazoviy murakkablik O(1) dir. Niderlandiya bayrog'i uchta rangdan iborat: oq, qizil va ko'k. Vazifa oq, qizil va ko'k rangli to'plarni tasodifiy tartibga solishdir, shunda bir xil rangdagi to'plar bir-biriga joylashtiriladi. Nolga asoslangan massiv indeksatsiyasini nazarda tutuvchi uch tomonlama bo linish uchun quyidagi psevdokod Dijkstraning o zi tomonidan taklif ʻ ʻ qilingan. [2] U i ≤ j ≤ k invariantini saqlab, uchta i , j va k indekslaridan foydalanadi . 0 dan (lekin shu jumladan emas) i gacha bo'lgan yozuvlar o'rtadan kichik qiymatlardir , i dan (lekin shu jumladan emas) j gacha bo'lgan yozuvlar mid ga teng qiymatlardir , j dan (shu jumladan) k gacha yozuvlar hali tartiblanmagan qiymatlar va k + 1 dan massivning oxirigacha bo'lgan yozuvlar o'rtadan kattaroq qiymatlardir . Eslatma: ushbu algoritm uchta noyob elementga ega bo'lgan massivda amalga oshirilishi mumkin. procedure three-way-partition(A : array of values, mid : value): i ← 0 j ← 0 k ← size of A - 1 while j <= k: if A[j] < mid: swap A[i] and A[j] i ← i + 1 j ← j + 1 else if A[j] > mid: swap A[j] and A[k] k ← k - 1
else: j ← j + 1 1.3.Niderlandiya bayrog’i algoritmi. Gollandiyalik bayroq algoritmi (DFA) massivlar uchun eng asosiy va muhim algoritmlardan biridir. U chiziqli vaqt murakkabligida 3 ta raqamdan iborat massivni ajratish uchun ishlatiladi.DFA uchun eng yomon vaqt murakkabligi O(n) va algoritm uchun fazoviy murakkablik O(1) dir. Muammo bayonoti quyidagicha: Sizga 0, 1 va 2 dan iborat massiv taqdim etiladi. Vazifa barcha raqamlarni bir- biriga ajratadigan funktsiyani yozishdir. Buyurtma har qanday bo'lishi mumkin. Faraz qilaylik, taqdim etilgan A massivi A = [1, 2, 0, 1, 2, 0, 1, 2, 0] va kutilgan natija A = [2, 2, 2, 0, 0, 0, 1” , 1, 1] Muammoni hal qilish uchun birinchi navbatda buyurtmani tanlashimiz kerak. Bu misol uchun 2,1,0 ni tanlaymiz. Endi biz massivning uch xil indeksini ko'rsatuvchi 3 ta ko'rsatkichga ega bo'lishimiz kerak, ya'ni start, end va P .Boshlanish o'rta elementning birinchi indeksini, ya'ni bu erda 0 ni bildiradi . End o'rta elementning oxirgi indeksini bildiradi va P ko'rsatkichi massivni aylanib o'tish uchun ishlatiladi. P belgisi End ga teng bo'lmaganda tsikl ishlaydi . P harakatlanayotganda, agar P 2 ga duch kelsa, u uni start bilan almashtiradi va startni oshiradi. Xuddi shunday, agar P 1 ga duch kelsa, u uni oxiri va kamaytiruvchi uchi bilan almashtiradi C++ dasturlash tilida qisqacha dasturyiy qism public class DutchFlagAlgorithm { public int[] dutchFlagAlgorithm(int[] inputArray, int size) { int start = 0; int p = 0; int end = size - 1; int temp; while (p < end) { if (inputArray[p] == 2) { temp = inputArray[p]; inputArray[p] = inputArray[start]; inputArray[start] = temp; start++; p++; } else if (inputArray[p] == 0) { p++; } else { temp = inputArray[p];