Javoblar 86. Хасис алгоритм қачон қўлланилади?

Ko’p qadamdan iborat “bo’lib tashla va hukmronlik qil” algoritmining ishlash printsipi
Bo’lib tashla va hukmronlik qil paradigmasi asosiy masalalari

Bu paradigma dasturlashning juda mashhur algoritmlari asosini tashkil qiladi:

1. 
   Ikkilik qidirish (Binary Search)
   
2. 
   Merge Sort
   
3. 
   Quick Sort
   
4. 
   Eng yaqin ikki nuqta (Closest two points)
   
5. 
   Strassen ko’paytirishi (Strassen multiplication)
   
6. 
   Karatsuba algoritmi (Karatsuba algorithm)
   
7. 
   Cooley-Tukey algoritmi (Cooley-Tukey Algorithm)
   

Bo’lib tashla va hukmronlik qil paradigmasi afzalliklari

• 
  qiyin masalalarni osonlik bilan yechishga imkon beradi
  
• 
  bu paradigmaga asoslangan algoritmlar oddiy yechimlardan ko’ra tezroq ishlaydi. Masalan: oddiy saralash bo’lgan Bubble Sortning tezligi O(n²) bo’lsa, MergeSortniki O(n*logn)
  
• 
  bunday algoritmlarni parallel hisoblovchi sistemalarda hech qanday o’zgarishsiz ishlatish mumkin
  
• 
  bunday algoritmlarni qo’llashda xotira keshidan unumli foydalanish mumkin. Chunki masalalar bo’linish jarayonida shunday kichik qismlarga ajraladiki, ularni keshni o’zida turib yechish mumkin bo’ladi.
  
• 
  haqiqiy sonlar uchun bunday algoritmlar aniqroq ishlaydi, chunki qism yechimlardagi haqiqiy sonlar ustidagi amallar aniqroq bajariladi (masalan, ko’paytirish algoritmlarida)
  

Bo’lib tashla va hukmronlik qil paradigmasi kamchiliklari

• 
  bunday paradigma asosida ishlaydigan algoritmlar rekursiyadan foydalanadi va bu narsa ularni ishlashini ma’lum miqdorga sekinlashtiradi. Buning ustiga kichik bir xato yechimni cheksiz takrorlanishga tushirib qo’yishi mumkin.
  
• 
  asos shartni tanlashda yo’l qo’yilgan xato barcha qism masalalarda xatolik va ortiqcha xotira ishlatilishiga olib keladi
  

88.Қандай саралаш алгоритмларини биласиз?

Pufakchali saralash (Bubble sort)

Massivda chapdan o’ngga qarab yuramiz. Agar joriy element keyingisidan kata bo’lsa, u holda ularning o’rnini almashtiramiz. Shu tartibda massiv saralanguncha davom ettiramiz. Aytish joizki, birinchi iteratsiyadan so’ng eng kata element massiv oxirida(o’zinging joyida) joylashadi. Okkita iteratsiyadan so’ng ikkita kata element o’z joyini egallagan bo’ladi va shu tartibda davom etadi. N ta iteratsiyadan so’ng massiv saralangan bo’lishi ham mumkin. Bundan kelib chiqqan holda, asimptotika eng yomon va o’rta holatda – O(n²) ga teng, eng yaxshisi esa – O(n).

void SortAlgo::bubbleSort(int data[], int lenD)

{

int tmp = 0;

for(int i = 0;i

for(int j = (lenD-1);j>=(i+1);j--){

if(data[j]

tmp = data[j];

data[j]=data[j-1];

data[j-1]=tmp;

}

}

}

}

Sheyker saralash (Shaker sort)

Sheyker sort aralash yoki kokteyl saralash deb ham yuritiladi. Ma’lumki, pufakchali saralash eng kichik element massiv oxirida joylashgan holatda testlanganda sekin ishlaydi(ularni “toshbaqalar” deb yuritadilar). Bunda element har bir qadamda atigi bitta pozitsiyaga chapga suriladi. Shu sababdan faqat chapdan o’ngga emas balki o’ngdan chapga ham yurish amalga oshiramiz. Ikkita begin va end ko’rsatkichlarini olamiz, bu bizga massivning qaysi bo’lagi saralanmaganini anglatadi. Keying iteratsiyada end ga yetib borganda undan birni ayiramiz va o’ngdan chapga qarab yuramiz, analog holda begin ga yetib borganda bitta oshiramiz va yana chapdan o’ngga yurishda davom etamiz. Algoritmning asimptotikasi ham huddi pufakcha saralashi kabidir, lekin ishlash vaqti anchayin yaxshiroq.

