Mavzu: Saralash va izlash algoritmlari

Mavzu:Saralash va izlash algoritmlari
Reja:
1. Kirish.
1.1. Saralash algoritmlari haqida ma’lumot;
1.2. Saralash algoritmlarining dasturlashdagi o’rni;
2. Asosiy qism.
2.1. Qiduruv ,izlash algoritmlari ;
2.2. Izlash algoritmlari haqida umumiy ma’lumot;
3. Yakuniy qism
3.1. Xulosa;
3.2. Foydalanilgan adabiyotlar;
Bugungi mavzumiz algoritmlashning to’rt asosiy yo’nalishlaridan biri hisoblangan saralash algoritmlariga bagishlanadi. Saralash deb, berilgan obyektlar ketma-ketligini ma’lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash bir necha korsatkichlarga bogliq bolishi mumkin. Misol uchun maktab jismoniy tarbiya darsi. Bu dars boshida bolalar bo’ylariga qarab safda turishadi. Me’yor topshirish jarayonida esa sinf jurnalidagi familyalar ketma-ketligiga qarab topshirishadi. Shu yerning ozida 2ta saralashdan foydalanilyapti. Biri, bo’y uzunligi boyicha, ikkinchisi sinf jurnalidagi orinlar boyicha.
Saralash jarayoni qanday kechadi? Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Bu jarayonni his qilish uchun miyamizdagi tezlik bilan kechayotgan jarayonlarni birma-bir taxlil qilib chiqamiz(buning uchun saralanmagan sonlar ketma-ketligini olamiz):
Sonlar berilishi: 23, 54, 3, 22, 1, 45;
Eng kattasini boshiga otkazamiz: 23, 3, 22, 1, 45, 54;(54 soni har bir son bilan solishtirilib eng katta ekani aniqlandi, 45 esa oz ornida turibdi)
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)

Demak, miyamiz xuddi shu jarayonni takrorlar ekan. Endi bizga ma’lumki, bizning miyamiz o’zi optimal deb bilgan yo’nalishdan ketadi va biz uchun faqat bitta saralash algoritmi mavjud. Ammo dasturlashda bunday deb bo’lmaydi. Dasturlashga talab ortib, bu soha rivojlanib borgani sari unda bir qator sohalardagi kabi tezlikni oshirish muammosi paydo boladi. Chunki ilk kompyuter tizimlarida kompyuter tizimining 30% tezligi, operativ xotirasi saralashga sarflanar edi. Shu o’rinda savol tugiladi, operatsion tizimlarda ham saralashdan foydalaniladimi? Albatta ha! Fikrimiz isbotini hozirda keng foydalaniladigan Total Commander dasturi isbotlaydi. Unda bir necha xil saralash mavjud: fayl turi, nomi, o’zgartirilgan sanasi va olchami. Har birini o’sish yoki kamayish tartibida saralash mumkin. Ha aytgancha, hozirgi tizimlar 30% emas anchagina kamroq tezlik va xotira sarflashadi. Chunki tezlik masalasi tobora yuqori cho’qqiga chiqayotgan va ishlanayotgan ma’lumotlar o’lchami oshib borayotgan bir paytda sekin ishlovchi algoritmlardan foydalanish kulguli. Ma’lumotlar o’lchamlari esa juda katta, shu sabali ularni aniq va tez saralashga ehtiyoj mavjud. Buni amalga oshirish uchun esa yangi algoritmlarga ehtiyoj tug’ila boshladi. Buni yechimi sifatida bir necha turdagi algoritmlardan foydalaniladi.

