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](https://docx.uz/documents/6795c8b6-2826-48e3-b4d4-90c3385b7449/page_4.png?v=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];](https://docx.uz/documents/6795c8b6-2826-48e3-b4d4-90c3385b7449/page_5.png?v=1)
![inputArray[p] = inputArray[end];
inputArray[end] = temp;
end--;
}
}
return inputArray;
}
}
Eslatma: ushbu algoritm uchta noyob elementga ega bo'lgan massivda amalga
oshirilishi mumkin.](https://docx.uz/documents/6795c8b6-2826-48e3-b4d4-90c3385b7449/page_6.png?v=1)
![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](https://docx.uz/documents/6795c8b6-2826-48e3-b4d4-90c3385b7449/page_7.png?v=1)
![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);](https://docx.uz/documents/6795c8b6-2826-48e3-b4d4-90c3385b7449/page_8.png?v=1)
![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]ʻ](https://docx.uz/documents/6795c8b6-2826-48e3-b4d4-90c3385b7449/page_9.png?v=1)
![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](https://docx.uz/documents/6795c8b6-2826-48e3-b4d4-90c3385b7449/page_10.png?v=1)
![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](https://docx.uz/documents/6795c8b6-2826-48e3-b4d4-90c3385b7449/page_11.png?v=1)
![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](https://docx.uz/documents/6795c8b6-2826-48e3-b4d4-90c3385b7449/page_12.png?v=1)
![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;](https://docx.uz/documents/6795c8b6-2826-48e3-b4d4-90c3385b7449/page_13.png?v=1)
![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: ";](https://docx.uz/documents/6795c8b6-2826-48e3-b4d4-90c3385b7449/page_14.png?v=1)
![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]);](https://docx.uz/documents/6795c8b6-2826-48e3-b4d4-90c3385b7449/page_18.png?v=1)
![// 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](https://docx.uz/documents/6795c8b6-2826-48e3-b4d4-90c3385b7449/page_19.png?v=1)
![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;
}
}](https://docx.uz/documents/6795c8b6-2826-48e3-b4d4-90c3385b7449/page_20.png?v=1)
Niderlandiya bayrog‘i masalasi asosida saralash