void shakersort(int* l, int* r)

{

int sz = r - l;

if (sz <= 1) return;

bool b = true;

int* beg = l - 1;

int* end = r - 1;

while (b)

{

b = false;

beg++;

for (int* i = beg; i < end; i++)

{

if (*i > *(i + 1))

{

swap(*i, *(i + 1));

b = true;

}

}

if (!b) break;

end--;

for (int* i = end; i > beg; i--)

{

if (*i < *(i - 1))

{

swap(*i, *(i - 1));

b = true;

}

}

}

}

Qo’yish orqali saralash (Insertion sort)

Algoritm tugagandan so’ng natijalar joylanadigan massiv yaratamiz. Elementlarni navbat bilan natijaviy massivga shunday joylaymizki, oxirida massiv saralangan holatda bo’lishi lozim. Asimptotika o’rta va yomon holda O(n²) ga, yaxshi holda esa O(n) ga teng bo’ladi. Algoritmni boshqacharoq usulda amalga oshirish qulayroq (yangi massiv yaratish va unga haqiqatdan biron elementni joylash nisbatan murakkabroq): kirish massivining prefiksini tartiblashni amalga oshiramiz, qo’yishni o’rniga joriy elementni oldingisi bilan (agar u noto’g’ri joyda turgan bo’lsa) almashtirishni amalga oshiramiz.

void insertionsort(int* l, int* r)

{

for (int *i = l + 1; i < r; i++)

{

int* j = i;

while (j > l && *(j - 1) > *j)

{

swap(*(j - 1), *j);

j--;

}

}

}

Tanlash orqali saralash (Selection sort)

Ushbu iteratsiyada massivdagi joriy elementdan keyingi minimum elementni topamiz, zarur bo’lsa o’rin almashtiramiz. Bu holatda i-iteratsiyadan keyin I ta element o’z o’rnida joylashgan bo’ladi. Asimptotika: O(n²) yaxshi, yomon va o’rta holatda ham. Shuni ham ta’kidlash joizki, bu saralashni ikkita holatda amalga joriy qilish mumkin – minimum element va uning indeksini saqlagan holda yoki joriy elementni ko’rilayotganlar noto’g’ri o’rinda joylashgan bo’lsa ularni qayta tartibga solish orqali. Birinchi usul ancha tezkorroq bo’lganligi sababli uni amalda qo’lladik.

void selectionsort(int* l, int* r)

{

for (int *i = l; i < r; i++)

{

int minz = *i, *ind = i;

for (int *j = i + 1; j < r; j++)

{

if (*j < minz) minz = *j, ind = j;

}

swap(*i, *ind);

}

}

Tezkor qidiruv (Quicksort)

Qandaydir tayanch element tanlab olinadi. Shundan so’ng undan kichik elementlarni chapga joylaymiz, kattalarini esa o’ngga. Rekursiv ravishda har bir qismga murojaat qilamiz. Tayanch elementdan har bir kichik element oldin tayanch elementdan kattalaridan oldin turardi. Asimptorika: O(nlogn) o’rta va O(n²) yaxshi holatda. Yomon holat massivning tayanch elementi omadsiz holatda tanlanadi. Bu algoritmning quyida standart holini ko’rib chiqamiz, bir vaqtning o’zida chapdan va o’ngdan ikkita element topamiz. Chapdagi element tayanch elementdan katta, o’ngdagisi kichik bo’lishi lozim va ularni o’rinlarini almashtiramiz. Bundan tashqari, aniq tezkor saralashda qo’yish orqali saralashning kam sondagi elementlari ustida taqqoslash va saralash amallari qatnashgan. Konstanta testlash orqali tanlab olingan, qo’yish orqali saralash esa ushbu masalani yechish uchun mos keluvchi eng munosib saralashdir (bu holdan uni kvadratik saralashlardan afzal deb hisoblash kerak emas).

void quicksort(int* l, int* r)

{

if (r - l <= 1) return;

int z = *(l + (r - l) / 2);

int* ll = l, *rr = r - 1;

while (ll <= rr)

{

while (*ll < z) ll++;

while (*rr > z) rr--;

if (ll <= rr)

{

swap(*ll, *rr);

ll++;

rr--;

}

}

if (l < rr) quicksort(l, rr + 1);

if (ll < r) quicksort(ll, r);

}

void quickinssort(int* l, int* r)

{

if (r - l <= 32)

{

insertionsort(l, r);

return;

}

int z = *(l + (r - l) / 2);

int* ll = l, *rr = r - 1;

while (ll <= rr)

{

while (*ll < z) ll++;

while (*rr > z) rr--;

if (ll <= rr)

{

swap(*ll, *rr);

ll++;

rr--;

}

}

if (l < rr) quickinssort(l, rr + 1);

if (ll < r) quickinssort(ll, r);

}


89.Саралаш алгоритмлари самарадорлигини қандай баҳолаш мумкин?

Saralash algoritmlarining tartibli statistikasi

Saralash algoritmlarini statistic tahlil qilishda ko’plab kuzatishlar olib borish mumkin. Quyida mavjud algoritmlarning asimptotik tahlilini jadvallar bilan ko’rib chiqamiz. Bunda:

Yaxshi

O’rta

Yomon

Saralash algoritmlari tahlili:

Algoritm	Ma’lumotlar tuzilmasi	Vaqt bo’yicha murakkabligi				Qo’shimcha ma’lumotlar
		Yaxshi	O’rta	Yomon	Yomon holatda
Tezkor saralash	Massiv	O(n log(n))	O(n log(n))	O(n^2)	O(n)
Surish orqali saralash	Massiv	O(n log(n))	O(n log(n))	O(n log(n))	O(n)
Piramidali saralash	Massiv	O(n log(n))	O(n log(n))	O(n log(n))	O(1)
Pufakchali saralash	Massiv	O(n)	O(n^2)	O(n^2)	O(1)
Qo’yish orqali saralash	Massiv	O(n)	O(n^2)	O(n^2)	O(1)
Tanlash orqali saralash	Massiv	O(n^2)	O(n^2)	O(n^2)	O(1)
Blokli saralash	Massiv	O(n+k)	O(n+k)	O(n^2)	O(nk)
Razryad bo’yicha saralash	Massiv	O(nk)	O(nk)	O(nk)	O(n+k)

Javob berilishi kerak bo'lgan birinchi jiddiy savol: qanday qilib “samarali algoritm” tushunchasini aniqlash mumkin? Bir qarashda samaradorlikning ishchi ta'rifi quyidagicha ko'rinishi mumkin.

ta'rif: algoritm samarador deb ataladi, agar ma'lumotlar kiritilganda uni amalga oshirish tezkor bajarilsa.

Albatta, samaradorlik nisbiy tushuncha bo’lib, bir nechta algoritmlarni solishtirish orqali aniqlanadi

Agar saralanayotgan yozuvlar xotirada katta hajmni egallasa, u holda ularni
almashtirishlar katta sarf (vaqt va xotira ma’nosida) talab qiladi. Ushbu sarfni
kamaytirish maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina ma’lumot ko’rsatkichlari almashtirilib, massiv o’z joyida qoladi. Bu usul adreslar jadvalini saralash usuli deyiladi.
Saralanayotganda bir xil kalitlar uchrashi mumkin, bu holda saralangandan keyin bir xil kalitlilar boshlang’ich tartibda qanday joylashgan bo’lsa, shu tartibda
qoldirilishi maqsadga muvofiq bo’ladi (Bir xil kalitlilar o’zlariga nisbatan).
Bunday usulga turg’un saralash deyiladi. Saralash samaradorligini bir necha
mezonlar bo’yicha baholash mumkin:

saralashga ketgan vaqt;
saralash uchun talab qilingan operativ xotira;
dasturni ishlab chiqishga ketgan vaqt.
Birinchi mezonni qarab chiqaylik. Saralash bajarilganda taqqoslashlar yoki
almashtirishlar sonini hisoblash mumkin. Faraz qilaylik, – taqqoslashlar soni. Agar 
bo’lsa, u holda ikkinchi qo’shiluvchi katta, aks holda ya’ni, bo’lsa,
birinchi qo’shiluvchi katta bo’ladi.
Demak, kichkina larda taqqoslashlar soni ga teng bo’ladi, katta larda
esa ga teng bo’ladi.
Saralashda taqqoslashlar soni quyidagi oraliqlarda bo’ladi:
Onlog n dan On2gacha; On– ideal holatda.
Saralashning quyidagicha usullari bor:
qat’iy (to’g’ridan-to’g’ri) usullar;
yaxshilangan usullar.
Qat’iy usullarning afzalliklarini ko’rib chiqaylik:
1. Bilamizki, dasturlarning o’zlari ham xotirada joy egallaydi. To’g’ridan-to’g’ri saralash usullarining dasturlari qisqa bo’lib, ular tushunishga oson.
2. To’g’ridan-to’g’ri saralash usullari orqali saralash tamoyillarining asosiy
xususiyatlarini tushuntirish qulay.

