Quick sort algoritmi Merge sort algoritmi Selection sort algoritmi
Download 1.63 Mb.
|
Saralash algoritmlari
- Bu sahifa navigatsiya:
- N = 0,01n 2 + 10n
- 1. Talabalar ismlari bo’yicha berilgan jadvalni alfavit bo’yicha quick sort saralash algoritmi bilan saralansin
- Selection sort saralash algoritmi yordamida saralangan massiv: Insertion sort Foydalanilgan adabiyotlar
MAVZU: Saralash algoritmlari Reja: Quick sort algoritmi Merge sort algoritmi Selection sort algoritmi Insertion sort algoritmi Tuzilma elementlarini saralash Malumotlarni kompyuterda qayta ishlashda elementning informatsion maydoni va uning mashina xotirasida joylashishini bilish zarur. Shu maqsadda malumotlarni saralash amalga oshiriladi. Demak, saralash bu malumotlarni kalitlari boyicha doimiy korinishda mashina xotirasida joylashtirishdan iborat. Bu yerda doimiylik malumotlarni massivda kalitlari boyicha osishi tartibida berilishi tushuniladi. Malumotlarga qayta ishlov berilayotganda malumotning 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 manosida) talab qiladi. Ushbu sarfni kamaytirish maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina malumot korsatkichlari almashtirilib, massiv oz joyida qoladi. Bu usul adreslar jadvalini saralash usuli deyiladi. Saralanayotganda bir xil kalitlar uchrashi mumkin, bu holda saralangandan keyin bir xil kalitlilar boshlangich tartibda qanday joylashgan bolsa, shu tartibda qoldirilishi maqsadga muvofiq boladi (Bir xil kalitlilar ozlariga nisbatan). Bunday usulga turgun saralash deyiladi. Saralash samaradorligini bir necha mezonlar boyicha baholash mumkin: saralashga ketgan vaqt; saralash uchun talab qilingan operativ xotira; dasturni ishlab chiqishga ketgan vaqt. Birinchi mezonni qarab chiqaylik. Saralash bajarilganda taqqoslashlar yoki almashtirishlar sonini hisoblash mumkin. Faraz qilaylik, N = 0,01n2 + 10n taqqoslashlar soni. Agar n < 1000 bolsa, u holda ikkinchi qoshiluvchi katta, aks holda yani, n > 1000 bolsa, birinchi qoshiluvchi katta boladi. Demak, kichkina n larda taqqoslashlar soni n ga teng boladi, katta n larda esa n2 ga teng boladi. Saralashda taqqoslashlar soni quyidagi oraliqlarda boladi: dan gacha; ideal holatda. Saralashning quyidagicha usullari bor: qatiy (togridan-togri) usullar; yaxshilangan usullar. Qatiy usullarning afzalliklarini korib chiqaylik: 1. Bilamizki, dasturlarning ozlari ham xotirada joy egallaydi. Togridan- togri saralash usullarining dasturlari qisqa bolib, ular tushunishga oson. 2. Togridan-togri saralash usullari orqali saralash tamoyillarining asosiy xususiyatlarini tushuntirish qulay. 3. Murakkablashtirilgan usullarda uncha kop amallarni bajarish talab qilinmasada, ushbu amallarning ozlari ham ancha murakkabdir. Garchi yetarlicha katta n larda ulardan foydalanish tavsiya etilmasada, kichik n larda mazkur usullar tezroq ishlaydi. Shu joyni ozida qatiy usullarni ishlash tamoyillariga kora 3 ta toifaga bolish mumkin: 1. Togridan-togri qoshish usuli (by insertion); 2. Togridan-togri tanlash usuli (by selection); 3. Togridan-togri almashtirish usuli (by exchange). 1. Talabalar ismlari bo’yicha berilgan jadvalni alfavit bo’yicha quick sort saralash algoritmi bilan saralansin N o’lchamli massiv berilgan. Uni Merge Sort saraalash algoritmi yordamida o’sish tartibida saralang: Selection sort saralash algoritmi yordamida saralangan massiv: Insertion sort Foydalanilgan adabiyotlar: Masalalar to’plami va o’z miyam, fikrlash hujayralarim! КОНЕЦ! Download 1.63 Mb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling