Tanlash va joylashtirish turkumidagi murrakkablikga EGA saralash algoritmlari

AMALIY MASHG’ULOT №3
TANLASH VA JOYLASHTIRISH TURKUMIDAGI MURRAKKABLIKGA EGA SARALASH ALGORITMLARI
¹Saralash algoritmlarini quyidagi guruhlarga ajratish mumkin (1-rasm):


1-rasm Saralash algoritmlari


1-misol. Tanlangan elementlar tartiblangan ro’yhatni hosil qiladi. Masalan, ro’yhatdan eng kichik elementni topish talab etilsin:

Tanlash jarayoni rasmda keltirilgan. Tanlanayogan elementlar kichik hajmda aylanaga olingan. Taqqoslanayotgan elementlar soni rasmdagi satrlar soniga mos kelishini, shuningdek, elementlarni ko’chirish soni tanlangan elementlarni o’zgartirish soniga mos kelishini Ko’rish qiyin emas.

2-rasm. Tanlash usulida saralash²

2-misol. Tanlash usulida saralash orqali ro’yhatdan eng kichik elementni toping:

3-misol. Tanlash usulida saralash orqali ro’yhatdan eng kichik elementni toping:

4-misol.
3-rasmdan namuna sifatida foydalanib,
massivni saralashda joylashtirish usulini (Insertion-sort) qo’llang.


³
3-rasm. massivni joylashtirish usulida saralashdir. (Insertion-sort). Kvadratlar bilan belgilangan massiv elementlarining yuqori qismida elementlar indekslari va kvadratlar ichida mos elementlar qiymatlari berilgan. Bu rasmning a-d qismi for sikliga mos keladi. 1-8 qatorida for sikl iteratsiya psevdokodlari (a)-(d) rasm qismiga mos keladi. Har bir iteratsiyada qora kvadratlarda A[j] kaliti qiymatlari tashkil topgan bo’lib, undan chapda joylashgan (psevdakodning 5-satri) kulrang kvadratlar bilan taqqoslanadi. Faqat bitta pozitsiyaga o’ng tomonga siljiydigan massivlar qiymati kulrang ko’rsatgich bilan ko’rsatilgan (6-satr), qora rangli ko’rsatgich orqali – kalitning ko’chishi ko’rsatilgan (8-satr). (e) qismida saralangan massivning yakuniy holati ko’rsatilgan.