Ma’lumotlar tuzilmasi va algoritmlar fanining maqsad va vazifasini izohlab bering

28. Saralash usullariga misollar keltiring, massivda saralash usullarining asosiy g’oyalarini ayting?
Massivlar odatda tezkor xotirada tashkil etiladi. Bunda asosiy kriteriya sifatida saralash uchun sarflanadigan xotirani minimallashtirish hisobga olinadi. Elementlar o’rnini almashtirish ushbu tezkor xotiraning o’zida amalga oshirilishi kerak.
Massivda saralash usullarini uchta sinfga ajratish mumkin:
Qo’shish orqali saralash;
Tanlash orqali saralash;
Almashtirish orqali sarlash:
qat’iy (to’g’ridan-to’g’ri) usullar;
yaxshilangan usullar.
Saralash samaradorligini bir necha mezonlar bo’yicha baholash mumkin:
saralashga ketgan vaqt;
saralash uchun talab qilingan tezkor xotira;
dasturni ishlab chiqishga ketgan vaqt.
Qat’iy saralash usullari
to’g’ridan-to’g’ri qo’yish usuli;
to’g’ridan-to’g’ri tanlash usuli;
to’g’ridan-to’g’ri almashtirish usuli.
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,01n 2 + 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 n 2 ga teng bo„ladi.
Saralashda taqqoslashlar soni quyidagi oraliqlarda bo„ladi:
  n n O log dan  
2
n O gacha;   n O – ideal holatda.
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
112
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).
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,01n 2 + 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 n 2 ga teng bo„ladi.
Saralashda taqqoslashlar soni quyidagi oraliqlarda bo„ladi:
  n n O log dan  
n O gacha;   n O – ideal holatda.
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).