|
Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand filiali mustaqil ish
|
| bet | 3/6 | | Sana | 20.12.2023 | | Hajmi | 33.03 Kb. | | #124728 |
Bog'liq Abdurizo a.l.m. (4) Ochiq kodli OT xavfsizligi, Mustaqil ish mavzu ko\'p o\'lchovli regressiya. Reja, BERDIYEV BOBOMUROD 2MAVZU, 1-Amaliy ish (2), 1-Mavzu husnixat metodikasining predmeti, vazifalari va husnixa, 10-ma\'ruza, Болаларни мактаб таълимига тайёрлашINSERTION SORT
"Insertion sort" algoritmi esa elementlarni bir-biridan olganda, har bir elementni oldingi saralgan qismga joylashtiradi. Yangi elementni joylashtirish uchun oldingi saralangan qismni yana saralash lozim bo'lishi mumkin.
Dastur kodi:
def insertionsort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
array = [5, 2, 8, 12, 1]
insertionsort(array)
print("Tartiblangan ro'yxat:", array)
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.
Birinchi mezonni qarab chiqaylik. Saralash bajarilganda taqqoslashlar yoki almashtirishlar sonini hisoblash mumkin.
Faraz qilaylik, N = 0,01n2 + 10n – taqqoslashlar soni. Agar n < 1000 bo'lsa, u holda ikkinchi qo'shiluvchi katta, aks holda ya'ni, n > 1000 bo'lsa, birinchi qo'shiluvchi katta bo'ladi.
Demak, kichkina n larda taqqoslashlar soni n ga teng bo'ladi, katta n larda esa n2 ga teng bo'ladi.
Saralashda taqqoslashlar soni quyidagi oraliqlarda bo'ladi:
dan gacha; – ideal holatda.
Saralashning quyidagicha usullari bor:
qat'iy (to'g'ridan-to'g'ri) usullar;
yaxshilangan usullar.
Qat'iy usullarning afzalliklarini ko'rib chiqaylik:
1. Bilamizki, dasturlarning o'zlari ham xotirada joy egallaydi. To'g'ridan-to'g'ri saralash usullarining dasturlari qisqa bo'lib, ular tushunishga oson.
2. To'g'ridan-to'g'ri saralash usullari orqali saralash tamoyillarining asosiy xususiyatlarini tushuntirish qulay.
3. Murakkablashtirilgan usullarda uncha ko'p amallarni bajarish talab qilinmasada, ushbu amallarning o'zlari ham ancha murakkabdir. Garchi yetarlicha katta n larda ulardan foydalanish tavsiya etilmasada, kichik n larda mazkur usullar tezroq ishlaydi.
Endi murakkab saralash algoritmlarini ko’rib chiqamiz.
|
| |