3. Murakkablashtirilgan usullarda uncha ko„p amallarni bajarish talab qilinmasada, ushbu amallarning o’zlari ham ancha murakkabdir. Garchi yetarlicha katta n larda ulardan foydalanish tavsiya etilmasada, kichik n larda mazkur usullar tezroq ishlaydi.
Shu joyni o’zida qat’iy usullarni ishlash tamoyillariga ko’ra 3 ta toifaga
bo’lish mumkin:
1. To’g’ridan-to’g’ri qo’shish usuli (by insertion);
2. To’g’ridan-to’g’ri tanlash usuli (by selection);
3. To’g’ridan-to’g’ri almashtirish usuli (by exchange)

To’g’ridan-to’g’ri qo’shish usuli bilan saralash algoritmi.
Bunday usul karta o’yinida keng qo’llaniladi. Elementlar (kartalar) hayolan
“tayyor” a(1),...,a(i-1) va boshlang’ich ketma-ketliklarga bo’linadi. Har bir
qadamda (i=2 dan boshlanib, har bir qadamda bir birlikka oshirib boriladi)
boshlang’ich ketma-ketlikdan i-chi element ajratib olinib tayyor ketma-ketlikning
kerakli joyiga qo’yiladi.
To’g’ridan-to’g’ri qo’shish orqali saralash algoritmi quyidagicha bo’ladi:
for (int i=1;i
x=a[i];
x ni a[0]...a[i] oraliqning mos joyiga qo‘shish
}
Kerakli joyni qidirish jarayonini quyidagi tartibda olib borish qulay bo’ladi. 2-
elementdan boshlab har bir elementni qarab chiqamiz, ya’ni har bir element
o’zidan oldin turgan element bilan solishtiriladi. Agar qaralayotgan element kichik
bo’lsa, oldinda turgan element bilan o’rin almashadi va yana o’zidan oldinda
turgan element bilan solishtiriladi, jarayon shu kabi davom etadi. Bu jarayon
quyidagi shartlarning birortasi bajarilganda to’xtatiladi:
1. x elementi oldida uning kalitidan kichik kalitli a(j) elementi chiqqanda.
2. x elementi oldida element qolmaganda.
for (int i=1;i
int j=i;
while(a[j]
int t=a[j-1];
a[j-1]=a[j];
a[j]=t;
j=j-1;
}
}
Tanlash orqali saralash algoritmi

