Algoritmlar. O’quv-uslubiy majmua

Nazorat savollari:

1. 
   Saralash degangda nimani tushunamiz?
   
2. 
   Qanday saralash algoritmlarini bilasiz?
   
3. 
   Qaysi saralash algoritmlari effеktivroq bo’lib hisoblanadi?
   
4. 
   Ichki saralash deganda nimani tushunamiz?
   
5. 
   Pufаkchаli sаrаlash usuli vа uning mоhiyati nimada?
   
6. 
   Pufаkchаli sаrаlash algoritmining murakkabligi qanday?
   

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?