Ma’lumotlar tuzilmasi va algoritmlar fanidan Mustaqil ish Mavzu: Saralash algoritmlari. Saralashning yaxshilangan usullari. «Piramidasimon saralash usuli»

Download 7,86 Kb.
Sana	07.02.2024
Hajmi	7,86 Kb.
	#152878

Bog'liq
MTA M1

O‘ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Dasturiy injinering fakulteti

Ma’lumotlar tuzilmasi va algoritmlar fanidan

Mustaqil ish

Mavzu: Saralash algoritmlari. Saralashning yaxshilangan usullari. «Piramidasimon saralash usuli» va uni qo‘llanishiga doir dastur tuzish.

Bajardi: 313-20 guruh talabasi

Xushnazarov Azizbek
Tekshirdi: Bo‘riyev Yusuf

TOSHKENT 2024
Reja:
1. Saralash algoritmlari haqida.
2. Mashhur saralash algoritmlari.
3. Piramidali saralash usuli.
4. Xulosa.

Saralash algoritmlari haqida
Ma'lumotlarni kompyuterda qayta ishlashda elementning informatsion maydoni va uning mashina xotirasida joylashishini bilish zarur. Shu maqsadda ma'lumotlarni saralash amalga oshiriladi. Demak, saralash – bu ma'lumotlarni kalitlari bo'yicha doimiy ko'rinishda mashina xotirasida joylashtirishdan iborat. Bu yerda doimiylik ma'lumotlarni massivda kalitlari bo'yicha o'sishi tartibida berilishi tushuniladi.
Ma'lumotlarga qayta ishlov berilayotganda ma'lumotning informatsion maydonini hamda uning mashinada joylashishini (adresini) bilish zarur. Saralashning ikkita turi mavjud: ichki va tashqi:
• ichki saralash bu operativ xotiradagi saralash;
• tashqi saralash – tashqi xotirada saralash.
Agar saralanayotgan yozuvlar xotirada katta hajmni egallasa, u holda ularni almashtirishlar katta sarf (vaqt va xotira ma'nosida) talab qiladi. Ushbu sarfni kamaytirish maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina ma'lumot ko'rsatkichlari almashtirilib, massiv o'z joyida qoladi. Bu usul adreslar jadvalini saralash usuli deyiladi.
Saralanayotganda bir xil kalitlar uchrashi mumkin, bu holda saralangandan keyin bir xil kalitlilar boshlang'ich tartibda qanday joylashgan bo'lsa, shu tartibda qoldirilishi maqsadga muvofiq bo'ladi (Bir xil kalitlilar o'zlariga nisbatan). Bunday usulga turg'un saralash deyiladi.
Saralash samaradorligini bir necha mezonlar bo'yicha baholash mumkin:
• saralashga ketgan vaqt;
• saralash uchun talab qilingan operativ xotira;
• dasturni ishlab chiqishga ketgan vaqt.
Sarlash algoritmlariga Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort va boshqalar kiradi. Ularning har biri o’zining kamchiliklari va yutuqlariga ega va qaysini ishlatish malumotlar tuzilmasining turiga va o’lchamiga qarab aniqlanadi.

Mashhur saralash algoritmlari
Ko'p sonli tartiblash algoritmlari mavjud bo'lsada, amaliy dasturlarda bir nechta algoritmlar ustunlik qiladi. Kichik ma'lumotlar to'plamlari uchun Insertion Sort keng qo'llaniladi, katta ma'lumotlar to'plamlari uchun esa asimptotik jihatdan samarali saralash, Heap Sort, Merge Sort yoki Quick Sort algoritmlari qo“llaniladi.
Insertion Sort algoritmi har bir takrorlashda bitta kirish elementini iste'mol qiladi va tartiblangan chiqish ro'yxatini kengaytiradi. Har bir iteratsiyada insertion sort kiritilgan ma'lumotlardan bitta elementni olib tashlaydi, tartiblangan ro'yxatda joylashgan joyni topadi va u erga kiritadi. U hech qanday kirish elementlari qolmaguncha takrorlanadi.
Saralash odatda massivni takrorlash, uning orqasida tartiblangan ro'yxatni ko'paytirish orqali joyida amalga oshiriladi. Har bir massiv pozitsiyasida u yerdagi qiymatni saralangan ro'yxatdagi eng katta qiymatga nisbatan tekshiradi (uning yonida, oldingi massiv pozitsiyasida tekshirilgan). Agar kattaroq bo'lsa, u elementni joyida qoldiradi va keyingisiga o'tadi. Agar kichikroq bo'lsa, u tartiblangan ro'yxatdagi to'g'ri pozitsiyani topadi, bo'sh joy qoldirish uchun barcha katta qiymatlarni yuqoriga siljitadi va o'sha to'g'ri joyga kiritadi.
Heap Sort algoritmi massivni ikkilik max-uyma shaklida qayta tartiblashdan boshlanadi. Keyin algoritm uyning ildizini (yig'imda qolgan eng katta element) so'nggi elementi bilan qayta-qayta almashtiradi, so'ngra uning bir qismi deb e'lon qilinadi. tartiblangan qo'shimcha. Keyin ildiz o'rniga shikastlangan uyum tuzatiladi, shunda eng katta element yana ildizda bo'ladi. Bu to'plamda faqat bitta qiymat qolguncha takrorlanadi.
Merge Sort algoritmi tartibga solinmagan roʻyxatni har birida bitta element boʻlgan n ta pastki roʻyxatlarga bo“ladi (bitta element roʻyxati tartiblangan hisoblanadi). Faqat bitta pastki roʻyxat qolmaguncha yangi saralangan pastki roʻyxatlarni yaratish uchun quyi roʻyxatlarni qayta-qayta birlashtiradi. Bu tartiblangan ro'yxat bo'ladi.
Quicksort — boʻlish tartibiga asoslangan massivni saralash uchun boʻlish va boʻysundirish algoritmining bir turi; Ushbu bo'limning tafsilotlari biroz farq qilishi mumkin, shuning uchun tezkor saralash haqiqatan ham yaqindan bog'liq algoritmlar oilasidir. Kamida ikkita elementdan iborat diapazonga qoʻllanilganda, boʻlinish ketma-ket ikkita boʻsh boʻlmagan pastki diapazonga boʻlinishni keltirib chiqaradi, shunda birinchi kichik diapazonning hech bir elementi ikkinchi kichik diapazonning biron bir elementidan kattaroq boʻlmaydi. Ushbu bo'limni qo'llaganingizdan so'ng, tezkor saralash pastki diapazonlarni rekursiv ravishda saralaydi, ehtimol ulardan bo'linish nuqtasidagi elementni chiqarib tashlaganidan so'ng, bu nuqtada allaqachon oxirgi joylashuvida ekanligi ma'lum. O'zining rekursiv tabiati tufayli, tezkor saralash (masalan, bo'lim tartibi) to'liq massivni saralash bo'lsa ham, katta massivdagi diapazon uchun chaqirilishi mumkin bo'lgan tarzda tuzilishi kerak.
Piramidali saralash usuli.

Download 7,86 Kb.