Ma’lumotlar tuzilmasi Data structures 4-ma’ruza: Saralash usullari

Ichki saralash (massivda saralash)

• 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 algoritmlarining samaradorligi

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

To’g’ridan-to’g’ri qo’yish usuli:

• Bu usulda elementlar xayolan oldindan tayyorlangan ketma-ketlik (a1,...,ai-1) va boshlang’ich ketma-ketliklarga ajratib olinadi.
• i=2 dan boshlab har bir qadamda i bir birlikka oshadi, boshlang’ich ketma-ketlikda i-element chiqarib tashlanadi va tayyor ketma-ketlikka joylashtiriladi. Bunda u kerakli joyga qo’yiladi.

To’g’ridan-to’g’ri qo’yish usuli:

• To’g’ridan-to’g’ri qo’yish usuli sxemasi

To’g’ridan-to’g’ri qo’yish usuli:

• To’g’ridan-to’g’ri qo’yish usuli algoritmi (C++ tilida)

void sort_insertion (key a[], int n)

{ key x;

int i, j;

for (i=1; i

x=a[i];

for (j=i-1; (j>=0)&&(x

a[j+1]=a[j];

a[j+1]=x; }

}

Saralash algoritmlarining samaradorligi