O‘zbеkiston rеspublikasi axborot tеxnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkеnt axborot tеxnologiyalari univеrsitеti samarqand filiali

Saralash – bu berilgan to’plam elementlarini biror bir tartibda joylashtirish
jarayonidir.
Saralash maqsadi - tartiblangan to’plamda kerakli elementni topishni
osonlashtirishdan iborat.
Saralash turlari – 1). ichki saralash bu operativ xotiradagi saralash va 2). tashqi saralash – tashqi xotirada saralash.
Adreslar jadvalini saralash usuli - agar saralanayotgan yozuvlar xotirada kata xajmni egallasa, u holda ularni almashtirishlar katta sarf (vaqt va xotira ma’nosida) talab qiladi. Ushbu sarfni kamaytirish maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina ma’lumot ko’rsatkichlari almashtirilib, massiv o’z joyida qoladi.
Saralash samaradorligi (taqqoslashlarga nisbatan) - O(n log n) dan O(n2) gacha; O(n) – ideal holatda.
To’g’ridan-to’g’ri qo’shish usuli bilan saralash - bunda elementlar hayolan “tayyor” a(1),...,a(i-1) va boshlang’ich ketma-ketliklarga bo’linadi. Har bir qadamda (i=2 dan boshlanib, har bir qadamda bir birlikka oshirib boriladi) boshlang’ich ketma-ketlikdan i-chi element ajratib olinib tayyor ketma-ketlikning kerakli joyiga qo’shiladi.
To’g’ridan-to’g’ri tanlash usuli bilan saralash – bunda berilgan elementlar ichidan eng kichik kalitga ega element tanlanadi va ushbu element boshlang’ich ketma- ketlikdagi birinchi element bilan o’rin almashadi. Undan keyin ushbu jarayon qolgan n-1 ta element, n-2 ta element va xokazo, toki bitta eng “katta” element qolguncha davom ettiriladi.
To’g’ridan-to’g’ri almashtirish usuli bilan saralash (pufaksimon) – agar ma’lumotlar jadvali massiv ko’rinishida berilgan bo’lib, uni tashkil etuvchi elementlar soni n ta bo’lsa, u holda n - 1 marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi jufti kalitidan kichik bo’lsa, u holda ular o’rni almashtiriladi.
Quiksort – mazkur usul almashtirish usulidagi saralashning modifikasiyasi bo’lib, bunda uning asosini kalitlarni tanlangan kalitga nisbatan ajratish tashkil qiladi. Algoritm samaradorlig: O(n log n).