Ma'lumotlarni saralash algoritmlari. Saralashning yaxshilangan usullari va ularning samaradorligi

6-mavzu.Ma'lumotlarni saralash algoritmlari. Saralashning yaxshilangan usullari va ularning samaradorligi.

TAD kafedrasi

Reja:

• Reja:
• 1.Sheyker saralash
• 2. Shell saralash usuli;
• 3. Tez saralash (Quicksort).
• 4.Birlashtirish orqali saralash (Сортировка слиянием,merge sort)
• (yana
• 1. Piramidasimon saralash;
• 2.Сортировка подсчетом
• 3.Цифровая сортировка
• va x.z.

1.Sheyker saralash
Pufaksimon saralashda agar biz nafaqat maksimum qiymatga ega elementlarni oxiridan joylashtirib kelsak, balki minimum qiymatga ega bo’lgan elementlarni ham massivning boshlang’ich tomonidan joylashtirib kelsak, unda biz SHEYKER saralash algoritmiga ega bo’lamiz.
Jarayon “pufaksimon saralash" da bo'lgani kabi boshlanadi:
Massiv oxiriga maksimal qiymatga ega bo’lgan elementni surib boramiz.
Shundan so'ng, biz 180 gradus atrofida aylanamiz va teskari yo'nalishda boramiz, shu bilan birga massivning boshlang’ich qismiga maksimal emas, balki minimal elementni joylashtiramiz. Massivdagi birinchi va oxirgi elementlarni saralab, biz yana jarayonni takrorlaymiz. Massivda bir necha marta oldinga va orqaga qarab yurib, oxirida biz jarayonni yakunlaymiz, bu holda ro'yxatning o'rtasida bo'lamiz.
SHEYKER saralash algoritmi
(aralash saralash yoki kokteyl saralash)
Sheyker saralash pufakchali saralashdan biroz tezroq ishlaydi, chunki maksimum va minimum elementlar navbatma-navbat massiv bo‘ylab kerakli yo‘nalishda o‘tadi.

Shell saralash usuli

Bu saralash usuli 1959 yilda amerikalik olim Donald Shell tomonidan taklif qilingan bo‘lib, qo‘yish orqali saralashning modifikatsiyasi hisoblanadi.

Shell usulining g'oyasi ketma-ketlikning guruhlarga ajratilgan bir-biridan ma'lum masofada joylashgan elementlarini solishtirishdir. Shell saralash usulida birinchi navbatda bir-biridan ma'lum d masofaga joylashgan elementlar solishtiriladi va tartiblanadi.