Reja : Saralash tushunchasi va uning vazifasi

• 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:

Qo’yish orqali saralash usuli psevdocodi :

• Qo’yish orqali saralash usuli psevdocodi :
• For 1=2 to n
• X=a(i)
• for j=i-1 downto 1
• if x
• then a(j+1)=a(j)
• Else go to L
• endif
• Next j
• L : a(j+1)=x
• Next I
• return

• Tanlash orqali saralash

• 1. Berilgan ob’ektlar ichidan eng kichik kalitga ega element tanlanadi.
• 2. Ushbu element boshlang‘ich ketma-ketlikdagi birinchi element a1 bilan o‘rin almashadi.
• 3. Undan keyin ushbu jarayon qolgan n-1 ta element, n-2 ta element va xokazo, toki bitta eng “katta” element qolguncha davom ettiriladi.

• Misol:

• - boshlang’ich holat

• Tanlash 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:

Tanlash orqali saralash algoritmi:

• For i=1 to n-1
• x=a(i)
• K=I
• For j=i+1 to n
• if a(j)< x then
• k=j
• x=a(k)
• endif
• Next j
• a(k)=a(i)
• a(i)=x
• Next i return

• Almashtirish orqali saralash (Pufaksimon)

• Algoritm g’oyasi

• n - 1 marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi jufti kalitidan kichik bo‘lsa, u holda ular o‘rni almashtiriladi.

• Misol:

• Almashtirish 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:

Almashtirish usuli uchun psevdokod:

• For i=2 to n
• for j=n to I step -1
• if a(j)
• x=a(j-1)
• a(j-1)=a(j)
• a(j)=x
• endif
• next j
• next I
• Return
• Bu holatda bitta bo’sh o’tish bo’ladi.Elementlarni ortiqcha almashtirmaslik uchun fl o’zgaruvchi (flajok) kirinish mumkin.

Bu ozgaruvchi agar birorta ham almashtitish bolmasa, false qiymat oladi. Quyida kerakli qo’shimchalar kursiv bilan ko’rsatilgan:

• FL=TRUE
• For i=2 to n
• IF FL=FALSE THEN RETURN
• ENDIF
• FL=FALSE
• for j=n to I step -1
• if a(j)FL=TRUE
• x=a(j-1)
• a(j-1)=a(j)
• a(j)=
• endif
• next j
• next I
• Return
• i.

5-Mavzu bo‘yicha nazorat savollari

• 1. Saralash deganda nima tushiniladi?
• 2. Saralashning vazifasi nimadan iborat?
• 3. Saralashning maqsadi nimadan iborat?
• 4. Qo‘yish orqali saralashning g‘oyasini tushuntirib bering?
• 5. Tanlash orqali saralash tushunchasi?
• 6. Pufaksimon saralash nima?