“Маълумотлар тузилмаси ва алгоритмлар” фанига кириш

• REJA :
• Saralash tushunchasi va uning vazifasi
• 2. Saralash masalasini formal qo‘yilishi
• 3. Ichki saralash usullari:Qat’iy usullar va yaxshilangan usullar

• 5-Mavzu: Ma'lumotlarni saralash algoritmlari. Saralashning qat’iy va yashilangan usullari

Saralash tushunchasi va uning vazifasi

• Saralashdan maqsad - tartiblangan to‘plamda kerakli elementni topishni osonlashtirishdan iborat.

• Izoh

• Saralash – bu berilgan to‘plam elementlarini biror bir tartibda (o‘sish yoki kamayish) joylashtirish jarayonidir.

• dasturlarni translyasiya qilishda;
• ma’lumotlar majmuasini tashqi xotirada tashkil qilishda;
• kutubxonalar, kataloglar, ma’lumotlar bazasini yaratishda va boshq.

• Saralashning tadbiqi

• Ma’lumotlarni xajmi va tuzilishiga nisbatan saralash usullari ikkiga ajraladi, ya’ni ichki va tashqi:
• ichki saralash – bu operativ xotiradagi saralash;
• tashqi saralash – tashqi xotirada saralash.

• Saralash masalasini formal qo‘yilishi

• Berilgan: a1, a2 ,…, an, ob’ektlar to‘plami.
• Talab qilinadi: Berilgan ob’ektlarni tartiblash, ularni shunday ap1, ap2 ,…, apn ketma-ketlikda o‘rinlashtirish lozimki, bunda ularning kalitlari kamaymaydigan tartibda joylashsin: kp1  kp2  …  kpn.

• Def.

• Saralash algoritmi turg‘un deyiladi, agarda saralash natijasida bir hil kalitli ob’ektlarlar bir-biriga nisbatan o‘rinlarini o‘zgartirmasa.

• Samaradorlik mezonlari

• saralashga ketgan vaqt (T(n)=C(n)+M(n), bunda C(n) - taqqoslashlar soni; M(n) - esa o‘rinlashtirishlar soni);
• dasturni ishlab chiqishga ketgan vaqt;
• talab qilinadigan xotira xajmi.

• Saralashga ketgan vaqt uchun quyidagi o‘rinli bo‘ladi:
• O(nlogn)  T(n)  O(n2);
• T(n)=O(n) – ideal holatda.

• Ichki saralash usullari

• Qat’iy usullar

• Yaxshilangan usullar

• Qo‘yish orqali saralash

• 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

• Qo‘yish orqali saralash algoritmi tahlili

• Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat.

• Taqqoslashlar soni:

• O‘rinlashtirishlar soni:

• Saralashga ketgan vaqt: