|
Algoritmlar
|
| bet | 170/275 | | Sana | 29.12.2020 | | Hajmi | 1,78 Mb. | | #13001 |
Nazorat savollari:
Saralash degangda nimani tushunamiz?
Qanday saralash algoritmlarini bilasiz?
Qaysi saralash algoritmlari effеktivroq bo’lib hisoblanadi?
Ichki saralash deganda nimani tushunamiz?
Pufаkchаli sаrаlash usuli vа uning mоhiyati nimada?
Pufаkchаli sаrаlash algoritmining murakkabligi qanday?
Mustaqil bajarish uchun vazifalar:
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.
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.
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?
|
| |
