|
University of Management and Future Technologies Fundamental fanlar kafedrasi
|
| bet | 4/7 | | Sana | 27.05.2024 | | Hajmi | 24 Kb. | | #255354 |
Bog'liq Tartiblash va saralash algoritmlari-fayllar.org
Oddiy algoritm
Kichik array’lar uchun mahsuldorlik yuqori
Kamchiliklari:
Katta array’larda mahsuldorlik pasayib ketadi, sababi juda ko’p solishtirishlarni amalga oshirish kerak bo’ladi.
Upper bound – ¼ N2 ~ O(N2). Algoritm mergesort va quicksort bilan solishtirganda yaxshi natija ko’rsatmaydi.
Ishlash konsepti
Arrayning ikkinchi elementini birinchi elementi bilan solishtiramiz. Agar ikkinchi element katta bo’lsa, birinchi element va ikkinchi element o’rnini almashtiramiz.
Arrayning uchinchi elementini ikkinchi elementi bilan solishtiramiz. Agar uchinchi elementi ikkinchi elementidan katta bo’lsa, uchinchi va ikkinchi element o’rnini almashtiramiz. So’ng 1-qadamni takrorlaymiz.
Arrayning to’rtinchi elementini uchinchi elementi bilan solishtiramiz. Agar to’rtinchi elementi uchinchi elementidan katta bo’lsa, to’rtinchi va uchinchi element o’rnini almashtiramiz. So’ng 2-qadamni takrorlaymiz.
Animatsion ko’rinishda:
Insertion sort
Kod:
|
function insertionSort(arr = []) {
|
|
const length = arr.length
|
|
for (let i = 1; i < length; i++) {
|
|
for (let j = i; j > 0; j--) {
|
|
if (arr[j] < arr[j - 1]) {
|
|
// Ikki element o'rnini almashtiramiz.
|
|
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
|
|
}
|
|
else {
|
|
// Keyingi solishtirishlarning foydasi yo'q.
|
|
// Ular allaqachon tartiblangan.
|
|
break
|
|
}
|
|
}
|
|
}
|
|
return arr
|
|
}
|
Note: Funksiya faqat integer sonlarni to’g’ri tartiblaydi. Harflarni yoki string sonlarni tartiblash uchun «<» dan boshqa amalni ishlatish kerak. Masalan, ES6 uchun String.prototype.localeCompare() ni ishlatib ko’ring.
3. Saralash algoritmlari
Saralash - tartiblash (Sorting Algorithms) deb, berilgan obyektlar ketma-ketligini ma`lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash bir necha ko`rsatkichlarga bog`liq bo`lishi mumkin. Misol uchun maktab jurnalida o'quvchilar familiyasi alifbo tartibiga ko'ra saralangan bo'ladi. Masalan bizga sonlar qatori berilgan: 8, 23, 0, -50, 100 Bu qatorni kichigidan kattasiga qarab yoki kattasidan kichigiga qarab saralashimiz mumkin. Bu saralashni amalga oshirish jarayoni Saralash algoritmi deyiladi. Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Yuqoridagi sonli qatorni kichigidan kattasiga qarab tartiblaganimizda -50, 0, 8, 23, 100 ko'rinishiga keladi. Biz buni qanday amalga oshirdik. Bunda har xil usuldan foydalanish mumkin va mana shu algoritm turlaridir Biz algoritmlardan bittasidan foydalanib yuqoridagi sonli qatorni tartiblaymiz. Avval, sonli qatordan eng kichigini topamiz va uni ro'yxatnin g boshiga qo'yamiz. Har bir sonni boshqasi bilan solishtirib chiqamiz. Agar son o'zidan keyingi sondan kichik bo'lsa, son shu joyida qoladi, agar katta bo'lsa sonlarning o'rnini almashtiramiz.
Saralash asosan ro'yxat, massiv elementlarida amalga oshiriladi. Masalan sizning sinfingizda 5 ta o'quvchi bor. Ularni familiyasini alifbo tartibida saralash mumkin.
Sonlar berilishi: 23, 54, 3, 22, 1, 45;
Eng kattasini boshiga o`tkazamiz: 23, 3, 22, 1, 45, 54;(54 soni har bir son bilan solishtirilib eng katta ekani aniqlandi, 45 esa o`z o`rnida turipti) Shu tartibni davom ettiramiz: 3, 22, 1, 23, 45, 54;(23 undan keyinda turuvchi eng katta son) Yuqoridagi amalni yana davom ettiramiz: 3, 1, 22, 23, 45, 54;(22 esa davomchi) Oxirgi marta almashtirishimiz quyidagi natijani beradi: 1, 3, 22, 23, 45, 54;(1 eng kichigi) Saralangan tartib quyidagi holatga keldi: 1, 3, 22, 23, 45, 54;
Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Bu jarayonni his qilish uchun miyamizdagi tezlik bilan kechayotgan jarayonlarni birma-bir tahlil qilib chiqamiz(buning uchun saralanmagan sonlar ketma-ketligini olamiz):
Sonlar berilishi: 23, 54, 3, 22, 1, 45;
|
| |
