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

Selection sort (Tanlab saralash)
Selection sort (Tanlab saralash) bu — oddiy tartiblash algoritmidir. Ushbu tartiblash algoritmi oʻz joyida taqqoslashga asoslangan algoritm boʻlib, unda roʻyxat ikki qismga boʻlinadi, tartiblangan qism chap tomonda va tartiblanmagan qism oʻng tomonda. Dastlab, tartiblangan qism boʻsh, tartiblanmagan qismi esa butun roʻyxatdir.

2-rasm. Selection sort

Eng kichik element tartiblanmagan massivdan tanlanadi va eng chap element bilan almashtiriladi va bu element tartiblangan massivning bir qismiga aylanadi. Bu jarayon tartiblanmagan massiv chegarasini bitta element bilan oʻngga siljitishda davom etadi.
Ushbu algoritm katta maʼlumotlar toʻplamlari uchun mos emas, chunki uning oʻrtacha va eng yomon holatlari murakkabligi (n²), bu yerda n — elementlar soni.
Tanlab saralash qanday ishlaydi?
Misol tariqasida quyidagi massivni koʻrib chiqamiz: arr[] = {64, 25, 12, 22, 11}
Birinchi oʻtish: Saralangan massivdagi birinchi oʻrin uchun butun massiv 0 dan 4 gacha boʻlgan indeksdan ketma-ket oʻtkaziladi. Hozirgi vaqtda 64 saqlanadigan birinchi pozitsiya, butun massivni aylanib oʻtgandan soʻng, 11 eng past qiymat ekanligi ayon boʻladi.

Shunday qilib, 64 ni 11 bilan almashtiring. Bir iteratsiyadan soʻng massivdagi eng kam qiymat boʻlgan 11, tartiblangan roʻyxatning birinchi pozitsiyasida paydo boʻladi.

Ikkinchi oʻtish: 25 mavjud boʻlgan ikkinchi pozitsiya uchun massivning qolgan qismini yana ketma-ketlikda aylantiring.

Ketishdan soʻng biz 12 massivdagi ikkinchi eng past qiymat ekanligini va u massivda ikkinchi oʻrinda paydo boʻlishi kerakligini aniqladik, shuning uchun bu qiymatlarni almashtiring.

Uchinchi oʻtish: Endi, uchinchi oʻrin uchun, 25 mavjud boʻlgan joyda yana massivning qolgan qismini aylanib oʻting va massivdagi uchinchi eng kam qiymatni toping.

Ketish paytida 22 uchinchi eng kam qiymat boʻlib chiqdi va u massivda uchinchi oʻrinda paydo boʻlishi kerak, shuning uchun 22 ni uchinchi oʻrindagi element bilan almashtiring.