SARALASH VA QIDIRISH UCHUN SAMARALI ALGORITMLAR
SARALASH VA QIDIRISH UCHUN SAMARALI ALGORITMLAR Mundarija KIRISH .......................................................................................................................................................... 2 Nazariy qism.Eng ko’p ishlatiladigan algoritm turlari. .................................................................................. 4 Joylashtirib saralash (Insertion sort) ........................................................................................................ 4 Qo’shib saralash (Merge sort) ................................................................................................................. 5 Saralash ............................................................................................................................................... 5 Qidirish ................................................................................................................................................ 5 Algoritm turlari bilan tanishish .................................................................................................................... 6 2. MA’LUMOTLARNI SARALASH ALGORITMLARI .......................................................................................... 6 2.1. TO’G’RIDAN-TO’G’RI QO’YISH USULI BILAN SARALASH ALGORITMLARI ........................................... 6 2.2 Tanlash usuli bilan saralash algoritmi ................................................................................................ 7 Saralashga misol. ....................................................................................................................................... 10 2.2. Mа’lumоtlаrni sаrаlаshning аsоsiy usullаri ......................................................................................... 11 3.MA’LUMOTLARNI IZLASH ALGORITMLARI. ............................................................................................. 21 3.1. Axborot izlashning (qidirish) asosiy tamoyillari. .................................................................................. 21 Ketma-ket qidiruv algoritmi ....................................................................................................................... 22 3.2. Kеtma-kеt izlash. ................................................................................................................................ 26 3.3. Izlashning tеzlashtiririlgan usullari. ..................................................................................................... 27 3.4.IKKILIK (BINAR) QIDIRISH ALGORITMI VA UNING TAHLILI. ................................................................... 28 Algoritmning tahlili .................................................................................................................................... 29 4.Amaliy qism. ........................................................................................................................................... 30 XULOSA ...................................................................................................................................................... 33 Foydalanilgan adabiyotlar .......................................................................................................................... 33 1
KIRISH Algoritm-bu cheklangan sonli qadamlar yordamida muammoni hal qilish uchun matematik jarayon. Algoritmlardan foydalangan holda dasturchi yoki kompyuter olimi o'z mashinasiga ma'lumotlar bazasini o'tgan oyning savdo ko'rsatkichlari uchun so'rashini, ularni o'tgan oy va o'tgan yilning o'sha oyi bilan taqqoslashini va keyin uni ustunli grafikada ko'rsatishini aytishi mumkin. Bir nechta algoritmlarni aralashtiring va sizda ishlaydigan kompyuter dasturi mavjud. Kutilganidek, deyarli har qanday matematik muammolarni hal qilish uchun ko'plab turdagi algoritmlar mavjud va bor: Sonli algoritmlar. Algebraik algoritmlar. Geometrik algoritmlar. Ketma-ket algoritmlar. Operativ algoritmlar. Nazariy algoritmlar. Shuningdek, ularni ixtiro qilgan etakchi matematiklar nomidagi turli xil algoritmlar mavjud: Shor algoritmi. Girvan-Nyuman algoritmi. Bir necha Yevklid algoritmlari. Shuningdek, ular hal qiladigan aniq muammo nomi bilan atalganlar mavjud, masalan: Ikki tomonlama qidirish algoritmi. K-yo'l algoritm birlashtirish. 2
Hisoblash sohasida aksariyat algoritmlar ma'lumotlarni boshqarish va tahlil qilish muammolarini hal qilishga moyil. 3
Nazariy qism. Eng ko’p ishlatiladigan algoritm turlari. Puffakchali saralash (Buble sort) “Bubble sort” bu eng sodda, ketma-ketlikdagi har bir sonni boshqa sonlar bilan solishtirishga, asoslangan algoritm hisoblanadi. Unda solishtirish natijasida son noto`g`ri o`rinda turganligi aniqlansa, son o`rni almashtiriladi. Bu jarayon almashtirish kerak bo`lmay qolguncha davom etadi, ya`ni kerakli ketma-ketlikka kelguncha. “Bubble sort” eng ko`p vaqt talab qiluvchi saralash algoritmi hisoblanadi. Chunki unda n ta element uchun takrorlanishlar soni n*n ga teng. Bu, n kichik son bo`lsa unchalik sezilmaydi. Sababi, hozirgi zamonaviy kompyuterlar uchun bu takrorlanish soni qiyinchilik tug`dirmaydi. Ammo butun boshli ma`lumotlar bazasidagi ma`lumotlarni saralash talab etilsachi? Albatta vaqtdan yutqazamiz. Ammo, bu algoritm saralash algoritmlarini tushunib olish uchun ilk qadam hisoblanadi. Tanlab saralash (Section sort) “Selection sort” g’oyasi juda ham oddiy: har qadamda arrayning saralanmagan qismidagi eng kichik (yoki eng katta) elementni topib saralangan qism oxiriga qo’shib ketish. Selection sort eng oddiy saralash algoritmlaridan bo’lib O(n²) vaqt tezligida ishlaydi. Ya’ni, algoritm barcha elementlarni ko’rib chiqish (n-1) mobaynida, har bir qadamda eng kichik elementni topish uchun qolgan elementlarni ko’rib chiqishi kerak bo’ladi. Matematik ko’rinishda quyidagicha bo’ladi: Joylashtirib saralash (Insertion sort) Insertion sort (Joylab saralash) ham tartibsiz array elementlarini saralash uchun mo’ljallangan. Uning ishlash prinsipi (g’oyasi) huddi qo’ldagi kartani saralashga o’xshab ketadi. Ya’ni tartibsiz turgan kartalar ichidan birini olasiz va uni o’zi turishi kerak bo’lgan joyga joylashtirib qo’yasiz. Algoritm oldin array boshidagi ikkita elementni saralab oladida qolgan elementlarni shularga qarab o’z o’rniga joylashtirib ketaveradi. (Ulardan oldiga, ularning orasiga yoki ulardan keyinga). Har bir element huddi shu tartibda o’z o’rnini topib boraveradi. Insertion sort ham Selection va Bubble sort kabi O(n²) vaqt murakkabligi bilan ishlasa ham, lekin ulardan ko’ra samaraliroq algoritm hisoblanadi. Aynan, array elementlari deyarli saralangan holatda Insertion sort algoritmi Merge yoki Quick sort algoritmidan ham ko’ra tezroq ishlaydi. 4
Tezkor saralash (Quick sort) Bu algoritm Charlz Hoar tamonidan 1964 yilda taklif qilingan. Charlz Hoar ingliz olimi, informatika va hisoblash texnikasi sohasida yetuk mutaxassis. Uning “Tezkor saralash” algoritmi saralash bo’yicha eng ommobop algoritm. Bu algoritm ham “Bo’lib tashla va hukmronlik qil” metodiga asoslanadi. Massivda bo’luvchi element X tanlanadi. Elementlarni shunday joylashtiramizki, dastlab X dan kichik yoki teng bo’lgan elementlar joylashsin, keyin undan katta bo’lgan elementlar joylashsin. Keyin ularni alohida saralaymiz. Qo’shib saralash (Merge sort) Bu algoritm Jon fon Neyman tamonidan 1946 yilda taklif qilingan. Jon Fon Neyman Vengriyalik matematika, kvant fizikasi, funksional analiz, to’plamlar nazariyasi, ekonomika, informatika kabi fanlarga munosib hissa qo’shgan. Algoritmlarni qurishning asosiy metodlaridan biri. Murakkab masalani yechish uchun, uni oddiyroq bo’laklarga ajratish kerak. Massivni ham huddi shunday saralash mumkin: 1. Uni ikkita bo’lakga ajratamiz. 2. Bo’laklarni alohida saralaymiz. 3. Saralangan massivlarni birlashtiramiz. Ikkita saralangan massiv berilgan. Ularni birlashtirib shunday massiv hosil qilish qilish kerakki, u yana saralangan bo’lsin. Xar safar hali ikki massivning hali ko’rilmagan qismlaridagi birinchi ikki elementni taqqoslaymiz. Ulardan kichigini olamiz. Saralash Ma'lumotlarni samarali va foydali tarzda tartibga solish. Bularga tez saralash, birlashtirish sort, hisoblash sort va boshqalar kiradi; Qidirish Tartiblangan ma'lumotlar to'plamlarida asosiy ma'lumotlarni topish. Ikkilik qidiruv chiziqli ma'lumotlar tuzilmalarida va tartiblangan ma'lumotlar to'plamlarida qidirish uchun ishlatiladi. Chuqurlik/kenglik birinchi qidirish (DFS / 5