Ular:
Bubble sort;
Selection sort;
Insertion sort;
Quick sort;
Merge sort.
Bugungi mavzumizda yuqoridagi algoritmlarni nomini keltirish bilangina cheklanamiz. Endi izlash algoritmlariga to’xtalamiz. Ro‘yxatdan zarur axborotni qidirish - nazariy dasturlashning fundamental masalalaridan biri hisoblanadi. Qidiruv algoritmini tahlil qilishda, qidirilayotgan axborot kompyuterda ma‘lumotlar massivi ko‘rinishida joylashgan deb faraz qilamiz. Yozuvlar yoki ro‘yxat elementlari massivda ketma-ket joylashadi va ular o‘rtasida bo‘shliq yo‘q. Ro‘yxatdagi yozuvlar 1 dan N gacha tartiblangan bo‘ladi. Aslida yozuvlar maydonlardan tashkil topgan bo‘ladi, bizni kalit deb ataluvchi maydonlardan bittasining qiymati qiziqtiradi. Ro‘yxatlar kalit maydonlari qiymati bo‘yicha tartiblangan yoki tartiblanmagan bo‘lishi mumkin. Aniq qiymatni qidirish masalasi biror elementni tanlash masalasi bilan bog‘liq. Aytaylik, bizga kattaligi bo‘yicha beshinchi element, oxiridan yettinchi yoki o‘rta qiymatli element kerak.
Qidiruv - bu kompyuter xotirasida ma‘lumotlarni qayta ishlash jarayonida qo‘llaniladigan asosiy amallardan biri hisoblanadi. Bu amalning mazmuni shundan iboratki, berilgan argument bo‘yicha massiv elementlari orasidan shu argumentga mos ma‘lumotni (elementni) aniqlashdan iborat.
Ixtiyoriy ma‘lumot (yoki tuzilma) elementi qandaydir belgisi bilan boshqasidan farq qiladi. Ushbu belgi kalit deyiladi. Kalit takrorlanmas bo‘lishi mumkin, ya‘ni tuzimadagi mavjud bitta element uchun aynan shu kalit qo‘llaniladi. Bunday kalit birlamchi deb ataladi. Elementlarning ma‘lum guruhi uchun takrorlanishi mumkin bo‘lgan kalit ikkilamchi kalit deyiladi, ushbu kalit bo‘yicha ham qidiruv tashkil qilish mumkin. Ma‘lumot elementlarining kalitlari alohida joyda to‘plangan (boshqa jadvalda) bo‘lishi yoki o‘zi alohida yozuvdagi biror bir maydonda saqlanishi mumkin. Bunday ajratib olingan yoki alohida faylda saqlanadigan tashqi kalit deyiladi. Agar kalit yozuvda joylashgan bo‘lsa, u holda ichki kalit deyiladi.
Berilgan argument bo‘yicha qidiruv berilgan argument kaliti bilan aniqlangan algoritm deyiladi. Qidiruv algoritmi ishlashi natijasi ushbu ma‘lumotda joylashishi mumkin yoki u jadvalda mavjud bo‘lmasligi mumkin. Ma‘lumotning mavjud bo‘lmaslik holati ikkita amalda yuz berishi mumkin:
berilgan qiymatning yo‘qligini aniqlashda;
berilgan qiymatni jadvalga qo‘yishda.
Masalan, bizga ro‘yxat elementi kaliti sifatida k berilgan bo‘lsin. Har bir k(i) kalitda r(i)-ma‘lumot mavjud. Qidiruv argumenti - Key. Unga yozuv ma‘lumoti rec mos keladi. Jadvalda ma‘lumotlar tuzilmasiga bog‘liq holda qidiruvning bir nechta shakllari farqlanadi.
Bu masalani yechish uchun ikki xil yondoshuv mavjud: ketma-ket qidiruv va
indeksli ketma-ket qidiruv. Ushbu qidiruv algoritmlarini o‘rganib chiqamiz.
Ketma-ket qidiruv algoritmi
Qidiruv algoritmlarida biror aniq elementni mavjud ro‘yxat elementlarini birma-bir qarab chiqish orqali qidirib topish masalasi hal qilinadi. Ketma-ket qidiruv algoritmida ro‘yxatning saralanganligi ahamiyatga ega bo‘lmasa-da, lekin saralangan ro‘yxatda eng yaxshi natijaga erishiladi. Odatda qidiruv kerakli elementning ro‘yxatda bor yoki yo‘qligini shunchaki tekshirish uchun emas, balki shu kalit-qiymatga ega bo‘lgan ma‘lumotni ajratib olish uchun ham qo‘llaniladi. Masalan, kalit-qiymat qidirilayotgan elementning tartib raqami yoki boshqa unikal (yagona) identifikator bo‘lishi mumkin. Kerakli kalit topilgandan so‘ng dastur shu kalitga mos ma‘lumotlarni o‘zgartirishi yoki shunchaki barcha yozuvlarni ajratib chiqarishi mumkin. Har qanday holatda ham qidiruv algoritmi kalitning joylashgan o‘rnini aniqlash masalasini yechish uchun qo‘llaniladi. SHuning uchun ham qidiruv algoritmlari kerakli kalitdan tarkib topgan yozuv indeksini natija sifatida ajratib beradi. Agar kalit-qiymat topilmasa, u holda qidiruv algoritmi massivning yuqori chegarasidan katta bo‘lgan indeks qiymatini qaytaradi. Maqsadga erishish uchun ro‘yxat elementlari 1 dan N gacha bo‘lgan sonlar yordamida raqamlangan bo‘lsin deb faraz qilamiz. Bu holatda qidirilayotgan kalit ro‘yxatda mavjud bo‘lmasa, algoritm 0 qiymatni beradi . Soddalik uchun ajratib olinadigan kalit-qiymatlar ro‘yxatda takrorlanmaydi deb qabul qilinadi.
Ro’yxatdan kеrakli axborotni izlash nazariy programmalashning fundamеntal masalalaridan biridir. Izlash algoritmlari to’g’risida gap kеtganda axborot dasturdagi bеrilganlar massividan iborat bo’lgan yozuvlarda saqlanadi dеgan nuqtayi nazardan kеlib chiqiladi.Yozuvlar yoki ro’yxat elеmеntlari massivda kеtma-kеt joylashadi. Ko’pincha yozuvlar bir nеcha sohalardan iborat bo’lishi mumkmn, ammo izlashda ushbu sohalardan faqat bittasi(kalit) hisobga olinadi.Yozuvlar kalit sohasi qiymati bo’yicha saralangan yoki saralanmagan bo’lishi mumkin.
Izlash algoritmlari quyidagi guruxlarga bo’linadi:
Kalitlarni qiyoslashga asoslangan(Ketma-ket izlash, Binar izlash, Binar daraxt bo’yicha izlash, Fibonachchi izlash, Interpolyatsion izlash);
Kalitlarning raqamli xususiyatlariga asoslangan(“Bor” bo’yicha, ya’ni tanlab guruxlashtirish usulida, Xeshlash usulida izlash).

