logo
  1. Главная страница
  2. Дипломные работы
  3. Общий
  4. MA’LUMOTLARNI SARALASH. SARALASHNI BIRLASHTIRISH(SILYANIE)USULI

MA’LUMOTLARNI SARALASH. SARALASHNI BIRLASHTIRISH(SILYANIE)USULI

Загружено в:

12.08.2023

Скачано:

0

Размер:

567.318359375 KB
Скачать
“ MA’LUMOTLARNI SARALASH. SARALASHNI BIRLASHTIRISH(SILYANIE)USULI ” Reja: • .Kirish.Algoritm haqida tushuncha • . Birlashtirib saralash • Amaliy qism 1. Birlashtirib saralash (Merge sort) 2.Dastur kodi 3.Birlashtirish algoritmi qay tarzda ishlashi haqida • ..Xulosa • . Foydalanilgan adabiyotlar “Algoritm — bu dasturchilar o’zlari nima qilayotganliklarini boshqalar bilmasligini xohlagan paytida ishlatadigan so’zlari” — Unanonymous. Kirish.Algoritm haqida tushuncha Algoritm so’zi al-Xorazmiyning arifmetikaga bag’ishlangan asarining dastlabki betidagi “Dixit Algoritmi” (“dediki al-Xorazmiy” ning lotincha ifodasi) degan jumlalardan kelib chiqqan. Shundan so’ng al-Xorazmiyning sanoq sistemasini takomillashtirishga qo’shgan hissasi, uning asarlari algoritm tushunchasining kiritilishiga sabab bo’lganligi ta’kidlab o’tiladi. Algoritm nima degan savolga, u asosiy tushuncha sifatida qabul qilinganligidan, uning faqat tavsifi beriladi, ya’ni biror maqsadga erishishga yoki qandaydir masalani yechishga qaratilgan ko’rsatmalarning (buyruqlarning) aniq, tushunarli, chekli hamda to’liq tizimi tushuniladi. Algoritm tushunchasi aniq shaklda 20-asr boshlarida D. Gilbert, K. Gyodel, S. Klin, A. Chyorch, E. Post, A. Tyuring, N. Viner, A. A. Markov singari olimlarning asarlari tufayli shakllandi. Eng qadimiy raqamli algoritmlardan biri Yevklid algoritmi (miloddan avvalgi III asr) deb hisoblanadi - ikki sonning eng katta umumiy bo'luvchisini topish. Algoritmlarning zamonaviy nazariyasi nemis matematikasi Kurt Gyodel (1931) asarlari bilan boshlandi, ular o'zlarining rasmiy, izchil aksiomalar tizimi doirasida yechib bo'lmaydigan muammolar mavjudligini ko'rsatdi. Algoritmlar nazariyasi bo'yicha birinchi fundamental ishlar 1936-yilda paydo bo'lgan. Tyuring mashinasi, Post va Chyorch tomonidan λ-hisobi taklif etiladi. Ushbu mashinalar algoritmning formallashtirilgan rasmiylashtirilishi edi. Algoritmni bajarayotgan kishi – ijrochi, asosiy algoritmni aniqlashtiruvchi algoritm – yordamchi algoritm ekanligini ham ta’kidlab o’tish joiz. Umuman, algoritmning 5 ta qanday maqsadga mo’ljallanganligidan qat’i nazar uni muvaffaqiyat bilan bajarish mumkinligini aytib o’tish lozimdir. Algoritmning bir nechta ta’rifi mavjud. Ulardan ayrimlarini keltirib o’tamiz: – “Algoritm - bu belgilaydigan cheklangan qoidalar to'plami, muayyan vazifalar to'plamini hal qilish bo'yicha amallar ketma -ketligi va beshta muhim xossaga ega: aniqlik, tushunarlilik, kiritish, chiqarish, samaradorlik”. (D. E. Knut). – “Algoritm - bu qat'iy belgilangan qoidalar asosida bajariladigan har qanday hisoblash tizimidir, bu ma'lum bir qator bosqichlardan so'ng, aniq qo'yilgan masalani hal qilishga olib keladi" (A. Kolmogorov) – “Algoritm - bu har xil boshlang'ich ma'lumotlardan kerakli natijaga o'tadigan 2 hisoblash jarayonini belgilaydigan aniq ketma-ketlik" (A. Markov). 1950-yillarda algoritm nazariyasiga o'z hissalarini Kolmogorov va Markov asarlari qo'shgan. 1960-1970 yillarda algoritm nazariyasida tadqiqot yo'nalishlari shakllandi: 1) Algoritmlarning klassik nazariyasi (rasmiy tillar nuqtai nazaridan masalalarni shakllantirish, yechuvchanlik muammosi tushunchasi, murakkablik sinflarini kiritish, P = NP (?) masalasini shakllantirish, NP-ning to'liq masalalarini sinfi va uni o'rganish); 2) Algoritmlarni asimptotik tahlil qilish nazariyasi (algoritmning murakkabligi tushunchasi, algoritmlarni baholash kriteriyal ari, asimptotik baholarni olish usullari, xususan, rekursiv algoritmlar uchun, murakkablikni yoki bajarilish vaqtini asimptotik tahlil qilish); 3) Hisoblash algoritmlarini amaliy tahlil qilish nazariyasi (funksiyalarning intervalli tahlili, algoritmlar sifatining amaliy mezonlari, ratsional algoritmlarni tanlash metodikasi). Algoritmning aniq yoki bilvosita turli xil ta'riflari bir qator talablarni keltirib chiqaradi: - algoritmda cheklangan miqdordagi elementar bajarilishi mumkin bo'lgan ketma ketlik bo'lishi kerak, ya'ni yozuvning aniqligi talabi bajarilishi kerak; - algoritm masalani yechishda cheklangan sonli bosqichlarni bajarishi kerak, ya'ni harakatlarning aniqligi talabi bajarilishi kerak; - barcha qabul qilingan kirish ma'lumotlari uchun algoritm bir xil bo'lishi kerak, ya'ni universallik talabiga javob berish; - algoritm qo'yilgan vazifaga nisbatan to'g'ri yechimga olib kelishi kerak, ya'ni to'g'rilik talabi bajarilishi kerak. Algoritm xossalari Algoritmning asosiy xossalari haqida quyidagilarni ta’kidlash mumkin: 1-xossa . Diskretlilik, ya’ni algoritmni chekli sondagi oddiy ko’rsatmalar ketma ketligi shaklida ifodalash mumkin. 2-xossa . Tushunarlilik, ya’ni ijrochiga tavsiya etilayotgan ko’rsatmalar uning uchun tushunarli bo’lishi shart, aks holda ijrochi oddiy amalni ham bajara olmay qolishi mumkin. Har bir ijrochining bajara olishi mumkin bo’lgan ko’rsatmalar tizimi mavjud. 3-xossa . Aniqlik, ya’ni ijrochiga berilayotgan ko’rsatmalar aniq mazmunda bo’lishi lozim hamda faqat algoritmda ko’rsatilgan tartibda bajarilishi shart. 4-xossa . Ommaviylik, ya’ni har bir algoritm mazmuniga ko’ra bir turdagi masalalarning barchasi uchun yaroqli bo’lishi lozim. Masalan, ikki oddiy kasr umumiy maxrajini topish algoritmi har qanday kasrlar umumiy maxrajini topish uchun ishlatiladi. 3 5-xossa . Natijaviylik, ya’ni har bir algoritm chekli sondagi qadamlardan so’ng albatta natija berishi lozim. Bu xossalar mohiyatini o’rganish va konkret algoritmlar uchun qarab chiqish talabalarning xossalar mazmunini bilib olishlariga yordam beradi. Algoritmning tasvirlash usullari Algoritmning tasvirlash usullari haqida gapirganda algoritmning berilish usullari xilma-xilligi va ular orasida eng ko’p uchraydiganlari quyidagilar ekanligini ko’rsatib o’tish joiz: 1. Algoritmning so’zlar orqali ifodalanishi. 2. Algoritmning formulalar yordamida berilishi. 3. Algoritmning jadval ko’rinishida berilishi, masalan, turli matematik jadvallar, loteriya yutuqlari jadvali, funksiyalar qiymatlari jadvallari bunga misol bo’ladi. 4. Algoritmning dastur shaklida ifodalanishi, ya’ni algoritm kompyuter ijrochisiga tushunarli bo’lgan dastur shaklida beriladi. 5. Algoritmning algoritmik tilda tasvirlanishi, ya’ni algoritm bir xil va aniq ifodalash, bajarish uchun qo’llanadigan belgilash va qoidalar m ajmui algoritmik til orqali ifodalashdir. Ulardan o’quv o’rganish tili sifatida foydalanilmoqda. Bo’lardan Ye-praktikum yoki Ye-tili algoritm ijrochisi algoritmik tili ham mavjud. 6. Algoritmlarning grafik shaklda tasvirlanishi. Masalan, grafiklar, sxemalar ya’ni blok - sxema bunga misol bo’la oladi. Blok sxemaning asosiy elementlari quyidagilar: oval (ellips shakli)-algoritm boshlanishi va tugallanishi, to’g’ri burchakli to’rtburchak-qiymat berish yoki tegishli ko’rsatmalarni bajarish. Romb - shart tekshirishni belgilaydi. Uning yo’naltiruvchilari tarmoqlar bo’yicha biri ha ikkinchisi yo’q yo’nalishlarni beradi, parallelogramm- ma’lumotlarni kiritish yoki chiqarish, yordamchi algoritmga murojaat - parallelogramm ikki tomoni chiziq, yo’naltiruvchi chiziq - blok-sxemadagi harakat boshqaruvi, nuqta-to’g’ri chiziq (ikkita parallel) - qiymat berish. Algoritmda bajarilishi tugallangan amallar ketma-ketligi algoritm qadami deb yuritiladi. Har bir alhoxida qadamni ijro etish uchun bajarilishi kerak bo’lgan amallar haqidagi ko’rsatma buyruq deb aytiladi. Algoritmlarni ko’rgazmaliroq qilib tasvirlash uchun blok-sxema, ya’ni geometrik usul ko’proq qo’llaniladi. Algoritmning blok-sxemasi algoritmning asosiy tuzilishining yaqqol geometrik tasviri: algoritm bloklari, ya’ni geometrik shakllar ko’rinishida, bloklar orasidagi aloqa esa yunaltirilgan chiziqlar bilan ko’rsatiladi. Chiziqlarning yunalishi bir blokdan so’ng qaysi blok bajarilishini bildiradi. Algoritmlarni ushbu usulda ifodalashda vazifasi, tutgan o’rniga qarab quyidagi geometrik shakl(blok) lardan foydalaniladi. Algoritmlar berilishi va ifodalanishiga qarab: chiziqli, tarmoqlanuvchi va 4 takrorlanuvchi turlarga bo’linadi. Algoritmning turlari bilan tanishtirganda, avvalo hech qanday shart tekshirilmaydigan va tartib bilan faqat ketma-ket bajariladigan jarayonlarni ifodalaydigan chiziqli algoritmlar aytib o’tiladi. Algoritm xato natijalarni keltirib chiqaradigan yoki umuman natija bermaydigan bo'lsa, xatolarni o'z ichiga oladi. Algoritm har qanday to'g'ri kirish uchun to'g'ri natijalarni beradigan bo'lsa, xatosiz bo'ladi. Ma'lumotlarni kirish va chiqish turlari bo'yicha farqlash mumkin - Raqamli masalalarni yechish algoritmlari (birinchi bo'lib paydo bo'ldi); - Raqamli bo'lmagan algoritmlar. Birlashtirib saralash algoritmlari. Samarali saralash algoritmlari. Birlashtirib saralash algoritmlari. Birlashtirib saralashni rekursiv va rekursiv bo'lmagan algoritmlari. Vaqt va xotira bo`yicha murakkabliklar tahlili. Merge prosedurasi birlashtirib saralashni asosiy prosedurasi sifatida. Birlashtirish protsedurasi bajarilishda xotirani tejash. Tashqi birlashtirib saralash. Tahlil va murakkablik. Ma’lumki, inson kundalik turmushida turli - tuman ishlarni bajaradi. Har bir ishni bajarishda esa bir qancha elementlarni ketma - ket amalga oshirishga to‘g‘ri keladi. Mana shu ketma-ketlik yozilsa, u bajariladigan ishning algoritmi bo‘ladi. Algoritm ma’lum bir buyruqlar to‘plami bo‘lib, bajaruvchi uchun aniq ko‘rsatmalarni o‘z ichiga mujassamlashtiradi. Ushbu buyruqlar bajaruvchiga ko‘rsatilgan maqsadga erishish uchun asos bo‘lishi kerak. Demak, qo‘yilgan masalani bajarish ma’lum ketma-ketlikda elementlarni ijro etish orqali erishiladi. Bunda algoritmni bajaruvchi algoritm ijrochisi hisoblanadi. Umuman, uni 2 guruhga ajratish mumkin: 1-guruh algoritmlarining ijrochisi faqat inson bo‘lishi mumkin. 2-guruh algoritmlarining ijrochisi ham inson, ham kompyuter bo‘lishi mumkin. Bu guruh algoritmlari ijrochisini kompyuter zimmasiga yuklash mumkin. Buning uchun algoritmni kompyuter tushunadigan biror dasturlash tilida yozib, keyin uning xotirasiga kiritish kifoya. Umuman olganda ijrochi algoritmda mavjud maqsadni bilmaydi. U bevosita keltirilgan buyruqlarni bajaradi. Informatikada algoritmlarning ijrochisi kompyuter deb hisoblanadi. 5 Shunday qilib, biz , algoritm deganda , berilgan masalani yechish uchun ma’lum tartib bilan bajarilishi lozim bo‘lgan chekli sondagi ko‘rsatmalar ketma - ketligini tushunamiz. Algoritmlarni yozish uchun qo‘llaniladigan tillar algoritmik tillar deb ataladi. Algoritmik tilni kompyuter ham tushunsa, u holda bu til dasturlash tili deb ataladi. Demak, algoritmik yoki dasturlash tillari ham berilgan masalani yechish algoritmining yozish usullaridan biri hisoblanar ekan. Algoritmlarni o‘rganish davomida biz quyidagi asosiy tushunchalar bilan tanishamiz: algoritm, blok-sxema , chiziqli algoritmlar, tarmoqli algoritmlar, takrorlash jarayonlari, iteratsion jarayonlar. Biror masalani kompyuterda yechishda eng muhim va ma’suliyatli ishlardan biri bu masalani yechish algoritmini yaratish bo‘lib, bu jarayonda bajarilishi lozim bo‘lgan barcha bo‘lajak buyruqlar ketma-ketligi aniqlanadi. Algoritmda yo‘l qo‘yilgan xatoliklar hisoblash jarayonining noto‘g‘ri bajarilishiga olib keladi , bu esa, o‘z navbatida, xato natijaga olib keladi. Umuman, istalgan masalaning yechimi deyilganda, masalani yechish algoritmi mavjudligi va ushbu algoritm natijaga erishishini ta’minlashi zarurligi tushuniladi. Masalalarni, ularning qo‘yilishi bo‘yicha, 4 ta sinfga ajratish mumkin. 1. Aniq ta’riflangan va yechimga erishadigan algoritmlari mavjud masalalar. Ushbu sinfga doir masalalar bevosita to‘g‘ridan - to‘g‘ri kompyuterda bajariluvchi dasturlarga aylantirilishi mumkin. 2. Masala qo‘yilishida yoki uning yechimida noaniqliklar mavjud bo‘lib, algoritmda ushbu noaniqliklarni e’tiborga olish zaruriyati paydo bo‘ladi. Bu yerda asosan tashqi muhitning o‘zgarishi bilan algoritmning shunga moslanishi nazarda tutiladi. 3. Bilimlarni qayta ishlash doirasida berilgan idrokiy masalalar. Bu yerda mantiqiy tushunchalar bilan ishlay oladigan algoritmik tillarning mavjudligi va ular asosida kompyuter uchun dasturlar yaratish mumkinligi nazarda tutiladi. 4. Inson faoliyatiga bog‘liq masalalarni modellashtirishga qaratilgan bo‘lib, aniq yechish algoritmlari mavjud bo‘lmagan masalalar. Ya’ni inson faoliyatini ma’lum bir model doirasida dasturlash mumkinligi nazarda tutilgan bo‘lib, algoritm ushbu faoliyatni to‘liq qamrab ololmaydi, masalan, shaxmat o‘yini. Berilgan masala algoritmini yozishning turli usullari mavjud bo‘lib, ular qatoriga so‘z bilan , blok-sxema shaklida , formulalar, operatorlar yordamida, algoritmik yoki dasturlash tillarida yozish kabilarni kiritish mumkin. Endi biror usulda tuzilgan algoritmning ayrim xossalarini va ularga qo‘yilgan talablarni ko‘rib chiqaylik. 1) Algoritm har doim to‘liq bir qiymatlidir, ya’ni uni bir xil boshlang‘ich qiymatlar bilan ko‘p marotaba qo‘llash har doim bir xil natija beradi. 6 2) Algoritm birgina masalani yechish qoidasi bo‘lib qolmay, balki turli-tuman boshlang‘ich shartlar asosida ma’lum turdagi masalalar to‘plamini yechish yo‘lidir. 3) Algoritmni qo‘llash natijasida chekli qadamdan keyin natijaga erishamiz yoki natijaga erishish mumkin emasligi haqidagi ma’lumotga ega bo‘lamiz. Yuqorida keltirilgan xossalarni umumlashtirib , algoritmlarning quyidagi asosiy xossalarini ta’kidlash zarur. 1. Algoritm boshlang‘ich qiymatli argumentlarga ega bo‘ladi. Algoritmni bajarishdan maqsad bu natija olishdir, ya’ni algoritm boshlang‘ich qiymatlarni biror usul orqali natijaga aylantiruvchi avtomatdir. Demak, algoritmni qo‘yilgan masalaning har xil boshlang‘ich qiymatlari uchun qo‘llash mumkin. Lekin algoritmning ijrochisi inson bo‘lsa, boshlang‘ich qiymat ko‘rsatilmagan bo‘lishi ham mumkin , masalan, “qogozda kvadrat chizing”. Har xil boshlang‘ich qiymatlar ishlatilishi mumkin bo‘lganligi sababli algoritmning ommaviylik xossasi yuzaga keladi. Lekin ba’zi-bir hollarda faqatgina individual boshlang‘ich qiymatga mo‘ljallangan algoritm ham mavjud bo‘ladi. 2. Algoritm ijrochiga tushunarli bo‘lishi lozim, ya’ni ijrochining bazasida mavjud bo‘lgan buyruqlar qo‘llanilishi zarur. Shu bois, algoritmni yaratish jarayonida ijrochining imkoniyatlari va nozik tomonlari e’tiborga olinishi darkor. 3. Algoritm cheklangan qadamlar ketma-ketligidan iborat bo‘ladi va har bir qadam to‘liq bajarilgandan so‘ng keyingi qadamga o‘tiladi. Ushbu xossa algoritmning diskretli xossasi deb ataladi. 4. Algoritm chekli qadamlar bajarilgandan so‘ng tugatiladi. Ya’ni chekli qadamlardan so‘ng algoritm natijaga erishishi kerak yoki natija olish mumkin emasligi aniqlanishi lozim. Ushbu xossa algoritmning natijaviylik xossasi deb ataladi. 5. Algoritmning har bir qadami aniq ta’riflangan bo‘lib, ko‘p ma’noli bo‘lishi mumkin emas. Ya’ni har bir qadamdan so‘ng keyingi qadam aniqlangan bo‘lishi yoki algoritm tugatilishi kerak. Algoritmning ushbu xossasi aniqlik xossasi deb yuritiladi va algoritmni bevosita kompyuterda bajarish uchun imkon beradi. Ushbu xossaga binoan, bir xil boshlang‘ich qiymatlar bilan bajariladigan algoritm doimo bir xil natijaviy qiymatlar bilan tugallanadi. 7 Birlashtirib saralash (Merge sort) Birlashtirib saralash (Merge sort) – tartiblashning tezkor bajariladigan algoritmlaridan biri. Ushbu tartiblash “bo’lib tashla va hukmronlik qil” prinsipining yaxshi namunasidir. Birinchidan, vazifa bir nechta kichik topshiriqlarga bo'linadi. Keyin ushbu vazifalar rekursiv chaqiruv yordamida yoki to'g'ridan-to'g'ri ularning hajmi yetarlicha kichik bo'lsa hal qilinadi. Nihoyat, ularning y echimlari birlashtirilib, asl muammoning echimi olinadi. Algoritmning bajarilishi. Saralash muammosini hal qilish uchun uch bosqich quyidagicha bo’ladi: 1. Saralanadigan massiv taxminan bir xil o'lchamdagi ikki qismga bo'linadi; 2. Olingan qismlarning har biri alohida saralanadi (masalan, xuddi shu algoritm bo'yicha saralanadi); 3. Yarim kattalikdagi ikkita saralangan massivlar birlashtiriladi. Bu eng mashhur saralash algoritmlaridan biri bo'lib, rekursiv algoritmlarni yaratishda ishonchni rivojlantirishning ajoyib usuli hisoblanadi. “Bo’lib tashla va hukmronlik qil” strategiyasi “Bo’lib tashla va hukmronlik qil” strategiyasi yordamida muammoni qismiy jarayonlarga ajratamiz. Har bir kichik topshiriq uchun yechimga ega bo'lsak, pastki vazifalarni yechish uchun pastki vazifalardan olingan natijalarni "birlashtiramiz". Aytaylik, biz A massivni saralashni xohladik. Kichik vazifa bu p indeksidan boshlanib, r indeksida tugagan, A [p..r] bilan belgilangan kichik qismini ajratishdir. “Bo’lib tashlash” Agar q qiymati p va r orasida bo'lsa, biz A [p..r] massivni ikkita A [p..q] va A [q + 1, r] kichik massivlarga bo'lishimiz mumkin. “Hukmronlik qilish”. “Hukmronlik qilish” bosqichida biz ikkala A [p..q] va A [q + 1, r] kichik massivlarni saralashga harakat qilamiz. Agar hali ham boshlang'ich darajaga yetib bormagan bo'lsak, yana ikkala quyi qismni ajratib, ularni saralashga harakat qilamiz. 8 Birlashtirish Birlashtirish bosqichi asosiy pog'onaga yetib borganida va biz A [p..r] massivi uchun ikkita tartiblangan A [p..q] va A [q + 1, r] kichik massivlarni olsak, natijalarni A [p..r] massiviga birlashtiramiz. Bu ikkita tartiblangan A [p..q] va A [q + 1, r] massivlarning birlashmasidir. 9 Birlashtirib saralash algoritmi MergeSort funksiyasi massivni ketma-ket ikki qismga ajratadi, biz 1-darajali ichki massivda MergeSort-ga o'tishga harakat qiladigan bosqichga yetguncha ya’ni p == r bo’lguncha. Shundan so'ng, birlashtirish funktsiyasi ishga tushadi, bu tartiblangan massivlarni butun massiv birlashguncha katta massivlarga birlashtiradi. 1. MergeSort ( A , p , r ) 2. If p > r 3. return ; 4. q = ( p + r )/ 2 ; 5. mergeSort ( A , p , q ) 6. mergeSort ( A , q + 1 , r ) 7. merge ( A , p , q , r ) Butun massivni saralash uchun MergeSort (A, 0, length (A) -1) ga murojaat qilishimiz kerak. Quyidagi rasmda ko'rsatilgandek, birlashtirib saralash algoritmi 1 elementli massivning asosiy holatiga kelgunimizcha massivni rekursiv ravishda ikkiga bo'ladi. So'ngra birlashtirish funktsiyasi saralangan ichki massivlarni tanlaydi va butun qatorni asta-sekin saralash uchun ularni birlashtiradi. Algoritmning eng muhim qismi bu "birlashtirish" bosqichidir. Birlashish bosqichi - ikkita katta ro'yxat (massiv) yaratish uchun ikkita tartiblangan ro'yxatni (massivlarni) birlashtirish bo'yicha oddiy muammoning yechimi. 10 Algoritm uchta ko'rsatgichni saqlaydi, ikkitasi har biri uchun va bittasi tartiblangan qatorning joriy indeksini saqlab qolish uchun. Ikkinchi massivda boshqa elementlar qolmaganligi va ikkala massiv ham ishga tushirilganda saralanganligini bilganimiz uchun qolgan massivlarni to'g'ridan-to'g'ri birinchi massivdan nusxalashimiz mumkin. Birlashtirib saralash algoritmi uchun dastur kodi #include <iostream> using namespace std; // Array[] ikkita ichki massivni birlashtiradi. //Birinchi ichki massiv - Array[l..m] // Ikkinchi ichki massiv Array[m+1..r] void merge(int Array[], int l, int m, int r) { int n1 = m - l + 1; 11 int n2 = r - m; // Vaqtinchalik massivlarni yaratish int L[n1], R[n2]; // Ma'lumotlarni vaqtinchalik L[] va R[] massivlariga nusxalash for (int i = 0; i < n1; i++) L[i] = Array[l + i]; for (int j = 0; j < n2; j++) R[j] = Array[m + 1 + j]; // Vaqtinchalik massivlarni yana arr [l..r] ga birlashtirish. // Birinchi ichki massivning boshlang'ich ko'rsatkichi int i = 0; // Ikkinchi kichik massivning boshlang'ich ko'rsatkichi int j = 0; // Birlashtirilgan ichki massivning dastlabki ko'rsatkichi int k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { Array[k] = L[i]; i++; } else { Array[k] = R[j]; j++; } k++; } // L [] ning qolgan elementlarini nusxalash, //agar mavjud bo'lsa while (i < n1) { Array[k] = L[i]; i++; k++; } // Agar mavjud bo'lsa, R [] ning //qolgan elementlarini nusxalash while (j < n2) { Array[k] = R[j]; j++; k++; } } // l chap indeks uchun, 12 //r esa tartiblangan ichki massivning o'ng indeksidir void mergeSort(int Array[],int l,int r){ if(l>=r){ return;//rekursiv ravishda qaytadi } int m =l+ (r-l)/2; mergeSort(Array,l,m); mergeSort(Array,m+1,r); merge(Array,l,m,r); } // Massivni chop etish funksiyasi void printArrayay(int A[], int size) { for (int i = 0; i < size; i++) cout << A[i] << " "; } int main() { int Array[] = { 12, 11, 13, 5, 6, 7 }; int Array_size = sizeof(Array) / sizeof(Array[0]); cout << "Berilgan massiv \n"; printArrayay(Array, Array_size); mergeSort(Array, 0, Array_size - 1); cout << "\n Tartiblangan massiv \n"; printArrayay(Array, Array_size); return 0; } 13 Merge Sort va uning ishlash prinsipi “Dasturlashning eng asosiy muammosi — bu murakkablik. Murakkablikni hal qilishning faqatgina bitta asosiy yo’li borBo’lib tashla va hukmronlik qil” — Bjarne Stroustrup Merge Sort bu saralanmagan arrayni taqqoslashga asoslangan holda saralovchi algoritm bo’lib, uning ishlash prinsipida to’liq bo’lib tashla va hukmronlik qil g’oyasini uchratish mumkin. Demak, merge sort asosiy ikkita qismdan iborat: 1. Berilgan arrayni rekursiv holda teng ikkita qismlarga bo’lib chiqish. Bu qadam, qism arraylar uzunligi 1 ga (yoki undan kichik) teng bo’lib qolguncha davom etadi. 2. Hosil bo’lgan arraylarni qaytib birlashtirib chiqish va bir vaqtni o’zida hosil bo’luvchi array saralangan bo’lishini ta’minlash. Merge sort qanday ishlashini vizual tasavvur qilish uchun quyidagi rasmga e’tiboringizni qaratmoqchiman. 14 Unda amallar tartibi ham ko’rsatib qo’yilgan Ko’rib turganingizdek algoritm ishlash prinsipini tushunish uchun unchalik ham murakkab emas. Va yana e’tibor bergan bo’lsangiz, birinchi bo’linishdan keyingi arrayning chap va o’ng qismlarida asosiy array bilan bir xil amal ketmoqda, ya’ni bizning masalamizning qism masalasi ham bosh masala bilan bir xilda ishlaydi. Endi esa algoritmni implementatsiya qilish uchun qadamma-qadam nima qilish kerakligiga o’tamiz Merge sort algoritmi qadamlari 1. Merge Sort funksiyasiga array va uning boshlang’ich ( left ) va oxirgi nuqtalari ( right ) beriladi. 15 2. Arraynining o’rtasi hisoblanadi: mid = (left + right)/2. Bu narsa uni teng ikkiga bo’lish uchun kerak bo’ladi. 3. Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi. 4. 2- va 3-qismlarda hosil bo’lgan arraylar birlashtirib chiqiladi. (Array mavzusidagi ikkita arrayni birlashtirish masalasini ko’rib chiqing) Algoritm ishlash tezligi O(nlogn) bo’lib tezligi O(n²) bo’lgan oddiy Bubble, Insertion, Selection Sortlardan ancha tez ishlaydi. O’zi umuman olganda, taqqoslash asosida ishlaydigan algortmlarning eng tez ishlash holati O(nlogn) bo’lishi isbotlangan . Merge sort turg’un saralash hisoblanadi, ya’ni saralamagan arrayda bir nechta bir xil elementlar kelgan bo’lsa, ularning tartibi saralangan massivda ham o’zgarib ketib qolmaydi. Algoritm ishlashi uchun xotiradan qo’shimcha O(n) joy talab qiladi. Bu Merge sort haqida bilishingiz kerak bo’lgan narsalar edi. Keyingi darsimizda algoritm implementatiyasiga to’xtalib o’tamiz. 16 Birlashtirib saralash algortimini baholash Birlashtirib bilan ichki saralash algoritmi (Merge sort) mashhur saralash algoritmlaridan biridir. “Bo'lib tashlash va hukmronlik qilish” usulini qo'llaydi. Algoritmning asosiy g'oyasi ikkita tartiblangan ketma-ketlikni birlashtirishdir. Xuddi shu prinsip tashqi tartiblash uchun asosdir. A 1 , A 2 , ..., A n va B 1 , B 2 , ..., B n elementlari bilan o'sish tartibida saralangan ikkita massiv bo'lsin va biz xohlagan bo'sh C 1 , C 2 , ..., C 2 n massiv mavjud. O'sish tartibida A va B massivlarining qiymatlari bilan bu bo’sh massivni to’ldirish lozim. Birlashtirish uchun quyidagi amallar bajariladi: A1 va B1 taqqoslanadi va qiymatlarning pastki qismi C1 ga yoziladi. Masalan, bu A1 bo’lsin. Keyin A2 B1 bilan taqqoslanadi va qiymatlarning eng kichigi C2 ga kiritiladi. Masalan, bu B1 qiymati bo’lsin. Keyinchalik, keyingi bosqichda A2 va B2 qiymatlari taqqoslanadi va shunga o'xshash ravishda, massivlardan birining chegaralariga yetib borgunimizcha davom etadi. Qolgan boshqa massiv C massivining oxiridan qo'shiladi. Birlashtirib saralash odatda rekursiv ravishda amalga oshiriladi. Rekursiyaning har bir qadamida massiv ikkita ichki massivlarga bo'linadi, ularning har biri ham ikkita ichki massivga bo'linadi va hokazo. Tartiblangan ketma-ketlikning uzunligi 1 ga teng bo'lganda rekursiya eng past chegaraga yetadi, bu holda barcha ishlar allaqachon bajarilgan, chunki bitta elementning har qanday bunday ketma-ketligini saralangan deb hisoblash mumkin. Quyida ushbu algoritmni amalga oshiradigan MergeSort funktsiyasi keltirilgan. Saralangan ketma-ketliklarning birlashishi yordamchi Merge(A, p, q, r) funksiyasi yordamida amalga oshiriladi, bu yerda massiv, va p, q va r massiv elementlarini raqamlash indekslari bo'lib, p-q < r. Ushbu funksiya A [p ... q] va A [q +1 ... r] kichik massivlarning elementlari tartiblangan deb taxmin qiladi. U ushbu ikkita kichik masshtabni bitta tartiblangan holda birlashtiradi, uning elementlari A massivning joriy elementlarini almashtiradi [p ... r]. Massivning dastlabki ko’rinishi 6 19 3 8 92 15 1 9 Saralash qadamlari 6 19 3 8 92 15 1 9 6 19 3 8 92 15 1 9 6 19 3 8 92 15 1 9 6 19 3 8 15 92 1 9 3 6 8 19 1 9 15 92 17 Saralash funksiyasi kodi void MergeSort (int* x, int first, int last) { if (first < last) { int split = (first + last) / 2; MergeSort (x, first, split); MergeSort (x, split + 1, last); Merge (x, first, split, last); } } Massivning uzunligi 1dan katta bo'lsa, uning o'rtasi hisoblanadi (split o'zgaruvchi), so'ngra chap va o'ng tomonlar uchun ikkita rekursiv chaqiruv boshlanadi, ular funksiya ushbu misoliga qaytganda, ular bog’lanadigan Merge funksiyasi: void Merge (int* x, int first, int split, int last) { int pos1 = first, pos2 = split + 1, pos3 = 0; int* temp = new int [last — first + 1]; while (pos1 <= split && pos2 <= last) { if (x [pos1] < x [pos2]) temp [pos3++] = x [pos1++]; else temp [pos3++] = x [pos2++]; } while (pos2 <= last) temp [pos3++] = x [pos2++]; while (pos1 <= split) temp [pos3++] = x [pos1++]; for (int i = 0; i < last — first + 1; ++i) x [first + i] = temp [i]; } Algoritmning murakkabligini taxmin qilaylik. Har qanday rekursiv funktsiya chaqiruvi daraxtga o'xshaydi (Izoh: “Daraxtlar” haqida keyingi ma’ruzalarda to’xtalib o’tiladi). Bunday daraxtni rekursion daraxt deb ham atashadi. Daraxtning har bir darajasi bir yoki bir nechta funktsiya chaqiruvlarini aks ettiradi. Shoxlari bo'lmagan daraxt tugunlari rekursiyani tugatadigan funktsiya chaqiruvlarini anglatadi. Birlashtirish tartibida daraxtning balandligi log 2 n ga teng, chunki har bir qadamda boshlang’ich massiv n/2 uzunlikdagi ikkita ichki massivga bo'linadi. Ajratishdan so'ng, birlashtirish operatsiyasi amalga oshiriladi. Birlashtirish jarayoni n taqqoslashni, navbati bilan log n marta, ya'ni daraxtning har bir darajasi uchun 1 marta takrorlashni talab qiladi. Keyin algortim asimptotikasi 18 saralash funksiyasini birlashtirish Yuqoridagi kodni massivlarni iloji boricha uzoqroqqa bo'ladigan rekursiv funksiya sifatida formatlaymiz, parametrlari birinchi chaqiruvda butun massivga, ikkinchi va uchinchi chaqiruvlarda uning yarmiga va hokazo. private void SortUnsorted ( int [] a, int lo, int hi) { if (hi <= lo) return ; int mid = lo + (hi - lo) / 2 ; SortUnsorted(a, lo, mid); SortUnsorted(a, mid + 1 , hi); int [] buf = Arrays.copyOf(a, a.length); for ( int k = lo; k <= hi; k++) buf[k] = a[k]; int i = lo, j = mid + 1 ; for ( int k = lo; k <= hi; k++) { if (i > mid) { a[k] = buf[j]; j++; } else if (j > hi) { a[k] = buf[i]; i++; } else if (buf[j] < buf[i]) { a[k] = buf[j]; j++; } else { a[k] = buf[i]; i++; } } 19 } Oddiy boshlang'ich o'ta murakkab compliyator. Ikki tartiblangan massivni birlashtirish eng oddiy kod yordamida amalga oshiriladi (variant eng samarali emas, lekin u siznikidan tezroq ishlaydi): while (i < a1.length && j < a2.length) { a3[k++] = a1[i] < a2[j] ? a1[i++] : a2[j++]; } if (i< a1.length) { arraycopy(a1, i, a3, k, a1.length - i); } else if (j< a2.length) { arraycopy(a2, j, a3, k, a2.length - j); } Minimal o'lchamga bo'linish faqat elementlarga ketma-ket kirish imkoniyati bilan ro'yxatlarni saralash uchun mantiqiydir. Boshqa tomondan, massivlar elementlarga to'g'ridan-to'g'ri kirish bilan samarali tartiblash algoritmini qo'llash uchun blok hajmi etarlicha kichik bo'lgunga qadar aniq bo'linishi kerak. Xotiraga to'liq mos keladigan massivlar uchun birlashma tartiblashdan foydalanish, xususan, ushbu algoritmni to'liq noto'g'ri tushunish va umuman algoritmlar nazariyasining minimal asoslarini ham to'liq bilmaslikning namoyishidir. 20 Birlashtirish saralash - ro'yxatlarni (yoki elementlariga faqat ketma-ket kirish mumkin bo'lgan boshqa ma'lumotlar tuzilmalarini, masalan, oqimlarni) ma'lum bir tartibda tartibga soluvchi tartiblash algoritmi. Ushbu saralash "bo'l va zabt et" tamoyilidan foydalanishning yaxshi namunasidir. Birinchidan, vazifa bir nechta kichik kichik vazifalarga bo'linadi. Keyinchalik bu vazifalar rekursiv qo'ng'iroq bilan yoki ularning hajmi etarlicha kichik bo'lsa, to'g'ridan-to'g'ri hal qilinadi. Nihoyat, ularning yechimlari birlashtirilib, dastlabki masala yechimi olinadi. Birlashtirib saralash algoritmi[tahrirlash | kodni tahrirlash] Tasodifiy nuqtalarni saralash misolida algoritmning harakati. Saralash muammosini hal qilish uchun ushbu uchta qadam quyidagicha ko'rinadi: 1. Saralangan massiv taxminan bir xil o'lchamdagi ikki qismga bo'linadi; 2. Olingan qismlarning har biri alohida, masalan, bir xil algoritm bo'yicha tartiblanadi; 3. Ikki yarim o'lchamdagi tartiblangan massiv bittaga birlashtiriladi. 1.1. - 2.1. Vazifani kichikroqlarga rekursiv bo'lish massivning o'lchami bittaga yetguncha sodir bo'ladi (uzunligi 1 bo'lgan har qanday massivni tartiblangan deb hisoblash mumkin). Ikki tartiblangan massivni birlashtirishning asosiy g'oyasini quyidagi misol bilan tushuntirish mumkin. Faraz qilaylik, bizda ortib boruvchi tartibda tartiblangan ikkita pastki qator bor. Keyin: 3.2. Ikki pastki qatorni uchinchi massivga birlashtirish. Har bir qadamda biz pastki massivlarning dastlabki ikkita elementidan kichigini olamiz va uni hosil bo'lgan massivga yozamiz. Olingan massiv va element olingan pastki massivning elementlari sonining hisoblagichlari 1 ga oshiriladi. 3.3. Qolganlarning "ilovasi". massivning qolgan barcha elementlarini qo'shamiz. C++ da saralash: /** * Rekursiv birlashma tartiblash yordamida massivni saralaydi * yuqoriga - saralanadigan massivga ko'rsatgich 21 * pastga - bufer sifatida ishlatiladigan kamida "yuqoriga" bilan bir xil o'lchamdagi massivga ko'rsatgich * chap - massivning chap chegarasi, massivni boshidan saralash uchun 0 dan o'ting * o'ng - massivning o'ng chegarasi, massiv uzunligini o'tkazing - 1 massivni oxirgi elementga saralash uchun * qaytaradi: tartiblangan massivga ko'rsatgich. Ushbu amalga oshirishning tabiati tufayli * massivning tartiblangan versiyasi "yuqoriga" yoki tugashi mumkin **/ Qolganini C++ ga tilda “biriktirmasdan” takomillashtirilgan birlashma algoritmi uchun psevdokod : L = *In1; R = *In2; if( L <= R ) { *t++ = L; In1++; } if( L >= R ) { *t++ = R; In2++; } If(L >= R) chekini olib tashlash orqali tekshirishlar sonini ikki baravar kamaytirish mumkin. Bunday holda, agar L va R teng bo'lsa, L birinchi iteratsiyada Out ga, R esa ikkinchisiga yoziladi. Agar asl massivda qolgan elementlardan ustun bo'lgan takroriy elementlar bo'lmasa, ushbu parametr samarali ishlaydi. Qolganini C++-ga o'xshash tilda "biriktirmasdan" qisqartirilgan birlashma algoritmi uchun psevdokod: L = *In1; R = *In2; if( L <= R ) { *t++ = L; In1++; } else { *t++ = R; In2++; } 22 L va R o'zgaruvchilarga ikkita o'tkazish dasturdagi ba'zi yozuvlarni soddalashtirish, bu ta'lim vositalari uchun foydali bo'lishi mumkin, ammo haqiqiy dasturlarda ularni olib tashlashumkin, bu esa dastur kodini yuklash. , siz tezroq dastur kodini yanada chiqadigan uchlik operatordan aniqlash mumkin . Qolganini C++-ga o'xshash tilda "biriktirmasdan" yanada kengaytirilgan birlashma algoritmi uchun psevdokod: *t++ = *In1 <= *In2 ? In1++: In2++; Algoritmning ishlash vaqti O(n * log n) bo'lib, yomon holatlarda buzilish bo'lmasa, bu tezkor tartiblashning og'riqli nuqtasidir (shuningdek, O(n * log n) tartibli algoritm), lekin faqat o'rtacha holat uchun ). Xotira iste'moli tez saralashdan ko'ra ko'proq, xotirani taqsimlash ancha qulayroq - xotiraning bir hududini boshidanoq ajratish mumkin, keyin esa ajratmaslik mumkin. Ommabop dastur tartiblangan massivga teng va rekursiyalarga ega bo'lmagan bir martalik ajratilgan vaqtinchalik xotira buferini talab qiladi. Amalga oshirish bosqichlari: 1. InputArray = tartiblanuvchi massiv, OutputArray = vaqtinchalik bufer; 2. InputArray[N * MIN_CHUNK_SIZE..(N + 1) * MIN_CHUNK_SIZE] kirish massivining har bir segmentida ba'zi yordamchi tartiblash algoritmi bajariladi, masalan, Shell sort yoki tez saralash; 3. ChunkSize = MIN_CHUNK_SIZE o‘rnating; 4. Ikki segment InputArray[N * ChunkSize..(N + 1) * ChunkSize] va InputArray[(N + 1) * ChunkSize..(N + 2) * ChunkSize] navbat bilan chapga va o‘ngga qadam qo‘yish orqali birlashtiriladi (yuqoriga qarang). ), natija OutputArray[N * ChunkSize..(N + 2) * ChunkSize] ga joylashtiriladi va massiv oxiriga yetguncha hamma N uchun shunday davom etadi; 5. ChunkSize ikki barobar oshiriladi; 6. agar ChunkSize massiv hajmi >= ga aylangan bo‘lsa, u holda natija OutputArray-da bo‘ladi, u (quyida tasvirlangan almashtirishlar tufayli) tartiblanuvchi massiv yoki vaqtinchalik bufer bo‘ladi, ikkinchi holatda u to‘liq tartiblanuvchiga ko‘chiriladi. massiv; 7. Aks holda, InputArray va OutputArray ko'rsatkichlarni almashtirish orqali almashtiriladi va hamma narsa 4-banddan boshlab takrorlanadi. Ushbu dastur, shuningdek, saralanadigan massivni va vaqtinchalik buferni disk fayllariga joylashtirishni qo'llab-quvvatlaydi, bu esa uni katta hajmdagi ma'lumotlarni saralash uchun mos qiladi. ORDER BY ni MySQL da mos indeks bo'lmaganda amalga oshirish aynan shunday ishlaydi (manba: MySQL manba kodidagi filesort.cc). Psevdokodda oddiy ikki tomonlama birlashma algoritmini amalga oshirishga misol: function mergesort(m): 23 Birlashtirish tartiblash algoritmi algoritm, birlashtirish tartiblash, Birlashtirish saralash algoritmi, saralash Birlashtirish tartibi - bu kompyuter dasturlashda bo'lish va zabt etish algoritmining bir turi. Bu eng mashhur saralash algoritmlaridan biri va rekursiv algoritmlarni yaratishda ishonchni mustahkamlashning ajoyib usuli. Tarkibi Birlashtirish tartiblash algoritmi 1.. Birlashtirish saralash birlashtirish qadami 2.. Birlashtirish algoritmi uchun kod yozish 3. Funktsiyani bosqichma-bosqich birlashtirish 1-bosqich . Saralash uchun pastki qatorlarning dublikat nusxalarini yarating 2-bosqich : pastki massivlar va asosiy massivning joriy indeksini saqlash 3-bosqich : L yoki M ning oxiriga yetgunimizcha, L va M elementlardan kattasi tanlanadi va A nuqtada to‘g‘ri joyga joylashtiriladi [p..r] 4-bosqich : L yoki M dagi elementlar tugagach, qolgan elementlar A [p..r] ga joylashtirilishi kerak. Agar q p va r orasidagi oraliq nuqta bo'lsa, u holda biz A [p..r] pastki massivni ikkita massivga bo'lishimiz mumkin. A [p..q] va A [q + 1, r]. 24 Qoida Fath bosqichida biz ikkala pastki qatorlarni A[p..q] va A[q + 1, r] saralashga harakat qilamiz. Agar biz hali ham asosiy holatga etib bormagan bo'lsak, biz ikkala pastki qatorni yana ajratib, ularni saralaymiz. Qachonki zabt etuvchi qadam asosiy bosqichga yetib, A[p..r] massiv uchun ikkita tartiblangan pastki massivlar A[p..q] va A[q + 1, r] ni olamiz, natijalarni birlashtirib, tartiblangan A massivini yaratamiz. A[p..q] va A[q + 1, r] ikkita tartiblangan pastki massivlarning [p. .r] Algorit m birlasht irish t art ibi MergeSort funktsiyasi massivni 1 o'lchamdagi kichik massivda MergeSort qilishga harakat qiladigan bosqichga etgunimizcha qayta-qayta ikkiga bo'ladi, ya'ni. p == r. Shundan so'ng, butun massiv birlashtirilgunga qadar tartiblangan massivlarni kattaroq massivlarga birlashtirgan birlashtirish funksiyasi ishga tushadi. MergeSort ( A , p , r ) 1. If p > r 2. return ; 3. q = ( p + r )/ 2 ; 4. mergeSort ( A , p , q ) 5. mergeSort ( A , q + 1 , r ) 6. merge ( A , p , q , r ) Butun massivni saralash uchun MergeSort(A, 0, length(A)-1) ni chaqirishimiz kerak. Quyidagi rasmda ko'rsatilganidek, birlashma tartiblash algoritmi 1 elementli massivning asosiy registriga yetguncha massivni rekursiv ravishda ikkiga bo'ladi. Keyin birlashtirish funksiyasi tartiblangan pastki qatorlarni tanlaydi va butun massivni bosqichma-bosqich saralash uchun ularni birlashtiradi. Har bir rekursiv algoritm asosiy holatga va asosiy holatlar natijalarini birlashtirish qobiliyatiga bog'liq. birlashtirish tartibi bundan mustasno emas. Algoritmning eng muhim qismi "birlashtirish" bosqichidir. Birlashtirish bosqichi bitta katta tartiblangan ro'yxatni (massiv) yaratish uchun ikkita tartiblangan ro'yxatni (massivlarni) birlashtirishning oddiy muammosini hal qilishdir. Algoritm ikkita massivning har biri uchun va oxirgi tartiblangan massivning joriy indeksini saqlash uchun bittadan uchta ko'rsatgichni saqlaydi. Ikkinchi massivda boshqa elementlar qolmagani va biz ikkala massiv ishga tushganda tartiblanganligini bilamiz, qolgan elementlarni birinchi massivdan to‘g‘ridan-to‘g‘ri nusxalashimiz mumkin. Birlasht irish algorit mi uchun k odni y ozish 25 Yuqorida tavsiflangan birlashtirish bosqichi va biz birlashma tartiblash uchun foydalanadigan qadam o'rtasidagi sezilarli farq shundaki, birlashtirish funktsiyasi faqat ketma-ket pastki qatorlarda amalga oshiriladi. Shuning uchun bizga faqat massiv, birinchi pozitsiya, birinchi pastki qatorning oxirgi indeksi (ikkinchi pastki qatorning birinchi indeksini hisoblashimiz mumkin) va ikkinchi pastki qatorning oxirgi indeksi kerak. Bizning vazifamiz A[p..q] va A[q + 1..r] ikkita pastki massivlarni birlashtirib, tartiblangan A[p..r] massivini yaratishdir. Shunday qilib, A, p, q va r funktsiyasi uchun kirish ma'lumotlari Birlashtirish funktsiyasi quyidagicha ishlaydi: 1. 1. L ← A [p..q] va M ← A [q + 1..r] kichik massivlarning nusxalarini yaratiladi 2. i, j va k uchta ko‘rsatkichni yaratiladi 3. i 1 dan boshlab joriy L indeksini saqlaydi 4. j 1 dan boshlab M ning joriy indeksini saqlaydi 5. k p dan boshlab A [p..q] ning joriy indeksini saqlaydi 6. L yoki M ning oxiriga yetgunimizcha, L va M dan kattaroq elementlarni tanlanadiva ularni A[p..q] dagi to‘g‘ri joyga qo‘ying.L yoki M dagi elementlar tugagach, qolgan elementlarni olib, A [p..q] ga qo‘ying. 7. Kodda u shunday ko'rinadi: Dastur kodi ko’rinishi: 1. void merge ( int A [], int p , int q , int r ) 2. { 3. int n1 = q - p + 1 ; 4. int n2 = r - q ; 5. 6. int L [ n1 ], M [ n2 ]; 7. 8. for ( i = 0 ; i < n1 ; i ++) 9. L [ i ] = A [ p + i ]; 10. for ( j = 0 ; j < n2 ; j ++) 11. M [ j ] = A [ q + 1 + j ]; 12. 13. /* Ichki massivlar va asosiy massivning joriy indeksini saqlang */ 14. int i , j , k ; 15. i = 0 ; 16. j = 0 ; 17. k = p ; 18. 19. 20. /* L yoki M ning oxiriga yetgunimizcha, L va M elementlardan kattarog‘ini tanlang va ularni A [p..r] nuqtasida to‘g‘ri joyga qo‘ying*/ 21. while ( i < n1 && j < n2 ) 22. { 23. if ( L [ i ] <= M [ j ]) 24. { 25. arr [ k ] = L [ i ]; 26. i ++; 26 27. } 28. else 29. { 30. arr [ k ] = M [ j ]; 31. j ++; 32. } 33. k ++; 34. } 35. 36. /* L yoki M dagi elementlar tugagach, qolgan elementlarni olib, A [p..r] ga qo‘ying*/ 37. while ( i < n1 ) 38. { 39. A [ k ] = L [ i ]; 40. i ++; 41. k ++; 42. } 43. 44. while ( j < n2 ) 45. { 46. A [ k ] = M [ j ]; 47. j ++; 48. k ++; 49. } 50. } Funktsiyani bosqichma-bosqich birlashtirish 1-qadam: Saralash uchun past k i qat orlarning dublik at nusxalarini y arat ing 1. n1 = 4 - 1 + 1 = 4 ; 2. n2 = 6 - 4 = 2 ; 3. 4. int L [ 4 ], M [ 2 ]; 5. 6. for ( i = 0 ; i < 4 ; i ++) 7. L [ i ] = A [ p + i ]; 8. /* L[0,1,2,3] = A[1,2,3,4] = [1,5,10,12] */ 9. 10. for ( j = 0 ; j < 2 ; j ++) 11. M [ j ] = A [ q + 1 + j ]; 12. /* M[0,1,2,3] = A[5,6] = [6,9] 2-qadam: Kichik massiv lar v a asosiy massiv ning joriy indek sini saqlash 1. int i , j , k ; 2. i = 0 ; 3. j = 0 ; 4.k = p ; 27 3-qadam: L y ok i M ning oxiriga y et gunimizcha, L v a M element laridan k at t asi t anlanadi v a A nuqt ada t o‘g‘ri joy ga joy lasht iriladi [p..r] 1. while ( i < n1 && j < n2 ) { 2. if ( L [ i ] <= M [ j ]) { 3. A [ k ] = L [ i ]; i ++; 4. } 5. else { 6. A [ k ] = M [ j ]; 7. j ++; 8. } 9. k ++; 10. } 4-qadam: L y ok i M dagi element lar t ugagach, qolgan element lar A [p..r] ga joy lasht irilishi k erak . 1. /* Biz oldingi sikldan chiqdik, chunki j <n2 ishlamayapti */ 2. while ( i < n1 ) 3. { 4. A [ k ] = L [ i ]; 5. i ++; 6. k ++; 7. } 1. 1. /* Oldingi sikldan chiqdik, chunki i <n1 ishlamayapti */ 2. while ( j < n2 ) 3. { 4. A [ k ] = M [ j ]; 5. j ++; 6. k ++; 7. } 8. } Biz yuqorida keltirilgan qadamlardan funksiyani bosqichma - bosqich birlashtirishni ko ’ rib chiqishimiz mumkin : avvalo saralash pastki qatorlarining dublikat nusxalarini yaratib oldik kkeyingqadamimizda kichik va joriy massiv indeksini aniqlab oldik . Birinchi qadamda for sikl operatori va massivdan foydalangan bo’lsak. Keyingi qadamda bir nuqta tanlanib olinib boshiga tenglashtiriladi ya’ni [p..r] oraliqda bo’lishi mumkin biz bunda while oparatoriga masofa belgilab olamiz i va j lar orqali va yana shart oparatoriga murojat qilamiz va so’nggi qadamda elementlardan birortasi qolmasa [p..r]ga joylashtirishimiz mumkin. 28 Xulosa : Gapimizni texnika asrida yashayotganimizdan boshlasak texnika-texnalogiyalar hayotimizga izchillik va shiddat bilan kirib keldiva hayotning ma’lum bir qismiga aylanib ulgurdi. Endilikda har bir soha vakillari ishlarini osonlashtirish va sifatli bo’lishi uchun o’z yumushlarini texnika va texnalogiyalar bilan baham ko’rishyapti,bu normal holat chunki yetarli sabablar mavjud. Bu texnika texnalogiyalar esa ma’lum bir algoritmlardan tashkil topgan bo’ladi, algoritm tushunchasiga yuqorida to’xtalib o’tgan edik. Albatta bu texnalogiyalar ma’lum bir tartib qoidalarga bo’ysungan holda ishlaydi va biz buni “algoritm” deb ataymiz. Demak biz texnalogiyalarga dasturchi nuqtai nazaridan qaraydigan bo’lsak algoritmlarni bilishimiz, tushinishimiz va foydalanaolishimiz judayam muhum. Algoritmlash ham o’z vazifasiga ko’ra turlanadi. Yuqoridagi ma’lumotlardan kelib chiqib aytadigan bo’lsak algoritmlarni ma’lum bir turlarlarga bo’linishini bilib oldingiz. Ularni odatda asosiy 3 ta guruhga bo’lib o’rganiladi va tavsiflanadi. Demak, bular: chiziqli, tarmoqlanuvchi va takrorlanuvchi algoritmalardir. Yuqoridagi dastur kodlarini taxlil qiladigan bo’lsak bu dasturlarda uchala guruh algoritmlarni ifodalovchi operatorlar ishtirok etgan. Shunday ekan bu tushuncha murakkab ko’rinishdagi algortim hisoblanadi va bunda uchala guruhga tegishli algoritm operatorlaridan foydalaniladi. Algoritmlarni muhim jihatlaridan ular qat’iy btartib asosida ishlaydi va sizning uslubingizga tayanadi,xo’p bizga birlashtirish saralash algoritmi nima uchun kerak? Albatta, odatda bir masalaga bir necha yechim bo’ladi. Shundan kelib chiqib dasturlashda ham bir masala uchun bir qancha yechimlar taklif etish mumkin. Ammo, bizga eng samarador yechim bo’lgani hamma uchun yaxshi hisoblanadi. Foydalanauvchi uchun ham, texnik vositalar uchun ham vatqdan yutish asosiy urg’u beriladigan omildir. Xotira hozirgi vaqtda dolzarb bo’lmasada ham xotira ham vaqt tejalishiga erishish eng maqbul yechim hisoblanadi. Aynan shu muammolarni(vaqt tejalishi) samarali hal etish uchun loyhalashtiriladi. Va saralash algorimlari orasida shu jihatlari bilan ajralib turadi. Masalan bir xil yo’nalishda algoritmlar sizda mavjud bo’lsa siz asosan xotiradan va vaqtdan yutadiganini tanlaysiz. 29 Demak, so’ngi so’z o’rnida shularni aytishim mumkinki, birlashtirish algoritmini yaxshilab o’rganishimiz kerak o’zlashtirishimiz, mustaqil ravishda algoritmlar tuzaolish ko’nikmasini o’zimizda shakillantirishimiz va buni amalyotda qo’llay olishimiz bizni maqsadga yetishimiza judayam asqotadi deb o’ylayman. Bu kurs ishimdan kimdir manfaat ko’rsa man faqat bundan xursand bo‘laman va mehnatim ham zoya ketmagan bo’ladi. Hech qachon bilim olishdan to’xtamang . Foydalanilgan adabiyotlar: 1. M.O‘. ASHUROV, SH.A.SATTAROVA, SH.U.USMONQULOV, “ALGORITMLAR” , «Fan va texnologiya» nashriyoti, 2018. 2. H.To’rayev,“Kombinatorika va graflar nazariyasi”, “Ilm ziyo”, 2009 , 3. Akbaraliyev B.B., Yusupova Z.Dj. , “MA LUMOTLAR TUZILMASI VA ‟ ALGORITMLAR”, Toshkent 2013 4. Toirov Sh.A., Raximov R.T., Karimov M.M ,” “ALGORITMGA KIRISH” fanidan laboratoriya ishlarini bajarish bo’yicha USLUBIY KO’RSATMA”, Samarqand 2015, 5. Xayitmatov O’.T., Inogomjonov E.E., Sharipov B.A., Ro’zmetova N., Rahimboboeva D,” MA'LUMOTLAR TUZILMASI VA ALGORITMLARI”, Toshkent – 2011 6. Л.И.Домнин, “ЭЛИМЕНТЫ ТЕОРИИ ГРАФОВ” , “ Пенза Издательство Пензенского государственного университета“ ,2007 7. Никлаус Вирт ,”Алгоритмы и структуры данных Новая версия для Оберона + CD “, Москва, 2010. Foydalanilgan internet saytlar: 1) https://kursovik.com/programming/320372.html 2) http://aliev.me/runestone/Graphs/PrimsSpanningTreeAlgorithm.html 30 3) http://www.hpcc.unn.ru/?dir=836 4) https://brestprog.by/topics/mst/ 5) wikipedia 6) https://evileg.com/ru/post/524/ 7) http://www.mkurnosov.net/ 31

