16-ma’ruza. Qidiruv va saralash. Оddiy almashtirish usuli bilan saralash

Qo`yish usuli. Saralashning bu bu usulidan foydalanishda tartibga solingan ketma – ketlik xotiraning bosh uchastkasida yaratiladi. Saralash uchun saralangan yozuvlar massivlar uzunligiga teng xotira xajmi ajratiladi. Dastlabki va tartibga solingan ketma – ketlik xotiraning turli uchastkalarida joylashganligi sababli ularni belgilash uchun turli belgilardan foydalanamiz. Dastlabki ketma – ketlik elementlarni Ai , tartibga solinsa ketma – ketlik elementlarini Bj bilan belgilaymiz.
Dastlabki A ketma – ketlikning birinchi elementi Ai xotiraning bosh uchastkasida birinchi pozitsiyani egallaydi, yani B ketma – ketlikning birinchi elementi B1 bo`lib qoladi. A element B1 bilan solishtiriladi. Agar solishtirish natijasida A2Saralash jarayoning xar bir i_ o`tishida Ai element navbati bilan B ketma – ketlikning B1 elementidan boshlab barcha elementlari bilan solishtiriladi. Ai elementidan katta bo`lgan bj aniqlanadi Bj, Bj+1 , Bj+2, …..Bj-1 elementlari bitta pozitsiyaga suriladi va j pozitsiyani egallaydigan Ai elementi uchun joy boshatadi.

A	10	4	11	9	7	2
1 o`tish	10
2 o`tish	4	10
3 o`tish	4	10	11
4 o`tish	4	9	10
5 o`tish	4	7	9	10	11
6o`tish	2	4	7	9	10	11

i	1	2	3	4	5	6
A(i)	10	4	11	9	7	2
O`tishN-^o	1	2	3	4	5	6
K	4	1	5	3	2	0
B(k+1)	2	4	7	9	10	11

10.3-rasm. Qo`yish usulida saralash 10.4-rasm. Xisoblash usulida saralash.

N elementdan iborat ketma – ketlik N o`tishda saralanadi. Birinchi o`tishda solishtirishlar talab etilmaydi, uchunki birinchi element xotiraning birinchi uyasida joylashgan bo`ladi. Keyin xar bir o`tish i- o`tish davomida eng yamon xolda I – 1 solishtirish bajaradi. Dastlabki ketma – ketlik kerakli tartibda saralab bo`lingan xolat eng yamon xisoblanadi.

Solishtirishlarning eng ko`p soni 1 + 2 + 3 +……+ (N-1) arifmetik pragretsiya azolariga teng va quyidagi fo`rmula bilan aniqlanadi.

C_max=

