3-MAVZU. TANLASH VA JOYLASHTIRISH TURKUMIDAGI MURRAKKABLIKGA EGA SARALASH ALGORITMLARI 

Ushbu mavzuda quyidagi saralash masalasini hal qilish mumkin bo’lgan bir qancha algoritmlar keltirilgan.

Odatda kiritish ketma-ketligi n-chi massiv elementi ko’rinishida bo’ladi, shu bilan birga yana bog’langan ro’yhat ko’rinishida ham bo’lishi mumkin.

Amaliyotda saralanayotdan sonlar kamdan-kam hollarda yakkalangan qiymatlar hisoblanadi. Odatlar ularning har biri yozuv (record) deb nomlanuvchi berilganlarning tarkibiga kiradi. Har bir yozuv(record)da qiymatlarni saralovchi kalitlar bo’ladi. Saralash algoritmi amaliyotda shunday amalga tatbiq qilinishi kerakki, u kalitlari bilan birgalikda tegishli bo’lishi va qayta ishlanishi kerak.

Saralash algoritmi saralash tartibini aniqlovchi beruvchi saralanishiga bog’liq bo’lmagan alohida sonlar yoki ko’pbaytli katta yozuvllar bilan berilganlardan iborat usullarni tasvirlaydi. Shu tariqa, agar saralash masalasi haqida gap ketsa, berilganlar faqat sonlardan iborat bo’ladi.

Nima uchun saralashdan foydalanamiz?

Hisoblash texnikasi sohasidagi ko’plab olimlar saralashni algoritmlarni o’rganishda eng fundamental masala deb qarashadi. Buning bir qancha sabablari bor:

1)    Ba’zan ilovalarda axborotlarni saralasmaslikning aslo iloji bo’lmaydi. Masalan, bankda mijozlarning hisob holatlari to’g’risidagi hisobotni tayyorlash uchun ularning chek nomerlari bo’yicha saralashni bajarish kerak bo’ladi.

2)    Odatda saralash algoritmlarda kalit qismdasturi sifatida ishlatiladi. Masalan, dasturda, turli xil darajalarda bo’lgan grafik obyektlarni vizual berkitishni bajarishda, dastlab ushbu obyektlarni chiqish tartibini o’rnatish uchun obyektlarni “pastdan tepaga” darajalari bo’yicha saralash kerak bo’ladi.

3)    Saralash algoritmlarning ko’plab turli xil texnologiyalar qo’llaniladigan turlari mavjud. Algoritmlarni saralashda turli xil algoritm sinflariga qo’llaniladigan juda ko’p muhim usullardan foydalaniladi.

4)    Algoritmlarni saralash jarayonini amalga oshirishda oldingi qatorga juda ko’plab amaliy muammolar chiqadi. Ko’plab saralash dasturi ishlab chiquvchilarni tanlash shu yoki boshqa vaziyatlarda juda ko’p faktlarga bo’gliq bo’lishi mumkin.  Juda ko’p shunga o’xshash masalalar hal qilishda “kodlarni sozlash” dan ko’ra “algoritmlar” darajasidan foydalanish maqsadga muofiqdir.

Saralash algoritmlari

O’sish yoki kamayish tartibida to’plam elementlarini tartiblangan saralash deyiladi.

Tartiblangan elementlar bilan ishlash tartibsiz joylashgan elementlardan ko’ra qulayroq: kerakli elementlarni yengil topish, olib tashlash, yangilarini qo’yish mumkin.      

Saralash algoritmlarini quyidagi guruhlarga ajratish mumkin (1-rasm):

Odatda saralanayotgan to’plam elementlari yozuvlar deyiladi va ko’rinishida k1, k2, k3, ...kn  yoziladi.

Saralashlar turlicha algoritmlar bajarilsada, yagona natijalarga olib keladi. Ammo saralashlar jarayonida sarfalanadigan vaqt miqdori ularning o‘zaro taqqoslashdagi mezonlardan biri hisoblanadi. Dastur bajarilish vaqti amallar bajarilish soniga va protsessor tezligiga proporsional.

 

Algoritmning vaqt bo‘yicha murakkabligi T_α(V)- ( α algoritm ushun) bilan belgilanadi. Bu yerda V- α algoritm bajarilishi uchun zarur bo‘lgan dastlabki kattaliklar miqdori.

 

Function fast(x:integer):integer; Var m,i:integer; Begin       m:=1;       for i:=2 to x do       m:=m*I; fast:=m end;