“ MA’LUMOTLARNI SARALASH. SARALASHNI BIRLASHTIRISH(SILYANIE)USULI ” Reja: • .Kirish.Algoritm haqida tushuncha • . Birlashtirib saralash • Amaliy qism 1. Birlashtirib saralash (Merge sort) 2.Dastur kodi 3.Birlashtirish algoritmi qay tarzda ishlashi haqida • ..Xulosa • . Foydalanilgan adabiyotlar

“Algoritm — bu dasturchilar o’zlari nima qilayotganliklarini boshqalar bilmasligini xohlagan paytida ishlatadigan so’zlari” — Unanonymous. Kirish.Algoritm haqida tushuncha Algoritm so’zi al-Xorazmiyning arifmetikaga bag’ishlangan asarining dastlabki betidagi “Dixit Algoritmi” (“dediki al-Xorazmiy” ning lotincha ifodasi) degan jumlalardan kelib chiqqan. Shundan so’ng al-Xorazmiyning sanoq sistemasini takomillashtirishga qo’shgan hissasi, uning asarlari algoritm tushunchasining kiritilishiga sabab bo’lganligi ta’kidlab o’tiladi. Algoritm nima degan savolga, u asosiy tushuncha sifatida qabul qilinganligidan, uning faqat tavsifi beriladi, ya’ni biror maqsadga erishishga yoki qandaydir masalani yechishga qaratilgan ko’rsatmalarning (buyruqlarning) aniq, tushunarli, chekli hamda to’liq tizimi tushuniladi. Algoritm tushunchasi aniq shaklda 20-asr boshlarida D. Gilbert, K. Gyodel, S. Klin, A. Chyorch, E. Post, A. Tyuring, N. Viner, A. A. Markov singari olimlarning asarlari tufayli shakllandi. Eng qadimiy raqamli algoritmlardan biri Yevklid algoritmi (miloddan avvalgi III asr) deb hisoblanadi - ikki sonning eng katta umumiy bo'luvchisini topish. Algoritmlarning zamonaviy nazariyasi nemis matematikasi Kurt Gyodel (1931) asarlari bilan boshlandi, ular o'zlarining rasmiy, izchil aksiomalar tizimi doirasida yechib bo'lmaydigan muammolar mavjudligini ko'rsatdi. Algoritmlar nazariyasi bo'yicha birinchi fundamental ishlar 1936-yilda paydo bo'lgan. Tyuring mashinasi, Post va Chyorch tomonidan λ-hisobi taklif etiladi. Ushbu mashinalar algoritmning formallashtirilgan rasmiylashtirilishi edi. Algoritmni bajarayotgan kishi – ijrochi, asosiy algoritmni aniqlashtiruvchi algoritm – yordamchi algoritm ekanligini ham ta’kidlab o’tish joiz. Umuman, algoritmning 5 ta qanday maqsadga mo’ljallanganligidan qat’i nazar uni muvaffaqiyat bilan bajarish mumkinligini aytib o’tish lozimdir. Algoritmning bir nechta ta’rifi mavjud. Ulardan ayrimlarini keltirib o’tamiz: – “Algoritm - bu belgilaydigan cheklangan qoidalar to'plami, muayyan vazifalar to'plamini hal qilish bo'yicha amallar ketma -ketligi va beshta muhim xossaga ega: aniqlik, tushunarlilik, kiritish, chiqarish, samaradorlik”. (D. E. Knut). – “Algoritm - bu qat'iy belgilangan qoidalar asosida bajariladigan har qanday hisoblash tizimidir, bu ma'lum bir qator bosqichlardan so'ng, aniq qo'yilgan masalani hal qilishga olib keladi" (A. Kolmogorov) – “Algoritm - bu har xil boshlang'ich ma'lumotlardan kerakli natijaga o'tadigan 2

