Mavzu: Selection sort, Insertion sort Quick sort saralash algoritmlari

Mavzu: Selection sort, Insertion sort Quick sort saralash algoritmlari.

Mundarija:

1. Kirish.

1.1. Mavzuning dolzarbligi;

1.2. Mavzuning maqsad va vazifalari;

2. Asosiy qism.

2.1.Reja1;

2 Insertion sort(joylab saralash).;

. Yakuniy qism.

.1. Xulosa;

2. Foydalangan adabiyotlar;

Insertion sort(joylab saralash)

Insertion sort (Joylab saralash) ham tartibsiz array elementlarini saralash uchun mo’ljallangan. Uning ishlash prinsipi (g’oyasi) huddi qo’ldagi kartani saralashga o’xshab ketadi. Ya’ni tartibsiz turgan kartalar ichidan birini olasiz va uni o’zi turishi kerak bo’lgan joyga joylashtirib qo’yasiz. (Yuqoridagi rasmga qarang)

Insertion sort ham shunday ishlaydi. Algoritm oldin array boshidagi ikkita elementni saralab oladida qolgan elementlarni shularga qarab o’z o’rniga joylashtirib ketaveradi. (Ulardan oldiga, ularning orasiga yoki ulardan keyinga). Har bir element huddi shu tartibda o’z o’rnini topib boraveradi.

Algoritm qanday ishlashini quyidagi animatsiya orqali ham ko’rishingiz mumkin:

Algoritm qadamlari

Array boshidagi ikkita element solishtirib, saralab olinadi.

Qolgan elementlar bitta bitta qarab chiqiladi. (Tashqi iteratsiya)

Har bir element ichki takrorlanish orqali o’z joyiga joylashtirib boriladi. Bu yerda array chegaralaridan o’tib ketib qolmaslikka e’tibor berish kerak.

4. Tashqi takrorlanish tugashi bilan array ham saralangan bo’ladi.

Algoritm murakkabligi

Insertion sort ham Selection va Bubble sort kabi O(n²) vaqt murakkabligi bilan ishlasa ham, lekin ulardan ko’ra samaraliroq algoritm hisoblanadi. Aynan, array elementlari deyarli saralangan holatda Insertion sort algoritmi Merge yoki Quick sort algoritmidan ham ko’ra tezroq ishlaydi.

Tanlovni saralash(Selection sort)

Tanlovni saralash algoritmi qatorni saralanmagan qismdan (o’sish tartibini hisobga olgan holda) minimal elementni bir necha bor topib, boshiga qo’yib qatorni saralaydi. Algoritm berilgan massivda ikkita kichik jadvalni saqlaydi.

1) allaqachon tartiblangan subarray.

2) saralanmagan qolgan subarray.

Tanlash tartibining har bir takrorlanishida tartiblanmagan pastki qatordan minimal element (o’sish tartibini hisobga olgan holda) tanlanadi va saralangan pastki qatorga ko’chiriladi.

Quyidagi misol yuqoridagi qadamlarni tushuntiradi:

Arr [] = 64 25 12 22 11

// arrdagi minimal elementni toping [0 ... 4]

// va uni boshida joylashtiring

11 25 12 22 64

// arrdagi minimal elementni toping [1 ... 4]

// va uni arr [1 ... 4] boshiga joylashtiring.

11 12 25 22 64

// arrdagi minimal elementni toping [2 ... 4]

// va uni arr [2 ... 4] boshiga qo’ying.

11 12 22 25 64

// arrdagi minimal elementni toping [3 ... 4]

// va uni arr [3 ... 4] boshiga qo’ying.

11 12 22 25 64

Quick sort saralash

Tez saralash(quick sort)

Tez saralash (quicksort) algoritmi – Charlz Xoar tomonidan yaratilgan mashxur saralash algoritmidir. Ushbu algoritm n ta elementdan iborat massivni eng uzog’i bilan O(n2) vaqtda saralaydi. Biroq algoritm bajarilish tezligining matematik kutilmasi O(n log n) ga teng va u boshqa shunday tezlikda bajariluvchi algoritmlardan tezroq ishlaydi.Bu algoritm “bo’lib ol va egalik qil” tamoyilining yaqqol misolidir. Bu algotirm rekursiv bo’lib, o’rtacha N*log2N ta solishtirish natijasida saralaydi. Algoritm berilgan massivni saralash uchun uni 2 taga bo’lib oladi. Bo’lib olish uchun ixtiyoriy elementni tanlab undan 2 ta qismga ajratiladi. Lekin o’rtadagi elementni tanlab, massivning teng yarmidan 2 ga ajratgan ma’qul. Tanlangan kalit elementga nisbatan chapdagi va o’ngdagi har bir element solishtiriladi. Kalit elementdan kichiklar chapga, kattalar o’ng tomonga o’tkaziladi (6.3-rasm). Endi massivning har ikkala tomonida xuddi yuqoridagi amallar takrorlanadi. Ya’ni bu oraliqlarning o’rtasidagi elementlar kalit sifatida olinadi va h.k. Misol uchun rasmdagi massivni saralash algoritmini ko’rib chiqamiz.

1. Oraliq sifatida 0 dan n-1 gacha bo’lgan massivning barcha elementlarini olamiz.

2.Oraliq o’rtasidagi kalit elementni tanlaymiz, ya’ni key = ( + ) / 2, i=, j=.

Quicksort algoritimida o’rinlashtrish.

3. Chapdagi i-elementni key bilan solishtiramiz. Agar key kichik bo’lsa, keyingi qadamga o’tamiz. Aks holda i++ va shu qadamni takrorlaymiz.

4. O’ngdagi j-element bilan key solishtiriladi. Agar key katta bo’lsa, keyingi qadamga o’tamiz, aks holda j—va shu qadamni takrorlaymiz.

5. i- va j-elementlarning o’rni almashtiriladi. Agar i

6. Endi shu ko’rilayotgan oraliqda key kalitning chap tomonida elementlar mavjud bo’lsa, ular ustida yuqoridagi amallarni bajarish lozim, ya’ni ko’riladigan oraliq 0 dan key-1 gacha deb belgilanadi va 2-qadamga o’tiladi. Aks holda keyingi qadamga o’tiladi.

7. Endi shu ko’rilayotgan oraliqda key kalitning o’ng tomonida elementlar mavjud bo’lsa, ular ustida yuqoridagi amallarni bajarish lozim, ya’ni ko’riladigan oraliq key+1 dan n-1 gacha deb belgilanadi va 2-qadamga o’tiladi. Aks holda algoritm tugaydi. Shu algoritmga misol ko’rib chiqamiz.

Misol: Talabalar ism-sharifi va tartib raqamidan iborat jadvalni quicksort algritmi bilan saralang va nechta o’rinlashtirish amalga oshirilganini aniqlang.

Foydalangan adabiyotlar;

1.http:\\acm.tuit.uz

2.C/C++ dasturlash tili .

3.Sorting Algorithms in 6 Minutes.

4.Merge-sort with Transylvanian-saxon (German) folk dance

5.http:\\Referat.arxiv.uz

6.http:\\Ziyonet.uz

7.http:\\dastur.uz

8.Algoritmlash asoslari

http://fayllar.org