|
Mavzu: Pufaksimon saralash. Birlashtirish orqali saralash. Piramidal saralash
|
| bet | 2/3 | | Sana | 23.11.2023 | | Hajmi | 179,43 Kb. | | #104055 |
Bog'liq Pufaksimon saralashBosqichma-bosqich misol
{5, 1, 4, 2, 8} raqamlari massivini oling va pufakchali tartiblash yordamida massivni eng kichik sondan eng katta raqamga tartiblang. Har bir bosqichda qalin harf bilan yozilgan elementlar taqqoslanadi. Uchta oʻtish kerak boʻladi;
Birinchi oʻtish
(5 1 4 2 8) → (1 5 4 2 8), Bu yerda algoritm dastlabki ikki elementni taqqoslaydi va 5 > 1 dan keyin almashinadi.
(1 5 4 2 8) → (1 4 5 2 8), 5 > 4 dan beri almashtirish
(1 4 5 2 8) → (1 4 2 5 8), 5 > 2 dan beri almashtirish
(1 4 2 5 8) → (1 4 2 5 8), Endi bu elementlar tartibda boʻlgani uchun (8 > 5), algoritm ularni almashtirmaydi.
Ikkinchi oʻtish
(1 4 2 5 8) → (1 4 2 5 8)
(1 4 2 5 8) → (1 2 4 5 8), 4 > 2 dan beri almashtirish
(1 2 4 5 8) → (1 2 4 5 8)
(1 2 4 5 8) → (1 2 4 5 8)
Endi massiv allaqachon tartiblangan, lekin algoritm uning tugallanganligini bilmaydi. Algoritm tartiblanganligini bilish uchun uni almashtirishsiz yana bitta toʻliq oʻtish kerak.
Uchinchi oʻtish
(1 2 4 5 8) → (1 2 4 5 8)
(1 2 4 5 8) → (1 2 4 5 8)
(1 2 4 5 8) → (1 2 4 5 8)
(1 2 4 5 8) → (1 2 4 5 8)
Optimallashtirilgan pufakchali saralash algoritmi
Yuqoridagi algoritmda, massiv allaqachon tartiblangan bo'lsa ham, barcha taqqoslashlar amalga oshiriladi. Buni bajarish vaqtini oladi. Buni hal qilish uchun biz qo'shimcha o'zgaruvchini kiritishimiz mumkin, almashtirildi ning qiymati elementlar almashinuvi sodir bo'lsa, rost bo'ladi. Aks holda, unga yolg’on qiymat o'rnatiladi.
Iteratsiyadan so'ng, agar almashtirish bo'lmasa, almashtirildi ning qiymati yolg'on bo'ladi. Bu shuni anglatadiki, elementlar allaqachon tartiblangan va keyingi takrorlashni amalga oshirishga hojat yo'q. Bu bajarilish vaqtini qisqartiradi va saralashni optimallashtirishga yordam beradi.
|
| |