Mazkur usul quyidagi tamoyillarga asoslangan:
1. Eng kichik kalitga ega element tanlanadi.
2. Ushbu element a0 birinchi element bilan o’rin almashinadi.
3. Keyin mazkur jarayon qolgan n-1, n-2 elementlar bilan takrorlanib, to
bitta eng “katta” element qolguncha davom ettiriladi.
for(int i=0;i
for(int j=i+1;j
if (a[i] > a[j]){
int k = a[j];
a[j]= a[i];
a[i]= k;
}
Algoritm samaradorligi:
-Taqqoslashlar soni
-Massiv tartiblanganda o’rinlashtirishlar soni
-Massiv teskari tartiblanganda o’rinlashtirishlar soni
Ushbu usul bo’yicha saralash bajarilsa, eng yomon holda taqqoslashlar va
o’rinlashtirishlar soni tartibi n^2 bo’ladi
“Pufaksimon” usulni yaxshilash

Ushbu usulning g„oyasi quyidagicha: marta massivda quyidan yuqoriga
qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati
yuqoridagi jufti kalitidan kichik bo„lsa, u holda ularning o„rni almashtiriladi
1) Agar massivda o’tishlar nafaqat yuqoridan pastga, balki bir vaqtning o’zida
pastdan yuqoriga ham bo’lsa, u holda “yengil” elementlar “yuqoriga suzib” chiqadi
va “og’ir” elementlar esa “cho’kadi”.
2) Massivda “bekor” o’tishni yo’q qilish uchun, tashqi siklda massiv
saralanganligini tekshiruvchi belgi qo’yish lozim.
for (int i=0;i
for (int j=n-1;j>i;j--)
if (a[j] < a[j - 1]){
int x= a[j - 1];
a[j - 1] = a[j];
a[j] = x; }
O’rinlashtirish va taqqoslashlar soni: (n* log( n )).

Masalaning qo’yilishi – tabalarning ism, familiyalarini optimallashtirilgan pufaksimon usuli bilan tartibga keltirish dasturini tuzamiz va saralash nechta o’rin almashtirish bilan amalga oshirilganini aniqlaymiz.

Algoritm
1. Jadvalga talabalar ism-sharifini kiritamiz.
2. Jadvaldagi 1-elementni olamiz, i=0.
3. Jadvaldagi n-1 oxirgi elementdan to i-elementgacha barcha elementni FIO
maydonini o’zidan oldin turgan element FIO maydoni bilan solishtiramiz.
Agar zarur bo’lsa, o’rin almashtiramiz va o’rin almashtirishlar hisoblagichi l
ning qiymatini bittaga oshiramiz, ya’ni l++.
4. Agar i
5. Natijaviy saralangan massivni ekranga chiqaramiz.
Dastur kodi
#include
#include
using namespace std;
int main(int args, char *argv[])
{
int n; cout<<"talabalar sonini kiriting=";cin>>n;
struct table{
int t;
char FIO[20];
} talaba[n];
cout<
for(int i=0;i
talaba[i].t=i+1;
cin>>talaba[i].FIO;
}
int l=0;
for(int i=0;i
for(int j=n-1;j>i;j--){
if (strcmp(talaba[j-1].FIO,talaba[j].FIO)==1){
l++;
table k=talaba[j];
talaba[j]=talaba[j-1];
talaba[j-1]=k;
}
}
}
for(int i=0;i
cout<<"| "<
cout<<"bu algoritm jadvalni "<
saraladi\n";
system("PAUSE");
}
Dastur natijasi:
talabalar sonini kiriting=5
5 ta talabalar FIO sini kiriting
Farhod
Asror
Sobir
Bobur
Vali
| 2 | Asror |
| 4 | Bobur |
| 1 | Farhod |
| 3 | Sobir |
| 5 | Vali |
bu algoritm jadvalni 10 ta solishtirishda saraladi.

92.Quicksort алгоритмини тушунтиринг.

Quiksort – тез саралаш алгоритмлари.

QuickSort яъни тез саралаш – Чарлз Хоар томонидан яратилган машхур сарааш алгоритмидир. Ушбу алгоритм n та элементдан иборат массивни энг узоги билан O(n²) вактда саралайди. Лекин бажарилиш тезлигининг математик кутилмаси O(n log n) га тенг ва у бошка шундай тезликда бадарилувчи алгоритмлардан тезрок ишлайди.

Ишлаш присипи:

• 
  Массивда ихтийорий таянч элемент талаймиз
  
• 
  Кейин ундан кичик йоки тенг элементларни унинг чап томонига, катталарини унг томонига утказамиз.
  
• 
  1-2 кадамларни таянч элементнинг унг ва чап томонларидаги элементлар учун куллаймиз
  

Айни шу 2-кадамда элементларни жойлаштириш алгоритми туфайли у саралаш алгоритмлари ичида енг тез ишлайдиганларидан биридир.

#include

#include

using namespace std;

int partition(int *a,int start,int end)

{

int pivot=a[end];

int P_index=start; //P-index sikldagi qiymat indexsi uchun

int i,t; //t vaqtinchalik o'zgaruvchi

for(i=start;i

{

if(a[i]<=pivot)

{

t=a[i];

a[i]=a[P_index];

a[P_index]=t;

P_index++;

}

}

//o'rin almasshtirish uchun

t=a[end];

a[end]=a[P_index];

a[P_index]=t;

return P_index;

}

void Quicksort(int *a,int start,int end)

{

if(start

{

int P_index=partition(a,start,end);

Quicksort(a,start,P_index-1);

Quicksort(a,P_index+1,end);

}

}

int main()

{

cout<<"\n\t\tAkramov Umarbek CAL006 guruh"<

int n;

cout<<"Neshta element kiritmoqchisiz: ";

cin>>n;

int a[n];

cout<<"\nAralash tartibda raqamlarni kiriting:\n";

for(int i=0;i

{

cin>>a[i];

}

Quicksort(a,0,n-1);

cout<<"\nQuickSort saralab bergan holati:\n";

for(int i=0;i

{

cout<

}

return 0;

}



1-расм. QuickSort дастур натижаси.