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

To’g’ridan-to’g’ri qo’yish algoritmning samaradorligi:

Bu saralash usulida taqqoslashlar soni:

O’rin almashtirishlar soni:

Agar berilgan massiv o’sish tartibida saralangan bo’lsa, u holda taqqoslashlar va o’rinlashtirishlar soni eng kichik bo’ladi, ya’ni

•  

To’g’ridan-to’g’ri tanlash usuli

void sort_selection (key a[], int n)

{ key x;

int i, j, k;

for (i=0; i

k=i;

for (j=i+1; j

if (a[k]>a[j])

k=j;

if (i!=k) {

x=a[i]; a[i]=a[k]; a[k]=x; } } }

Saralash algoritmlarining samaradorligi

To’g’ridan-to’g’ri tanlash algoritmning samaradorligi

Taqqoslashlar soni:

O’rin almashtirishlar soni:

•  

To’g’ridan-to’g’ri almashtirish orqali (pufaksimon) saralash

Ushbu usulni g’oyasi quyidagicha:

• marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi.
• Agar pastki kalit qiymati, undan yuqoridagi juftining qiymatidan kichik bo’lsa, u holda ular o’rni almashtiriladi va h.k.

Pufaksimon saralash algoritmi:

• Eng quyidan boshlab, har bir element, o’zidan yuqoridagi element bilan taqqoslanadi;
• Yuqoridagi element katta bo’lsa, ularning o’rni almashtiriladi;
• Bu almashtirish kichik element massivning eng yuqorisiga “qalqib” chiqqanicha davom ettiriladi.
• Ushbu jarayon massivning har bir elementi uchun takrorlanadi.

•  

To’g’ridan-to’g’ri almashtirish orqali (pufaksimon) saralash

To’rtta elementdan iborat A butun sonli tartiblanmagan massiv berilgan bo’lsin

Algoritmi:

• 3- va 2- element qiymatlari taqqoslanadi va o’rin almashtiriladi;
• 2- va 1- element qiymatlari taqqoslanadi va o’rin almashtiriladi;
• 1- va 0- element qiymatlari taqqoslanadi va o’rin almashtiriladi;
• Natijada massivning eng kichik elementi 2 massivning yuqorisiga “qalqib” chiqadi.
• Ushbu algoritm 2- elementdan boshlab keyingi qism massivda amalga oshiriladi va o’rinlar almashtiriladi, 4 “qalqib” chiqadi.