Agar dastlabki ketma – ketlik teskari tartibda tartibga solingan bo`lsa , saralash uchun solishtirishlarning eng kam soni Cmin=N-1 talab etiladi. Solishtirishlarning o`rtacha soni 0,25N2 ga mutanosibdir.
Joy almashtirishlarning eng kam soni no`lga teng va dastlabki ketma – ketlik tartibga solib bo`lingan xollarda shunday bo`ladi. Joy almashtirishning eng ko`p soni Cmax teskari tartibda tartibga solingan dastlabki ketma – ketlik uchun talab etiladi. Joy almashtirishlarning o`rtacha soni 0,25N2 ga mutanosib.
Xisoblash usuli. Tartibga solingan B ketma - ketlik dastlabki ketma – ketlik A ni xotiraning bosh soxasida saralash natijasida yaratildi. Usul shunga asoslanganki , tartibga solingan ketma – ketlikning (K+1) elementi roppa rasa K elementga ortiq , demak (K+1)- pozitsiyasini egallaydi. Saralash jarayonida xar bir i- o`tishda dastlabki ketma – ketlikning i- elementi boshqa barcha qolgan elementlar bilan juftlab solishtiriladi. Agar solishtirish natijasida A > A_j ligi aniqlansa , K son qiynati bittaga oshiriladi. O`tish tugallangandan so`ng K ning qiymati A_i ga nisbatan kichik bo`lgan elementlar soniga teng bo`lib qoladi. Bu ketma – ketlikdagi i-element pozitsiyasining no`meri K+1 ga teng.
Xisoblash usulida saralash namunasi 10.4 – rasmda keltirilgan. Birinchi o`tish natijasida dastlabki ketma – ketlikning birinchi elementi A(1) =10 to`rtta elementga ortiqligi aniqlandi va u uchun K=4 deb belgilanadi. Bu element tartibga solingan D ketma – ketlikda beshinchi pozitsiyani egallaydi. Xuddi shu tartibda ketma – ketlikning boshqa elementlari pozitsiyasi belgilanadi.
N elementlardan iborat ketma – ketlikni saralash uchun N o`tish talab etiladi, xar bir o`tishda N solishtirish bajariladi. O`tishlar va solishtirishlar soni dastlabki ketma – ketlikning tartibga solinganlik darajasiga bog`liq bo`lmaydi. Shu sababli ushbu usul uchun solishtirishlarning eng katta , eng kichik va o`rtacha soni N<sub>2</sub> ga teng.
Xisoblash usulida saralashning ko`rib chiqilgan algoritmidan faqat dastlabki ketma – ketlikda bir xil elementlar, boshqacha aytganda tartibga solingan massivda kalitning qiymati bir yozuvlar bo`lmaganda foydalanish mumkin. Kalitning qiymati bir xil bo`lgan yozuvlar bor, massivlarni saralash uchun algaritimni modifiqatsiyalash zarur.

Misol

Misol1: Tartiblanmagan butun sonlar ketmaketligi berilgan. Sonlar o`ish bo`yicha tartiblansin.(oddiy saralash usuli bilan)
uses crt;
var
r,i,j,n:integer;
a:array[1..100] of integer;
begin
readln(n);
for i:=1 to n do
read(a[i]);
for i:=1 to n do
write(a[i],' ');
writeln;
for i:=1 to n - 1 do
for j:=i+1 to n do
if (a[i]>a[j]) then
begin
r:=a[i];
a[i]:=a[j];
a[j]:=r;
end;
for i:=1 to n do
write(a[i],' ');
end.

Analiz

Algaritmni ishlatib ko`ramiz. Bizga bir olchamli sonli massivni 9 ta elementi berilgan bo`lsin
5 4 7 8 3 1 2 7 8

Dasturni ishlash xolatidagi siql qamlarini tekshiramiz.

I=1, 1 5 7 8 4 3 2 7 8
I=2, 1 2 7 8 5 4 3 7 8
I=3, 1 2 3 8 7 5 4 7 8
I=4, 1 2 3 4 8 7 5 7 8
I=5, 1 2 3 4 5 8 7 7 8
I=6, 1 2 3 4 5 7 8 7 8
I=7, 1 2 3 4 5 7 7 8 8
I=8, 1 2 3 4 5 7 7 8 8

Topshiriqlar

Sodda topshiriqlar:

1. 
   Matndagi simvollar alfabet bo`ycha saralansin
   
2. 
   massiv elementlari kamayish bo`yicha saralansin
   
3. 
   IO`SM berilgan masssivni asosiy dioganal elementlari saralansin
   
4. 
   IO`SM berilgan masssivni 1 - ustun bo`yicha saralansin
   
5. 
   IO`SM berilgan masssivni 1 - satr bo`yicha saralansin
   
6. 
   IO`SM berilgan masssivni n ustun bo`yicha saralansin
   
7. 
   IO`SM berilgan masssivni n satr bo`yicha saralansin
   
8. 
   Matindagi so`zlar alfabit bo`yicha sarlanasin
   
9. 
   Matindagi gaplar alfabit bo`yicha sarlanasin