hisoblash jarayonini belgilaydigan aniq ketma-ketlik" (A. Markov). 1950-yillarda algoritm nazariyasiga o'z hissalarini Kolmogorov va Markov asarlari qo'shgan. 1960-1970 yillarda algoritm nazariyasida tadqiqot yo'nalishlari shakllandi: 1) Algoritmlarning klassik nazariyasi (rasmiy tillar nuqtai nazaridan masalalarni shakllantirish, yechuvchanlik muammosi tushunchasi, murakkablik sinflarini kiritish, P = NP (?) masalasini shakllantirish, NP-ning to'liq masalalarini sinfi va uni o'rganish); 2) Algoritmlarni asimptotik tahlil qilish nazariyasi (algoritmning murakkabligi tushunchasi, algoritmlarni baholash kriteriyal ari, asimptotik baholarni olish usullari, xususan, rekursiv algoritmlar uchun, murakkablikni yoki bajarilish vaqtini asimptotik tahlil qilish); 3) Hisoblash algoritmlarini amaliy tahlil qilish nazariyasi (funksiyalarning intervalli tahlili, algoritmlar sifatining amaliy mezonlari, ratsional algoritmlarni tanlash metodikasi). Algoritmning aniq yoki bilvosita turli xil ta'riflari bir qator talablarni keltirib chiqaradi: - algoritmda cheklangan miqdordagi elementar bajarilishi mumkin bo'lgan ketma ketlik bo'lishi kerak, ya'ni yozuvning aniqligi talabi bajarilishi kerak; - algoritm masalani yechishda cheklangan sonli bosqichlarni bajarishi kerak, ya'ni harakatlarning aniqligi talabi bajarilishi kerak; - barcha qabul qilingan kirish ma'lumotlari uchun algoritm bir xil bo'lishi kerak, ya'ni universallik talabiga javob berish; - algoritm qo'yilgan vazifaga nisbatan to'g'ri yechimga olib kelishi kerak, ya'ni to'g'rilik talabi bajarilishi kerak. Algoritm xossalari Algoritmning asosiy xossalari haqida quyidagilarni ta’kidlash mumkin: 1-xossa . Diskretlilik, ya’ni algoritmni chekli sondagi oddiy ko’rsatmalar ketma ketligi shaklida ifodalash mumkin. 2-xossa . Tushunarlilik, ya’ni ijrochiga tavsiya etilayotgan ko’rsatmalar uning uchun tushunarli bo’lishi shart, aks holda ijrochi oddiy amalni ham bajara olmay qolishi mumkin. Har bir ijrochining bajara olishi mumkin bo’lgan ko’rsatmalar tizimi mavjud. 3-xossa . Aniqlik, ya’ni ijrochiga berilayotgan ko’rsatmalar aniq mazmunda bo’lishi lozim hamda faqat algoritmda ko’rsatilgan tartibda bajarilishi shart. 4-xossa . Ommaviylik, ya’ni har bir algoritm mazmuniga ko’ra bir turdagi masalalarning barchasi uchun yaroqli bo’lishi lozim. Masalan, ikki oddiy kasr umumiy maxrajini topish algoritmi har qanday kasrlar umumiy maxrajini topish uchun ishlatiladi. 3

