Amaliy matematika va informatika” yo’nalishi 19. 08 a-guruh talabasi Eshimova Gulsumoyning

1-rasm . Saralash qutisi

Kelgusida algoritmlar tarixi elektron kompyuterlarning rivojlanishi bilan bogliq bolib chiqdi. Bazi malumotlarga kora, bu saralash dasturi kompyuterlar uchun birinchi dastur boldi. Bazi kompyuter dizaynerlari, xususan, EDVAC ishlab chiquvchilari malumotlar saralash vazifasini kompyuterlar uchun eng xarakterli raqamli bolmagan vazifa deb atashdi. 1945 yilda Jon fon Neuman EDVAC uchun bir qator buyruqlarni sinash uchun birlashtirish tartibini dasturini ishlab chiqdi.

1.3. SARALASH ALGORITMLARI VA ULARNING TURLARI.

Dasturlashda eng muhim mavzulardan bo’lgan saralash mavzusi hisoblanadi. Biror bir ma’lumotni saralash yoki qandaydir qolipga solish juda ham muhim. Sababi, tartibsiz ma’lumotlar bilan ishlash doimo noqulayliklar keltirib chiqaradi va bunday tizim sekin va xatoliklarga moyil bo’ladi.

Saralash- massiv elementlarini biror qonun qoida ( o'sish, kamayish, boshlang'ch hafi...raqamlari soni) bo'yicha tartiblashga aytiladi. Saralash algoritmlari kundalik turmushda juda keng foydalaniladi.

Tasavvur qilaylik bizda telefon raqamlari saqlanadigan daftarchasi bor (hali qo’l telefonlari ommalashmagan vaqtni eslang) va undagi nomlar tartibsiz holda yozilgan. Siz, aytaylik, Nodir ismli do’stingizning raqamini topishingiz uchun bu daftarchani boshidan boshlab axtarib chiqishga majbur bo’lasiz, bu esa ko’p vaqtni oladi. Lekin, agar ular alifbo tartibida saralab qo’yilgan bo’lsa, siz to’g’ri N harfiga o’tib izlashni boshlaysiz va vaqtdan bir necha barobarga yutasiz. (Chiziqli va Ikkilik saralash mavzularini eslang)

Biz bu bo’limda saralash deganda, eng oddiy bo’lgan arraydagi ma’lumotlarni saralashni nazarda tutamiz va bu kabi saralash algoritmlarining olti xilini ko’rib chiqamiz:

*Selection sort (Tanlab saralash)

*Bubble sort (Pufakchali saralash)

*Insertion sort (Joylashtirib saralash)

*Quick sort (Tezkor saralash)

*Merge sort (Qo’shib saralash)

*Heap sort (piramidasimon saralash)

Ularning deyarli hammasi ma’lumotlarni taqqoslab ko’rish orqali saralaydi va tayyor saralangan arrayni javob sifatida beradi. Birinchi 3 ta algoritm O(n²) vaqtda ishlasa, 4–5 lari O(nlogn) vaqtda ishlaydi. Algoritmlar bir xil ishni bajarsa va ularning aksariyatining ishlash vaqti ham bir xil bo’lsa, unda ularning hammasi nimaga kerak degan haqli savol tug’iladi.

Algoritm xilma-xilligiga ikkita asosiy sabab keltirish mumkin:

Algoritmlarning ishlash vaqtlari har doim ham bir xil bo’lmaydi va ularning ishlashi qandaydir ma’lum holatlarda o’zgarib turadi. Ya’ni, umumiy holatda biror algoritmdan yomonroq ishlovchi boshqa bir algoritm, aynan, qandaydir holat uchun undan ko’ra yaxshiroq ishlashi mumkin. Buni tushunish uchun quyidagi misolni keltiramiz. Bu yerda turli xil saralash algoritmlarining ishlashi vizual holda bir biri bilan taqqoslangan. Birinchi holatda kiruvchi ma’lumotlar, ya’ni saralanishi kerak bo’lgan ma’lumotlar ixtiyoriy turda va holatda: Bu holatda Heap, Merge, Quick sort kabi algoritmlar o’z ishini boshidagi 3 ta algoritmdan ko’ra ancha tez yakunlayapti. Bu holda e’tibor bergan bo’lsangiz, Insertion sort (birinchi turgani) algoritmi yuqorida aytilgan murakkab algoritmlardan ko’ra bir necha barobar tez ishlashini ko’rishingiz mumkin.

Biz yuqorida holatni, ixtiyoriy va deyarli saralangan ma’lumotlarni saralagan holatni ko’rib chiqdik. Bunday holatlar esa ko’plab topiladi, masalan teskari saralangan, bir turdagi ma’lumotlar ko’p yoki kam bo’lgan va h.k ma’lumotlarni saralash. Har bir holat uchun ma’lum bir algoritmlar qolganlaridan ko’ra tezroq yoki sekinroq ishlab qolishi mumkin. Ikkinchi sabab sifatida esa, albatta, saralash algoritmining xotiradan qo’shimcha joy egallashi va uning turg’unlik xususiyati inobatga olinadi.

