Kichik massivlar uchun qo’shilgan saralash. Qo’shilgan saralash

Pufakli saralash usuli.

Nazariy qism

Pufaksimon saralash algoritmi

Ushbu usulning g’oyasi quyidagicha: 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 ularning o’rni almashtiriladi (1-rasm).

Misol: massiv - 4, 3, 7, 2, 1, 6.

1-rasm. Pufaksimon saralash usulida massiv elementlarining o’rnini almashtirish

Pufaksimon usulni massiv elementlarida pastdan yuqoriga va yuqoridan pastga o’tishni bir vaqtda amalga oshirish natijasida yaxshilash mumkin.

Taqqoslashlar soni:

Almashtirishlar soni:

“Pufaksimon” saralash usulini hisoblashga misol.

2-rasm. Massivni pufaksimon saralashga misol

2-rasmda berilgan misolda 5 ta elementdan iborat massiv berilgan. Demak, massivda pastdan yuqoriga (yuqoridan pastga) o’tishlar soni 5-1=4 marta bo’ladi.

Misoldan ko’rinib turibdiki, algoritm ichki siklda 3-qadamdan boshlab massivni “bekor” qayta ishlaydi, 4-qadamni bajarmasa ham bo„ladi.
Berilgan usullarning afzalligi:

1) Eng sodda algoritm;

2) Amalga oshirish sodda;

3) Qo„shimcha o„zgaruvchilar shart emas.

Kamchiliklari:

1) Katta massivlarni uzoq qayta ishlaydi;

2) Har qanday holatda ham o’tishlar soni kamaymaydi.
“Pufaksimon” usulni yaxshilash

1) Agar massivda o„tishlar nafaqat yuqoridan pastga, balki bir vaqtning o’zida pastdan yuqoriga ham bo’lsa, u holda “yengil” elementlar “yuqoriga suzib” chiqadi va “og’ir” elementlar esa “cho’kadi”.

2) Massivda “bekor” o’tishni yo’q qilish uchun, tashqi siklda massiv saralanganligini tekshiruvchi belgi qo’yish lozim.
for (int i=0; i

for (int j=n-1; j>i;j--)

if (a[j]

int x= a[j-1];

a[j-1]=a[j];

a[j]=x;

}

O’rinlashtirish va taqqoslashlar soni: (n* log( n )).

Pufakchali saralash. Saralashlarning turli algoritmlari mavjud bo’lib, ulardan yeng sodda va ko’p qullaniluvchisi-bu "pufakchali" saralashdir.

S (a_ь a₂, ...,a_p) massiv berilgan bo’lsin. S massivning a_i va a_j yelementlari inversiyani tashkil yetiladi deyiladi, qachonki:

i>j uchun a(i)>a(j) bo’lsa.

"Pufakchali" saralashning mazmuni shundan iboratki, Bunda S massivning oxiridan boshiga qarab yelementlar ketma-ket tekshiriladi va inversiyali qo’shni yelementlarning o’rni almashtirib boriladi. Ko’rilayotgan algoritm murakkablik darajasi 0 (n²), ya’ni ixtiyoriy S va n uchun algoritm S n² ta taqqoslash va o’rin almashtirish operasiyalarini bajaradi. Bu yerda S n ga bog’liq bo’lmagan o’zgarmas son. Quyida "Pufakchali" saralashning Beysik algoritmik tilidagi dasturini keltiramiz:

10 REM PUFAKSHALI SARALASH

20 SSREEN 0: COLOR 15,4: KEY OFF

30 INPUT "ELEMENTLAR SONI" ; N: DIM A (N)

40 FOR 1=1 TO N: A(I)=INT(RND(-TIME)*100):NEXT

50 REM O'ZAK

60 FOR 1=2 TO N: FOR J=N TO I STEP -1

70 IF A(J-1)>A(J) THEN SWAP A(J-l), A(J)

80 NEXT J,I

100 FOR 1=1 TO N: PRINT A(I);:NEXT I

110 END

Ushbu dastur kiritilgan p soni bo’yicha tasodifiy butun sonli (0 dan 99 gacha) massiv yaratadi va uni saralaydi. Algoritm o’zagini 50-90 satrlar tashkil yetadi. Bu saralash usuli qo’shimcha xotira talab yetmaydi, ammo ko’p vaqt talab etadii.