Referati toshkent 2023 saralash algoritmlari mohiyati va ularning samaradorligini baholash. Reja

Partition va sort rekursiya ichida ishlaydi.

Partition va sort

Array:

Ajratuvchi element – pivotni tanlaymiz. Biz arrayni aralashtirganimiz uchun birinchi elementning qiymati arraydagi eng katta yoki eng kichik bo‘lish ehtimoli kam. Shu sababli arrayning birinchi elementi indeksini pivot deb olamiz. Demak array uchun pivot = 0.
Ikki pointerni (elementning indeks nomerini) belgilaymiz. Birinchi pointer i = 1, ikkinchi pointer – j = array.length – 1 = 14.
i >= j bo‘lmaguncha katta siklni (O) ishga tushiramiz.
(a) Kichkina sikl ichida arr[pivot] > arr[i] shart bajarilishdan to‘xtaguncha yoki i arrayning ohirgi elementi indeksiga teng bo‘lmaguncha i ni oshirib boramiz.
(b) Yana bir alohida kichkina sikl ichida arr[pivot] < arr[j] shart bajarilishdan to‘xtaguncha yoki j array’ning birinchi elementi indeksiga teng bo‘lmaguncha j ni oshirib boramiz.
(a) va (b) sikllar alohida-alohida (parallel) ishlaydi. Bizning holatda i = 2 va j = 11 da kichkina sikllar to‘xtaydi:
Sababi arr[pivot] arr[i] dan kichkina bo‘lib qoldi va arr[pivot] arr[j] dan katta bo‘lib qoldi. arr[i] va arr[j] o‘rnini almashtiramiz:

(O) katta sikl ishlashda davom etadi. Biz (a) va (b) sikllarni qayta ishga tushiramiz. Kichkina sikllar i = 3 va j = 10 holatda to‘xtaydi.

Sababi ma’lum, arr[pivot] < arr[i] va arr[pivot] > arr[j] bo‘lib qoldi. arr[i] va arr[j] o‘rnini almashtiramiz:

(O) katta sikl ishlashda davom etadi. Biz (a) va (b) sikllarni qayta ishga tushiramiz. Kichkina sikllar i = 4 va j = 9 holatda to‘xtaydi.

arr[i] va arr[j] o‘rnini almashtiramiz:

Endi esa i = 6, j = 5 bo‘lib qoldi, ya’ni i j dan katta bo‘lib ketdi. Bu degani biz array o‘rtasini topdik. (O) katta siklni to‘xtatamiz. Endi arr[pivot] va arr[j] o‘rnini almashtiramiz.

Pivot elementni arrayning kerakli joyiga qo‘ydik. Endi pivotning o‘ng tarafida undan kichik sonlar, chap tarafida undan katta sonlar joylashdi.

Arrayni pivot bo‘yicha ikki qismini alohida-alohida tartiblaymiz. Bizning misolda array

va

ga bo‘lindi. Aslida array o‘zi bo‘linmadi, biz arrayning qismlarini alohida tartiblaymiz.