Saralashning tadbiqi Saralash masalasini formal qo‘yilishi Berilgan: a1, a2 ,…, an, ob’ektlar to‘plami.
Talab qilinadi: Berilgan ob’ektlarni tartiblash, yani 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.
YA’NI: Saralanayotganda bir hil kalitlar uchrashi mumkin, bu holda saralangandan keyin bir hil kalitlilar boshlang’ich tartibda qanday joylashgan bo’lsa, ushbu tartibda qoldirilishi maqsadga muvofiq bo’ladi (Bir hil kalitlilar o’zlariga nisbatan).
Bunday usulga turg’un saralash deyiladi.
Samaradorlik mezonlari 1.Saralashga ketgan vaqt (T(n)=C(n)+M(n), bunda C(n) - taqqoslashlar soni; M(n) - esa o‘rinlashtirishlar soni);
2.Dasturni ishlab chiqishga ketgan vaqt;
3.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.
Agar saralanayotgan yozuvlar xotirada katta xajmni egallasa, u holda ularni almashtirishlar katta sarf (vaqt va xotira ma’nosida) talab qiladi.
Ushbu sarfni kamaytishi maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina ma’lumot ko’rsatkichlari(kalitlar) almashtirilib, massiv o’z joyida qoladi. Yuqoridagi usul adreslar jadvalini saralash usuli deyiladi.
Ma’lumotlarni xajmi va tuzilishiga nisbatan saralash usullari ikkiga ajraladi, ya’ni ichki va tashqi:
