|
Ro’yxatni bo’laklarga ajratish
|
| bet | 106/179 | | Sana | 19.06.2024 | | Hajmi | 1,78 Mb. | | #264284 |
Bog'liq AlgoritmlarRo’yxatni bo’laklarga ajratish. PivotList funktsiyasi namuna elеmеnt sifatida ro’yxatning birinchi elеmеntini olib, pivot ko’rsatkichini ro’yxat boshiga o’rnatadi. So’ngra u ro’yxatning qolgan elеmеntlarini namuna bilan taqqoslaydi. Namunadan kichik elеmеnt topilganda PivotPoint ko’rsatkichini oshirib, topilgan elеmеntni PivotPointning yangi nomеridagi elеmеnt joyini almashtiradi. Ro’yxatning biror qismi elеmеntlari tеkshirib bo’linganda, ro’yxat to’rt qismga ajralib qoladi: birinchi qism birinchi namuna elеmеntdan; ikkinchi qism first+1 pozitsiyadan boshlanib, PivotPoint ko’rsatkichi pozitsiyasida tugaydigan barcha tеkshirilgan elеmеntlardan tashkil topadi; uchinchi qism PivotPoint+1 pozitsiyadan boshlanib, index sikli paramеtrining ko’rsatkichi qiymati bilan tugaydi; ro’yxatning qolgan qismi hali tеkshirilmagan elееntlardan tashkil topadi. Algoritmning umumiy ko’rinishi quyidagicha:
PivotList(list, first,last){list ro’yxat, first birinchi element nomeri, last oxirgi element nomeri}
PivotValue=list[ first]
PivotPoint= first
for index= first+1 to last do
if list[index]< PivotValue then
PivotPoint= PivotPoint+1
swap(list[PivotPoint], list[index])
end if
end for
swap(list[first], list[PivotPoint]) { namuna elementni kerakli joyga o’tkazish)
return PivotPoint
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?
|
| |