5-xossa . Natijaviylik, ya’ni har bir algoritm chekli sondagi qadamlardan so’ng albatta natija berishi lozim. Bu xossalar mohiyatini o’rganish va konkret algoritmlar uchun qarab chiqish talabalarning xossalar mazmunini bilib olishlariga yordam beradi. Algoritmning tasvirlash usullari Algoritmning tasvirlash usullari haqida gapirganda algoritmning berilish usullari xilma-xilligi va ular orasida eng ko’p uchraydiganlari quyidagilar ekanligini ko’rsatib o’tish joiz: 1. Algoritmning so’zlar orqali ifodalanishi. 2. Algoritmning formulalar yordamida berilishi. 3. Algoritmning jadval ko’rinishida berilishi, masalan, turli matematik jadvallar, loteriya yutuqlari jadvali, funksiyalar qiymatlari jadvallari bunga misol bo’ladi. 4. Algoritmning dastur shaklida ifodalanishi, ya’ni algoritm kompyuter ijrochisiga tushunarli bo’lgan dastur shaklida beriladi. 5. Algoritmning algoritmik tilda tasvirlanishi, ya’ni algoritm bir xil va aniq ifodalash, bajarish uchun qo’llanadigan belgilash va qoidalar m ajmui algoritmik til orqali ifodalashdir. Ulardan o’quv o’rganish tili sifatida foydalanilmoqda. Bo’lardan Ye-praktikum yoki Ye-tili algoritm ijrochisi algoritmik tili ham mavjud. 6. Algoritmlarning grafik shaklda tasvirlanishi. Masalan, grafiklar, sxemalar ya’ni blok - sxema bunga misol bo’la oladi. Blok sxemaning asosiy elementlari quyidagilar: oval (ellips shakli)-algoritm boshlanishi va tugallanishi, to’g’ri burchakli to’rtburchak-qiymat berish yoki tegishli ko’rsatmalarni bajarish. Romb - shart tekshirishni belgilaydi. Uning yo’naltiruvchilari tarmoqlar bo’yicha biri ha ikkinchisi yo’q yo’nalishlarni beradi, parallelogramm- ma’lumotlarni kiritish yoki chiqarish, yordamchi algoritmga murojaat - parallelogramm ikki tomoni chiziq, yo’naltiruvchi chiziq - blok-sxemadagi harakat boshqaruvi, nuqta-to’g’ri chiziq (ikkita parallel) - qiymat berish. Algoritmda bajarilishi tugallangan amallar ketma-ketligi algoritm qadami deb yuritiladi. Har bir alhoxida qadamni ijro etish uchun bajarilishi kerak bo’lgan amallar haqidagi ko’rsatma buyruq deb aytiladi. Algoritmlarni ko’rgazmaliroq qilib tasvirlash uchun blok-sxema, ya’ni geometrik usul ko’proq qo’llaniladi. Algoritmning blok-sxemasi algoritmning asosiy tuzilishining yaqqol geometrik tasviri: algoritm bloklari, ya’ni geometrik shakllar ko’rinishida, bloklar orasidagi aloqa esa yunaltirilgan chiziqlar bilan ko’rsatiladi. Chiziqlarning yunalishi bir blokdan so’ng qaysi blok bajarilishini bildiradi. Algoritmlarni ushbu usulda ifodalashda vazifasi, tutgan o’rniga qarab quyidagi geometrik shakl(blok) lardan foydalaniladi. Algoritmlar berilishi va ifodalanishiga qarab: chiziqli, tarmoqlanuvchi va 4

