left_arrow
right_arrow
9-rasm. Ikkinchi marta o‘rin almashgandan keyingi holat.
M assiv qismlarini tartiblash “left_arrow > right_arrow” sharti
o ‘rinli bo‘lganidan so‘ng yakunlanadi. 9-rasmdagi holda bu shart
114
“yolg‘on”, shuning uchun “right_arrow” chap tomonga qarab suri-
lishda davom etmoqda. Bu holat 10-rasmdagi holat yuzaga kelguncha
davom etadi.
p iv o t
[ A 1 3 1 2 I 2 I 5 | j ) l 0 j 11 I 9 1 14 |20~|
l e f t _ a r r o w
r i a h t . a r r o w
10-rasm, 0 ‘ng tomonda almashish uchun element topildi.
“left arrow”ning surilishi 11-rasmdagi holatga sabab bo ‘ladi.
0 ‘ng tomonga surilishda “pivot”dan katta yoki teng elementni topish
talab qilingani uchun “left_arrow” chegaraviy elementga yetganidan
kcyin surishni to ‘xtatadi.
p i v o t
| 4 | 3 | 2 | 2 | 5 | ( ! ) | 0 | 11 | 9 | 14 |20 |
I
|
le ft _ a r r o w
r ia h t arrow
11-rasm. Chap element ci egaraviy bilan ustma-ust tushdi.
Shundan keyin chegaraviy elementni o ‘z ichiga oluvcbi alma-
shuv bajariladi va massiv 12-rasmdagi holatga o ‘tadi.
p i v o t
A
3 | 2
2
5
0
© 1 11
9
14 j 20
I
l e f t _ a r r o w
ric rh t arro w
1 2-rasm .
Uchinchi almashuvdan keyingi holat.
Elementlar o'rin almashganlaridan so‘ng “right_arrow” chap,
"lol't arrow” esa o ‘ng tomonga suriladi (13-rasm).
115
pivot
\ 4 | 3 | 2 | 2 | 5 | 0 |d ) | 11 | 9 114 120 |
I
I
I left_arrow
right arrow
13-rasm. Tartiblash indekslar massiv o‘rtasidan o‘tganda
yakunlanadi.
13-rasmda tartiblash sharti “left_arrow>right_arrow” o ‘rinli
b o ig a n hoi tasvirlangan. Shuning uchun massivni ikkiga ajratish va
qayta tartiblash jarayonini tugatilgan deb hisoblash mumkin.
Quyida tez tartiblash algoritmi Quicksort ni amalga oshiruvchi
funksiya keltirilgan.
Do'stlaringiz bilan baham: |