Saralangan ro’yxatda yozuvlar kalitning o’sib borish tartibida joylashgan bo’lib, saralanmagan ro’yxatda ular tasodifiy ravishda joylashadi.Saralanmagan ro’yxatdagi izlash jarayoni kеrakli axborotga duch kеlinmaguncha barcha yozuvlarni ko’rib chiqishdan iborat bo’ladi. Bu eng sodda izlash algoritidir. Konkrеt qiymatni izlash tanlash masalasi bilan bog’liq bo’lib, bunda qandaydir xususiyatga ega bo’lgan elеmеntni topish talab etiladi. Masalan, kattalik bo’yicha bеshinchi o’rindagi elеmеnt, ro’yxat oxiridan еttinchi elеmеnt yoki o’rtacha qiymatli elеmеnt.

Fodalanilgan adabiyotlar;

1. 
   Jumanov I.I., Mingboyev N.S.. Informatika. Uslubiy qo’llanma. –
   

Samarqand: SamDU. - 2002.
2 . Nurmuhammedov T.A. IBM PC va MS DOS bilan ishlash. - T.: Fan, Toshkent – 1995.
3. G’ulomov S.S., Shermuhammedov A.T., Begalov B.A. Iqtisodiy
informatika. – T.: “O’zbekiston”, Toshkent. – 1999.
4. Qobilov S.S., Jumanov I.I. SUBD i informasionniye sistemi. –
Samarqand: SamDU. - 1997.
5. Aripov M. Internet va elektron pochta aloqasi. - T.: «Universitet».- 2000.
6. Jumanov I.I., Mingboyev N.S. Hisoblash sistemalarining informatsion
asoslari. – Samarqand: SamDU. – 2002.