Ma'lumotlarni saralash algoritmlari. Tad kafedrasi

Saralashning qanday turlari bor
O'nlab saralash algoritmlari mavjud, ularning har biri o'ziga xos tarzda yaxshi. Ba'zilarida saralash tamoyillarini tushuntirish oson, boshqalari katta massivlar bilan ishlashda yaxshi, uchinchisi tezlik uchun optimallashtirilgan, to'rtinchisi - protsessor davrlari soni, kodning ixchamligi va boshqalar uchun.
Eng mashhur saralash usullari:
Pufakchani saralash.
Saralashning Sheyker usuli.
Saralashning Taroq usuli.
Tez saralash usuli.
Piramidasimon saralash.
Birlashtirish orqali saralash.
Алгоритмлар:
• Оддий ва тушунарли, лекин катта массивлар учун, самарали
эмас
 Пуфакча усули
 Танлаш усули
Қийин, лекин самарали усуллар
 «тез саралаш» (Quick Sort)
 «тўп-тўп» саралаш (Heap Sort)
 Қўшилиб саралаш
 Пирамидали саралаш

Saralashning qat’iy usullari

Qo‘yish orqali saralash (Insertion sort)
Algoritm g’oyasi
Ob’ektlar hayolan “tayyor” a(1),...,a(i-1) va boshlang‘ich ketma-ketliklarga bo‘linadi. Har bir qadamda (i=2 dan boshlab) boshlang‘ich ketma-ketlikdan i-chi element ajratib olinib tayyor ketma-ketlikning kerakli joyiga qo‘shiladi.
Misol: Faraz qilaylik, kalit qiymatlari 40,51,8,38,90,14,2,63 bo‘lgan ob’ektlar berilgan bo‘lsin.
- boshlang’ich holat
Berilgan massivdan elementlarni birma-bir o’qib, yangi massivga tartibiga qarab joylaymiz. Algoritm tugagandan so’ng natijada saralangan massiv hosil qilamiz.
Asimptotika O'rtacha va eng yomon holatda O(n2), eng yaxshi holatda O(n).

Сложность	Наилучший случай	В среднем	Наихудший случай
Время	O(n)	O(n2)	O(n2)
Память	O(1)	O(1)	O(1)

Algoritmni boshqa usulda amalga oshirish qulayroqdir (yangi massiv yaratish va unga aslida biror narsa kiritish nisbatan qiyin): biz shunchaki berilgan massivning qandaydir bosh bo’lagi tartiblanganligiga ishonch hosil qilamiz.

Kiritish o‘rniga biz joriy element noto'g'ri tartibda joylashgan bo'lsa oldingi element bilan almashtiramiz.
Kiritish tartibi massivni bosqichma-bosqich chapdan o'ngga siljitadi. Bunday holda, har bir keyingi element minimal va maksimal qiymatga ega bo'lgan eng yaqin elementlar orasida joylashtiriladi.