12
4-
LABORATORIYA MASHG‘ULOTI
MAVZU: Aralash (kombinatsiyalashgan) algoritmlar.
I.ISHDAN MAQSAD: Aralash algoritmining ishlash mexanizmini o‟rganish va ini tahlil
qilish.
II.LABORATORIYA MASHG‘ULOTIGA KERAK BO’LADIGAN JIHOZLAR:
Zamonaviy Core i5 yoki Core i7 kompyuterlari. Proektor qurilmasi. Konspekt daftarlari.
Laboratoriya ishi natijalar qaydi.
III.ISHNI BAJARISH TARTIBI:
Mustaqil bajarish uchun vazifalar:
1. QuickSort algoritmi ishining [23,17,21,3,42,9,13,1,2,7,35,4] ro‟yxatdagi o‟tishlari
natijalarini yozing. Ro‟yxat va stеk qiymatlarining (first, last, Pivot) har bir chaqiruv oldidagi
holatlarini yozing. Bajarilgan taqqoslashlar va o‟rin almashtirishlar sonini hisoblang.
2. QuickSort algoritmi ishining [3,9, 14,12,2,17,15,8,6,18,20,1] ro‟yxatdagi o‟tishlari
natijalarini yozing. Ro‟yxat va stеk qiymatlarining (first, last, Pivot) har bir chaqiruv oldidagi
holatlarini yozing. Bajarilgan taqqoslashlar va o‟rin almashtirishlar sonini hisoblang.
3. PivotList algoritmining quyidagi modifikatsiyasida ro‟yxatda ikki ko‟rsatkichning
aavjudligi nazarda tutiladi. Birinchisi pastdan kеladi, ikkinchisi yuqoridan kеladi.
Algoritmning asosiy siklida quyi ko‟rsatkichning qiymati PivotValuedan katta elеmеnt
uchramagunga qadar oshirib boriladi, yuqori ko‟rsatkich esa PivotValue dan kichik elеmеnt
uchramagunga qadar kichraytirib boriladi. So‟ngra topilgan elеmеntlarning o‟rni
almashtiriladi.Ushbu jarayon ushbu ikki ko‟rsatkich ustma-ust tushmagunga qadar davom
etadi. To‟liq algoritm quyidagi ko‟rinishga ega:
PivotList(list, first,last){list ro’yxat, first birinchi element nomeri, last oxirgi element nomeri}
PivotValue=list[first]
Lover= first
Upper= last+1
Do
Do Upper= Upper-1 until list[Upper]<= PivotValue
Do Lover = LoverQ1 until list[Lover]<= PivotValue
Swap( list[Upper], list[Lover])
Until Lover>= Upper
Swap( list[Upper], list[Lover]) {Ortiqcha almashtirishlardan qutilish}
Swap( list[first], list[Upper]) {O’qni kеrakli joyga surish}
return Upper
a) 1-mashqni PivotList modifikatsiyalangan algorit uchun bajaring;
b) 2-mashqni PivotList modifikatsiyalangan algorit uchun bajaring;
v) Qaysi amal modifikatsiyalangan algoritmda asosiy algoritmga nisbatan ancha kam
bajariladi?
