12
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?