1-marotaba bajariladi   2 ta amal (ko‘paytirish va qiymat berish) 2*(x-1) 1-marotaba bajariladi

 

Agar bajariladigan har bir amalni murakkablikning 1-birligi sifatida qabul qilsak, uning qiymati 1+2(x-1)+1=2x ga teng bo‘ladi. Demak, vaqt bo‘yicha murakkablik T_α(V)=2V ekanligi kelib chiqadi. o‘z navbatida bu murakkablik qiymati chiziqli holda fast funksiyasining parametiga bog’liqligi aniqlanadi.

Joylashtirish, qo’shish, piramida va tezkor saralash usullarining bitta umumiy tomoni shundan iboratki, ular berilgan massiv elementlarini juftliklarda taqqoslash prinsipi bo’yicha ishlaydi.

 

Tanlash saralash

Tanlash saralash boshida tartibsiz ro’yhatdan eng kichik elementni tanlanashdan iborat. Shundan so’ng dastlabki ro’yhat o’zgaradi. O’zgartirilgan ro’yhat boshlang’ich ro’yhat sifatida qabul qilinadi va jarayon barcha elementlar tanlangungacha davom etadi. Tanlangan elementlar tartiblangan ro’yhatni hosil qiladi. Masalan, ro’yhatdan eng kichik elementni topish talab etilsin:

2-rasm. Tanlash usulida saralash

 

Boshlang’ich ro’yhatdan tanlangan eng kichik element unga berilgan joyga bir qancha usullar bilan joylashadi:

·        Eng kichik element  i chi marta i chi marta (i=1, 2, …, n) yangi ro’yhat joyiga ko’chirilganda, boshlang’ich ro’yhatning tanlangan element joyiga boshqa katta element joylashadi, bu bilan berilgan ro’yhat uzunligi o’zgarmaydi. Ushbu usulda o’zgartirilgan ro’yhatni boshlang’ich ro’yhat sifatida qabul qilish mumkin.

·        Eng kichik element boshlang’ich ro’yhatning (i=1, 2, …, n)  i chi joyiga joylashadi, i chi joyning elementi esa tanlangan element joyiga joylashadi.

·        Shu bilan birga ko’rinib turibdiki, tartiblangan elementlar keyingi saralashdan chiqariladi, shuning uchun ham har bir keyingi ro’yhatning uzunligi oldingi ro’yhatdan bitta elementga kam bo’lishi kerak.

·        Tanlangan eng kichik element oldingi holda kabi berilgan ro’yhatning i chi joyiga, i chi joy keyingi eng kichik elementni yozish uchun bo’shashi uchun tanlangan elementdan ro’yhatning chap tomonda turgan qismi o’ng tomonga bitta pozitsiya bilan tanlangan element joyni to’ldirish uchun siljiydi. (Ro’yhat elementlari sikl bo’yicha siljiydi).   [3]

Tanlash usulida saralash murakkabligi O(n²) tartibda tashkil qiladi.

Tanlash saralash usulida eng kichik saralanmagan element aniqlanib massivning saralangan qismining oxiriga joylashtiriladi. Bu hol massivning barcha elementlari saralanib bo‘lguncha davom etadi. Bu holatni quyidagicha tasvirlash mumkin.

 

Ushbu saralashning kodini keltirib o‘tamiz:

proсedure TForm1.Button1Click(Sender: TObjest);

var a:array [byte] of integer;

i,j,k,m,z,d:integer;

begin k:=10;

for i := 1 to k do

begin

a[i]:=random(20);

memo1.Lines.Add(inttostr(a[i]));

end;

for j :=1 to k do

begin

m:=a[j];

for i := j to k do begin

if m<a[i] then

begin

m:=a[i];

d:=i;

z:=a[j];

a[j]:=m;

a[d]:=z;

end ;

end;

end;

for i := 1 to k do

memo2.Lines.Add(inttostr(a[i]));

end;

 

proсedure TForm1.Button2Click(Sender: TObjest);

var a:array [byte] of integer;

i,j,k,m,z,d:integer;

begin k:=10;

memo1.Slear;

memo2.Slear;

for i := 1 to k do

begin

a[i]:=random(20);

memo1.Lines.Add(inttostr(a[i]));

end;

for j :=1 to k do

begin

m:=a[j];

for i := j to k do begin

if m>a[i] then

begin

m:=a[i];

d:=i;

z:=a[j];

a[j]:=m;

a[d]:=z;

end ;

end;

end;

for i := 1 to k do

memo2.Lines.Add(inttostr(a[i]));

