SARALASHNING SHEYKER USULI
Almashish usulida saralash
Almashish usulida saralash- bu ro’yhat elementlari ketma-ket o’zaro taqqoslanadi va avvalgi element keyingi elementdan katta bo’lgan holda joyini almashtiradi. Masalan, ro’yhatni standart almashish usulida saralash talab qilinsin:
{40, 11, 83, 57, 32, 21, 75, 64}.
Almashtiriladigan elementlarni strelkali kvadrat qavslar orqali, taqqoslanayotgan elementlarni esa kvadrat qavslar orqali belgilaymiz. Saralashning birinchi bosqichi 1-rasmda, ikkinchi bosqichi esa 2-rasmda ko’rsatilgan.
Har bir ro’yhatni ko’rishdan so’ng, oxiridan boshlab barcha elementlar o’zlarining oxirgi pozisiyalarini egallashini ko’rish qiyin emas.
Har bir keyingi ko’rib chiqish eng katta element topgan pozitsiyani yo’qotib borib, ro’yhatni qisqartirib boradi. Birinchi ko’rib chiqishdan so’ng oxirgi pozitsiyada 83 ga teng eng katta element qoldi.
Ikkinchi ko’rib chiqishdan eng katta element 75 ga teng ekenligini kelib chiqadi (2- rasmga qarang).
Saralash jarayoni oxirgi ro’yhatning barcha elementlari shakllangunicha davom etadi, aks holda Ayverson sharti bajarilamydi.
Ayverson sharti: agar saralash jarayonida elementlarni taqqoslashda bir marotaba bo’lsa ham o’zgartirish bo’lmasa, u holda to’plam tartiblangan hisoblanadi (Ayverson sharti qadam d=1 bo’lganda bajariladi).
Sheker usulida saralash
Standart almashtirish saralash usulidan biri sheker yoki chelnochnaya saralash hisoblanadi. Bu yerda elementlar o’zaro saralanib boriladi. Bu bilan birinchi o’tish chapdan o’ngga, ikkinchisi esa o’ngdan chapga bo’ladi va hokazo. Bir so’z bilan aytganda, ro’yhat elementlarning yo’nalishi o’zgaradi.
Standart almashish usulining murakkabligi- O(n2 ).[1]
[1] Колдаев В.Д. Основы алгоритмизации и
программирования: Учебное пособие/ Под ред. проф. Л.Г.Гагариной.-М.:ИД «Форум»:
ИНФА-М, 2006.-416 с.: ил. –(Профессиональное образование).
71-72 cc.
Dastur kodi:
Var A : array[1..1000] of integer;
N,i,j,p : integer;
Min, Max : integer;
Begin
readln(n); randomize;
for i:=1 to n do
begin
a[i]:=random(120);
write(a[i],’ ‘);
end;
writeln;
for i:=1 to n div 2 do
begin
if A[i]>A[i+1] then
begin
Min:=i+1;
Max:=i;
end
else
begin
Min:=i;
Max:=i+1;
end;
for j:=i+2 to n-i+1 do
if A[j]>A[Max] then
Max:=j
else
if A[j]<A[Min] then Min:=j;
P:=A[i];
A[i]:=A[min];
A[min]:=P;
if max=i then
max:=min;
P:=A[N-i+1];
A[N-i+1]:=A[max];
A[max]:=P; write(a[i],’ ‘);
end;
writeln;
for i:=1 to n do
write(a[i],’ ‘);
readln;
End.
Olinadigan natija:
Pufakcha (qalqib chiqish) usuli.
A[0], A[1],.., A[N] massivning elementlari berilgan bo‘lsin. Ketma-ket ravishda A[0], va A[1], A[1], va A[2] elementlar o‘zaro taqqoslanib agar A[i]>a[i+1] bo‘lsa, ular o‘zaro o‘rin almashadilar. Ikkinchi qadamda shu holat A[N-1] gacha davom ettiriladi va hokazo. Bu usul hubobcha(qalqib chiqish) usuli deyilishiga sabab har safar hajmi katta «sharcha» element qolganlarini ortda qoldirib yuzaga “qalqib” chiqadi.
Ushbu algoritmni Delphi dasturlash tilida keltirib o‘tamiz.
proсedure TForm1.BitBtn1Сliсk(Sender: TObjest);
var A:ARRAY[1..15] OF INTEGER; I,D,K,Z,QAT:INTEGER;
begin
RANDOMIZE; QAT:=2; StringGrid1.RowSount:=1;
for I := 1 to 15 do
BEGIN
A[I]:=RANDOM(39); StringGrid1.Sells[I,1]:=FloatToStr(A[I]);
END;
K:=14;
while (K>=1) do
BEGIN
I:=1;
while (I<=K) do
BEGIN
if A[I]>A[I+1] then
BEGIN D:=A[I]; A[I]:=A[I+1]; A[I+1]:=D;
END;
I:= I+1;
END;
K:=K-1;
for Z := 1 to 15 do
BEGIN StringGrid1.Sells[Z,QAT]:=FloatToStr(A[Z]); END;
QAT:=QAT+1; StringGrid1.RowSount:=StringGrid1.RowSount+1;
END;
end;
end.
Dastur natijasi:
Piramida usulida saralash[1](Binar) piramidaning tuzilishi butun binar daraxt sifatida qaralishi mumkin bo’lgan obyekt-massivni ifodalaydi (6.1-rasmda keltirilgan).
[1] Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest. Introduction to Algorithms, 3rd Edition. MIT Press. USA, 2009. 152-bet
Binar piramidalarni ikki turga ajratishadi: kamaymaydigan va o’smaydigan. Piramidalarning asosiy xususiyatlaridan biri hisoblanadigan piramidalar xossalari (heap property) qoniqtiradigan ikkala ko’rinishdagi qiymatlar tugunlarda joylashadi. O’smovchi piramidalar xossalari (max-heap property) dan biri har bir i indeksli ildiz tugun uchun quyidagi tengsizlik bajariladi:
Shu tarzda, O’smovchi piramidaning eng katta elementi daraxt ildizida qiymatlari esa qism daraxt tugunlarida joylashgan bo’ladi. Kamayvovchi piramida prinsipi esa mutlaqo teskaridir. Kamayvovchi piramida xossasi (min-heap property) da har bir i indeksli ildiz tugun uchun quyidagi tengsizlik bajariladi:
Shuning uchun ham piramidaning eng kichik elementi
ildizda joylashgan bo’ladi.
Misol. Dastlabki A{2.4.6.3.5.7} to’plam berilgan. Piramida usulida saralash 5-rasmda ko’rsatilgan.
Natijada tartiblangan {2,3,4,5,6,7} to’plam hosil bo’ladi.
Комментарии
Отправить комментарий