takrorlanuvchi turlarga bo’linadi. Algoritmning turlari bilan tanishtirganda, avvalo hech qanday shart tekshirilmaydigan va tartib bilan faqat ketma-ket bajariladigan jarayonlarni ifodalaydigan chiziqli algoritmlar aytib o’tiladi. Algoritm xato natijalarni keltirib chiqaradigan yoki umuman natija bermaydigan bo'lsa, xatolarni o'z ichiga oladi. Algoritm har qanday to'g'ri kirish uchun to'g'ri natijalarni beradigan bo'lsa, xatosiz bo'ladi. Ma'lumotlarni kirish va chiqish turlari bo'yicha farqlash mumkin - Raqamli masalalarni yechish algoritmlari (birinchi bo'lib paydo bo'ldi); - Raqamli bo'lmagan algoritmlar. Birlashtirib saralash algoritmlari. Samarali saralash algoritmlari. Birlashtirib saralash algoritmlari. Birlashtirib saralashni rekursiv va rekursiv bo'lmagan algoritmlari. Vaqt va xotira bo`yicha murakkabliklar tahlili. Merge prosedurasi birlashtirib saralashni asosiy prosedurasi sifatida. Birlashtirish protsedurasi bajarilishda xotirani tejash. Tashqi birlashtirib saralash. Tahlil va murakkablik. Ma’lumki, inson kundalik turmushida turli - tuman ishlarni bajaradi. Har bir ishni bajarishda esa bir qancha elementlarni ketma - ket amalga oshirishga to‘g‘ri keladi. Mana shu ketma-ketlik yozilsa, u bajariladigan ishning algoritmi bo‘ladi. Algoritm ma’lum bir buyruqlar to‘plami bo‘lib, bajaruvchi uchun aniq ko‘rsatmalarni o‘z ichiga mujassamlashtiradi. Ushbu buyruqlar bajaruvchiga ko‘rsatilgan maqsadga erishish uchun asos bo‘lishi kerak. Demak, qo‘yilgan masalani bajarish ma’lum ketma-ketlikda elementlarni ijro etish orqali erishiladi. Bunda algoritmni bajaruvchi algoritm ijrochisi hisoblanadi. Umuman, uni 2 guruhga ajratish mumkin: 1-guruh algoritmlarining ijrochisi faqat inson bo‘lishi mumkin. 2-guruh algoritmlarining ijrochisi ham inson, ham kompyuter bo‘lishi mumkin. Bu guruh algoritmlari ijrochisini kompyuter zimmasiga yuklash mumkin. Buning uchun algoritmni kompyuter tushunadigan biror dasturlash tilida yozib, keyin uning xotirasiga kiritish kifoya. Umuman olganda ijrochi algoritmda mavjud maqsadni bilmaydi. U bevosita keltirilgan buyruqlarni bajaradi. Informatikada algoritmlarning ijrochisi kompyuter deb hisoblanadi. 5

Похожие

MA’LUMOTLARNI SARALASH. SARALASHNING PIRAMIDALI USULI
Ko’p oqimli birlashtirish saralash
Ma’lumotlarni saralash usullari
Ko’p oqimli birlashtirish saralash algoritimi
Atribut va geofazoviy ma’lumotlarni birlashtirish