end;end.

 

Natija.

JOYLASHTIRISH SARALASH USULI

Biz joylashtirish usulida saralash (Insertion-sort)ni ko’rib chiqaylik.  Ushbu saralash algoritmi katta bo’lmagan elementlarni saralashda qo’llaniladi. Saralash jarayonini sonlarni tartiblashdan boshlaymiz. Dastlab chap tomonda bo’sh bo’lsin.So’ng sonlarni chap tomonga joylashtirib boramiz.

massivni joylashtirish usulida saralash (Insertion-sort). Kvadratlar bilan belgilangan massiv elementlarining yuqori qismida elementlar indekslari va kvadratlar ichida mos elementlar qiymatlari berilgan. Bu rasmning a-d qismi for sikliga mos keladi. 1-8 qatorida for sikl iteratsiya psevdokodlari (a)-(d) rasm qismiga mos keladi. Har bir iteratsiyada qora kvadratlarda  A[j] kaliti qiymatlari tashkil topgan bo’lib, undan chapda joylashgan (psevdakodning 5-satri) kulrang kvadratlar bilan taqqoslanadi.

  Rasmda ushbu algoritm A={5,2,4,6,1,3}  massivda qanday ishlashi ko’rsatilgan. j saralanayotgan sonlar indeksini bildiradi. Dastlab j indeksli A massivning har bir for sikl iterasiyasi ikki qismdan tashkil topadi. A[1..j-1]  elementlari saralangan sonlarga mos keladi, A[j+1..n] elementlari esa hali saralanmagan sonlardir. A[1..j-1]  elementlari dastavval 1 dan  j-1 gacha bo’lgan pozitsiyada edi, ammo endi ular saralandi.   elementlarining ushbu xossasini sikl invarianti (loop invariant) deb ataymiz.

Ushbu usulda tartiblanmagan elementlarning ketma-ketligidan navbatma-navbat har bir oldingi tartiblangan element bilan taqqoslanib tanlanadi va mos o’ringa joylashtiriladi.

Birinchi bosqichda ikkita boshlang’ich element taqqoslanadi. Ikkinchi element birinchi elementdan kichik bo’lganligi tufayli, u bitta pozitsiya o’ngga siljiydigan birinchi element joyiga kelib joylashadi. Ketma-ketlikning qolgan qismi esa o’zgarmasdan qoladi.

Ikkinchi bosqichda tartiblanmagan ketma-ketlikdan element tanlanadi va avvalgi ikkita tariblangan elementlar bilan taqqoslanadi. U element avvalgi elementdan kattaligi tufayli, o’z joyida qoladi. So’ngra, to’rtinchi, beshinchi va keyingi elementlar butun ro’yhat (yettinchi bosqichda joyga ega bo’lgunicha) tartiblanmaguncha tahlil qilinadi.

[5]

3-rasm. Joylashtirib saralash

---

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. Introduction to Algorithms, 3rd Edition. MIT Press. USA, 2009.  16-p.

 

[2] Колдаев В.Д. Основы алгоритмизации и программирования: Учебное пособие/ Под ред. проф. Л.Г.Гагариной.-М.:ИД «Форум»: ИНФА-М, 2006.-416 с.: ил. –(Профессиональное образование).

 66-c.

 

[3] Колдаев В.Д. Основы алгоритмизации и программирования: Учебное пособие/ Под ред. проф. Л.Г.Гагариной.-М.:ИД «Форум»: ИНФА-М, 2006.-416 с.: ил. –(Профессиональное образование).

67-68 cc.

 

[4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. Introduction to Algorithms, 3rd Edition. MIT Press. USA, 2009.  17-p.

 

[5] Колдаев В.Д. Основы алгоритмизации и программирования: Учебное пособие/ Под ред. проф. Л.Г.Гагариной.-М.:ИД «Форум»: ИНФА-М, 2006.-416 с.: ил. –(Профессиональное образование).

 68-69 cc.

[6]Robert Sedgewick and Kevin Wayne. Algorithms. FOURTH EDITION. Princeton University. First printing, March 2011. Pp 270 .

[7] Колдаев В.Д. Основы алгоритмизации и программирования: Учебное пособие/ Под ред. проф. Л.Г.Гагариной.-М.:ИД «Форум»: ИНФА-М, 2006.-416 с.: ил. –(Профессиональное образование).

69-70 cc.

[8] Robert Sedgewick and Kevin Wayne. Algorithms. FOURTH EDITION. Princeton University. First printing, March 2011. Pp 270-273.