|
Saralash samaradorligi mezonlari
|
| bet | 75/82 | | Sana | 29.05.2024 | | Hajmi | 6,67 Mb. | | #256570 |
Bog'liq Dasturiy ta\'mnot sifatini ta\'minlashi UMK 2021 2022 (2)Saralash samaradorligi mezonlari - saralashga ketgan vaqt; saralash uchun talab qilingan operativ xotira; dasturni ishlab chiqishga ketgan vaqt.
Saralash samaradorligi (taqqoslashlarga nisbatan) - O(n log n) dan O(n2) gacha; O(n) – ideal holatda.
To’g’ridan-to’g’ri qo’shish usuli bilan saralash - bunda elementlar hayolan “tayyor” a(1),...,a(i-1) va boshlang’ich ketma-ketliklarga bo’linadi. Har bir qadamda (i=2 dan boshlanib, har bir qadamda bir birlikka oshirib boriladi) boshlang’ich ketma-ketlikdan i-chi element ajratib olinib tayyor ketma-ketlikning kerakli joyiga qo’shiladi.
To’g’ridan-to’g’ri tanlash usuli bilan saralash – bunda berilgan elementlar ichidan eng kichik kalitga ega element tanlanadi va ushbu element boshlang’ich ketma- ketlikdagi birinchi element bilan o’rin almashadi. Undan keyin ushbu jarayon qolgan n-1 ta element, n-2 ta element va xokazo, toki bitta eng “katta” element qolguncha davom ettiriladi.
To’g’ridan-to’g’ri almashtirish usuli bilan saralash (pufaksimon) – agar ma’lumotlar jadvali massiv ko’rinishida berilgan bo’lib, uni tashkil etuvchi elementlar soni n ta bo’lsa, u holda n - 1 marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi jufti kalitidan kichik bo’lsa, u holda ular o’rni almashtiriladi.
Quiksort – mazkur usul almashtirish usulidagi saralashning modifikasiyasi bo’lib, bunda uning asosini kalitlarni tanlangan kalitga nisbatan ajratish tashkil qiladi. Algoritm samaradorlig: O(n log n).
Shell saralashi (qisqarib boruvchi qadamlar orqali saralash) – mazkur usul to’g’ridan to’g’ri qo’shish usulini modifikasiyasi bo’lib, 1959 yilda D. Shell tomonidan taklif qilingan. Mazkur algoritmning g’oyasi quyidagicha. Faraz qilaylik, a[0],a[1],a[2],…, a[n] boshlang’ich elementlar ketma-ketligi bo’lsin. 1-qadam. Boshlang’ich ketma-ketlikning har r1 o’rinda joylashgan elementlari guruhlanib, har bir guruh alohida qo’shish usuli orqali saralanadi({a[0], a[r1], a[2*r1],…,}, {a[1], a[1+r1], a[1+2*r1],…,} v.h.). 2-qadam. Hosil qilingan ketma-ketlikda har r2 o’rinda joylashgan elementlar guruhlanib, har bir guruh alohida saralanadi va xokazo k-qadam. k-1 qadamda hosil bo’lgan ketma-ketlik oddiy qo’shish usuli orqali saralanadi. Eslatma: r1>r2>…>rk-1>rk=1.
Xeshlashtirish – ma’lumotlarni ma’lumotlar jadvaliga joylashtirish bo’lib, bundan maqsad kelgusida kerakli element joylashgan o’rinni tez aniqlashdir.
|
| |
