Algaritmlash va Loihalash fanidan

Saralash samaradorligini bir necha mezonlar bo’yicha baholash mumkin:

• • saralashga ketgan vaqt;
• • saralash uchun talab qilingan operativ xotira;
• • dasturni ishlab chiqishga ketgan vaqt.
• Birinchi mezonni qarab chiqaylik. Saralash bajarilganda taqqoslashlar yoki almashtirishlar sonini hisoblash mumkin. Faraz qilaylik, N = 0,01n2 + 10n – taqqoslashlar soni. Agar n < 1000 bo’lsa, u holda ikkinchi qo’shiluvchi katta, aks holda ya’ni, n > 1000 bo’lsa, birinchi qo’shiluvchi katta bo’ladi.
• Demak, kichkina n larda taqqoslashlar soni n ga teng bo’ladi, katta n larda esa n2 ga teng bo’ladi.
•  
• 1 dan n gacha; – ideal holatda.

Eng oddiy bo’lgan arraydagi ma’lumotlarni saralashni va bu kabi saralash algoritmlarining olti xilini ko’rib chiqamiz:

• Selection sort (Tanlab saralash)
•  
• Bubble sort (Pufakchali saralash)
•  
• Insertion sort (Joylashtirib saralash)
•  
• Quick sort (Tezkor saralash)
•  
• Merge sort (Qo’shib saralash)
•  
• Radix sort

Saralashning quyidagicha usullari bor:

qat’iy (to’g’ridan-to’g’ri) usullar;

•  
• yaxshilangan usullar.
• Qat’iy usullarning afzalliklarini ko’rib chiqaylik:
• 1. Bilamizki, dasturlarning o’zlari ham xotirada joy egallaydi. To’g’ridan-to’g’ri saralash usullarining dasturlari qisqa bo’lib, ular tushunishga oson.
• 2. To’g’ridan-to’g’ri saralash usullari orqali saralash tamoyillarining asosiy xususiyatlarini tushuntirish qulay.
• 3. Murakkablashtirilgan usullarda uncha ko’p amallarni bajarish talab qilinmasada, ushbu amallarning o’zlari ham ancha murakkabdir. Garchi yetarlicha katta n larda ulardan foydalanish tavsiya etilmasada, kichik n larda mazkur usullar tezroq ishlaydi.

Shu joyni o’zida qat‟iy usullarni ishlash tamoyillariga ko’ra 3 ta toifaga bo’lish mumkin:

• 1. To’g’ridan-to’g’ri qo’shish usuli (by insertion);
• 2. To’g’ridan-to’g’ri tanlash usuli (by selection);
• 3. To’g’ridan-to’g’ri almashtirish usuli (by exchange).
• To’g’ridan-to’g’ri qo’shish usuli bilan saralash algoritmi
• Bunday usul karta o’yinida keng qo’llaniladi. Elementlar (kartalar) 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’yiladi.