Saralash algoritmlarida turg’unlik (stability) deganda, ikkita bir xil elementning ilk holatdagi bir biriga nisbatan o’rninini saralashdan keyin ham saqlab qolishiga aytiladi.

Masalan, 3 1 2 4 1 5 sonlari bor deylik, ularni saralmoqchimiz. Agar biz qo’llagan algoritm saraladan keyin doim birinchi 1 sonini ikkinchi 1 sonidan doim oldin joylashtirsa, bu algoritm turg’un saralovchi algoritm deyiladi. Yana haqli savol tug’ilishi mumkin, “Bu narsaning kimga keragi bor, baribir natija 1 1 2 3 4 5 bo’ladiku?” degan. Albatta, bu holatda turg’unlik ahamiyati sezilmasligi mumkin. Lekin, aytaylik siz biror korxona ishchilari ma’lumotlarini ularning nomiga ko’ra saralagan paytda turg’unlik kerak bo’lib qolishi mumkin. Ya’ni, birinchi Nodirbek ma’lumotlari, ikkinchi Nodirbek ma’lumotlaridan keyin turishi kerak degan kabi. Saralash algoritmlari ichidagi Quick Sort ko’p hollarda Merge yoki Heap sortdan tez ishlagani bilan u turg’un saralash algoritmi hisoblanmaydi (Turg’un holga keltirishning iloji bor). Ko’rib turgangizdek har xil algoritmlar ishlash tezliklari bir xil bo’lgani bilan bizga turli holatlarda aynan bir turdagi algoritm kerak bo’lib qolishi va u biz tuzayotgan tizim samaradorligiga ta’sir qilishi mumkin. Shu sababdan, turli xil saralash algoritmlari ishlashini o’rganish va tushunish professional dasturchi uchun muhim hislatlardan biri hisoblanadi.

Saralashda yana bir asosiy tushunchalardan biri bu massivdir. Massiv deb, bir xil tipga tegishli ma’lumotlarning kompyuter xotirasida joylashuviga aytiladi. Demak, massiv turidagi ma’lumotlar bir xil tipga tegishli bo’lishi lozim.

Massivlar katta miqdordagi ma’lumotlarni qayta ishlashni osonlashtiradi, ularni bir joyga yig’adi va saqlaydi. Keyinchalik biz ularni o’chirishimiz, o’rnini almashtirishimiz, ma’lumot qo’shishimiz va boshqa amallarni bajarishimiz mumkin.

Massiv tarkibida elementlar mavjud bo’ladi. Massivning eng ko’pi bilan ketishi mumkin bo’lgan elementlar soni uning o'lchamini bildiradi. Massivning elementi turgan o’rni uning indeksi deyiladi. Massivning elementiga uning indeksi orqali murojaat qilinadi. Massivning indeksi sifatida butun sonlar xizmat qiladi. Har bir massiv o’zining individual nomiga ega bo’lishi kerak, ya’ni bir xil nomdagi massivlar bo’lmaydi. Ularning nomi oldin e’lon qilingan oddiy o’zgaruvchi nomi bilan ustma-ust tushmasligi kerak. Massivlar o’lchamiga qarab ikki xil bo’ladi: bir o’lchovli massivlar, ko’p o’lchovli massivlar. Array operatori esa massivlarni qidirish, saralash va o'zgartirish ushlarini bajaruvchi sinfi hisoblanadi.

Saralash algoritmlari avvaldan borligiga hozir ham yanada kengayib yangilari chiqib kelyatganini marda tutsak. Bu juda muhim algoritm hosoblanadi.

Saralashlarninh turlariga alohida to'xtaladigan bo'lsak:

*Selection sort(tanlab saralash) 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.

2-rasm. Selection sort (tanlab saralash)ning diogrammasi.

*Bubble sort (pufakchali saralash) algoritmi juda ham oddiy ishlaydi. U shunchaki array boshidan yurib ikkita qo’shni elementlarni ularning katta kichikligiga qarab joyini almashtiradi. Bu orqali har bir to’liq yurib chiqishdan keyin arraydagi eng katta (yoki eng kichik) element arrayning eng oxiriga o’tib qoladi. Ushbu xusiyatiga ko’ra bu algoritm ba’zida Sink sort (Cho’kib saralash) deb ham ataladi. Lekin, albatta, Bubble sort nomi ko’proq jarangdorroq eshitiladi.

Bubble sort algoritmining ishlash tezligi ham O(n²) hisoblanadi (n — array uzunligi). Ya’ni yuqorida ko’rib o’tganimizdek, bitta tashqi takrorlanish har bir qadamida arrayni to’liq ko’rib chiqish kerak bo’ladi.

3-rasm. Bubble (pufakchali) sortning diogrammasi.

* 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. Insertion sort ham shunday ishlaydi. 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.

Algoritm qadamlari:

Array boshidagi ikkita element solishtirib, saralab olinadi, qolgan elementlar bitta bitta qarab chiqiladi. (Tashqi iteratsiya) Har bir element ichki takrorlanish orqali o’z joyiga joylashtirib boriladi. Bu yerda array chegaralaridan o’tib ketib qolmaslikka e’tibor berish kerak.

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 alg oritmidan ham ko’ra tezroq ishlaydi.