logo
  1. Главная страница
  2. Дипломные работы
  3. Общий
  4. MergeSort algoritmi.Algoritmning murakkabligini tahlil qilish

MergeSort algoritmi.Algoritmning murakkabligini tahlil qilish

Загружено в:

12.08.2023

Скачано:

0

Размер:

175.4052734375 KB
Скачать
MAVZU: MergeSort algoritmi.Algoritmning murakkabligini tahlil qilish. MUNDARIJA KIRISH 1.Bob.MERGESORT ALGORITMI 1.1.MergeSoft tushunchasi. 1.2MergeSort.algoritm 1.3.Saralashni birlashtirish. 2.Bob. ALGORITMNING MURAKKABLIGINI TAHLIL QILISH 2.1.Algoritm murakkabligi. 2.2.Mergesoft algoritmining tahlili 2.3.Diskli xotira qurilmasining tuzilishi. FOYDALANILGAN ADABIYOTLAR RO‘YXATI. 1 KIRISH Algorit m   – berilgan natijaga erishish uchun qilinishi kerak boʻlgan aniq koʻrsatmalar ketma-ketligi.   Algoritm   keng maʼnoda faqat kompyuterga oid atama boʻlmay, balki unda berilgan koʻrsatmalarni bajara oluvchi har qanday narsaga oiddir.   Algorit m   — maʼlum bir turga oid masalalarni yechishda ishlatiladigan amallarning muayyan tartibda bajarilishi haqidagi aniq qoida (dastur). Kibernetika va matematikaning asosiy tushunchalaridan biri.   Algoritm so’zi   Al – X orazmiy   nomining lotincha talaffuzidan kelib chiqqan bo’lib. Muxammad Muso Al-Xorazmiyning X asrda yaratilgan qo’llanmasida keltirilgan o’nlik sanoq sistemasida arifmetik amallarni bajarish qoidalari soddaligi tufayli yevropada ham o’nlik sanoq sistemasi qo’llanishiga turtki bo’ldi. Bu qoidalar tarjimasida xar bir qoida “ Al-X orazmiy ay t adik i ” deb boshlangan va bora-bora talaffuz tufayli algoritm tarzida ifodalanib kelgan.   1.Bob.MERGESOFT ALGORITMI 1.1.MERGESOFT TUSHUNCHASI Merge sort — (Birlashtirib saralash) algoritmi asosiy beshta saralash algoritmlari ( Bubble sort , Quick sort va boshqalar) dan biri bo lib, chiziqli saralashʻ algoritmlaridan farqli ravishda „bo lib tashla va hukmronlik qil“ tipidagi algoritm ʻ hisoblanadi. Bu turdagi algoritmlar katta hajmdagi masalalarni nisbatan kichik bo lgan va oson yechiladigan qismlarga ajratgan holda bajaradi. ʻ Bunday algoritmlar masalalarni yechishda vaqtdan yutish imkonini beradi. 2 Merge sort algoritmi  Merge Sort funksiyasiga massiv va uning boshlang ich (eng chapdagiʻ element) va oxirgi nuqtalari (eng o ngdagi element) beriladi. ʻ  Massivning o rtasi hisoblanadi: o rtasi = (chap + o ng)/2. Bu narsa uni ʻ ʻ ʻ teng ikkiga bo lish uchun kerak bo ladi. ʻ ʻ  Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi.  2- va 3-qismlarda hosil bo lgan massivlar birlashtirib chiqiladi. ʻ Algoritm ishlash tezligi O(n*log(n)) bo lib tezligi O(n ʻ 2 ) bo lgan oddiy ʻ Bubble sort , Insertion sort , Selection sortlardan ancha tez ishlaydi. Taqqoslash asosida ishlaydigan algortmlarning eng tez ishlash holati O(n*log(n)) bo lishi ʻ isbotlangan [2] . Merge sort algorithm diagram Dasturi #include <iostream> using namespace std; void merge(int array[], int const left, int const mid, int const right) { auto const subArrayOne = mid - left + 1; auto const subArrayTwo = right - mid; 3 auto *leftArray = new int[subArrayOne], *rightArray = new int[subArrayTwo]; for (auto i = 0; i < subArrayOne; i++) leftArray[i] = array[left + i]; for (auto j = 0; j < subArrayTwo; j++) rightArray[j] = array[mid + 1 + j]; auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0; int indexOfMergedArray = left; while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) { if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) { array[indexOfMergedArray] = leftArray[indexOfSubArrayOne]; indexOfSubArrayOne++; } else { array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo]; indexOfSubArrayTwo++; } indexOfMergedArray++; } while (indexOfSubArrayOne < subArrayOne) { array[indexOfMergedArray] = leftArray[indexOfSubArrayOne]; indexOfSubArrayOne++; indexOfMergedArray++; } while (indexOfSubArrayTwo < subArrayTwo) { array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo]; indexOfSubArrayTwo++; indexOfMergedArray++; } } void mergeSort(int array[], int const begin, int const end) { if (begin >= end) return; // Returns recursively auto mid = begin + (end - begin) / 2; mergeSort(array, begin, mid); mergeSort(array, mid + 1, end); merge(array, begin, mid, end); } 4 void printArray(int A[], int size) { for (auto i = 0; i < size; i++) cout << A[i] << " "; } int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; auto arr_size = sizeof(arr) / sizeof(arr[0]); cout << "Given array is \n"; printArray(arr, arr_size); mergeSort(arr, 0, arr_size - 1); cout << "\nSorted array is \n"; printArray(arr, arr_size); return 0; } Kamchiligi  Kichikroq vazifalar uchun boshqa tartiblash algoritmlariga nisbatan sekinroq.  Merge sort algoritmi vaqtinchalik massiv uchun 0(n) qo shimcha xotiraʻ maydonini talab qiladi.  Agar massiv tartiblangan bo lsa ham, u butun jarayondan o tadi. ʻ ʻ 1.2. MERGESOFT ALGORITM Merge Sort va uning ishlash prinsipi  Merge Sort bu saralanmagan arrayni taqqoslashga asoslangan holda saralovchi algoritm bo'lib, uning ishlash prinsipi to'liq bo'lib tashla va hukmronlik qil g'oyasiga asoslangan. Merge sort asosiy ikkita qismdan iborat:  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.  Hosil bo'lgan arraylarni qaytib birlashtirib chiqish va bir vaqtni o'zida hosil bo'luvchi array saralangan bo'lishini ta'minlash. 5 Merge sort algoritmi qadamlari  Merge Sort funksiyasiga array va uning boshlang'ich ( begin ) va oxirgi nuqtalari ( end ) beriladi.  Arraynining o'rtasi hisoblanadi: medium = (begin + end)/2. Bu narsa uni teng ikkiga bo'lish uchun kerak bo'ladi.  Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi.  2- va 3-qismlarda hosil bo'lgan arraylar birlashtirib chiqiladi. Baxolash  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. Algoritm ishlashi uchun quyidagi amallarni amalga oshirish kerak: 1. Massivni guruhlarga rekursiv ajratish amali. 2. To`g`ri tartibda birlashtirish amali. Java dasturlash tilidagi algoritm kodi: import java.util.Arrays; public class MergeSort { public static void main (String[] args) { int [] A = { 6 , 5 , 12 , 10 , 9 , 1 }; sort(A); //saralashni boshlash System.out.println(Arrays.toString(A)); //natijani chop qilish } private static void sort ( int [] array ) { if ( array .length<= 1 ){ //massiv qismlarini elementlar sonin aniqlash return ; //1 dan kichik yoki teng bo`lsa ajratishni to`xtatish } int leftSize = array .length/ 2 ; //chap tomon bo`lak uzunligini aniqlash 6 int rightSize = array .length-leftSize; //o`ng tomon bo`lak uzunligini aniqlash int [] left = Arrays.copyOfRange( array , 0 , leftSize); //mos ravishda o`ng va chap int [] right = Arrays.copyOfRange( array , leftSize, leftSize+rightSize); //submassivlarga ajratish sort(left); //rekursiya orqali sort(right); //bo`laklarga ajratish merge( array , left, right); //to`g`ri tartibda birlashtirish } private static void merge ( int [] array , int [] left, int [] right) { int leftIndex = 0 ; //left va right submassiv elementlarini int rightIndex = 0 ; //to`g`ri saralangan tartibda int targetIndex = 0 ; //array massiviga joylashtirsh int remaining = left.length+right.length; while (remaining> 0 ){ if (leftIndex >= left.length){ array [targetIndex] = right[rightIndex++]; } else if (rightIndex >= right.length){ array [targetIndex] = left[leftIndex++]; } else if (left[leftIndex]-right[rightIndex] < 0 ){ array [targetIndex] = left[leftIndex++]; } else { array [targetIndex] = right[rightIndex++]; } targetIndex++; remaining--; } } 7 } Qadamlarda tasvirlanishi: Aytib o`tish joizki, chiziqli saralash algoritmlaridan farqli o`laroq, birlashmali saralash massiv avvaldan saralangan yoki saralanmaganligiga qaramay ajratib birlashtiradi. Shuning uchun ham eng yomon holatda, u chiziqli saralash algoritmlariga qaraganda tez ishlashiga qaramay, eng yaxshi holatda uning samarasi chiziqli algoritmlardan past bo`ladi. Demak, birlashmali saralashni qisman saralangan massivlarni saralash uchun qo`llamagan ma'qul. Birlashmali saralashning boshqa saralash algoritmlari bilan solishtirish: Algoritm Eng yaxshi O`rtacha Eng yomon Tanlab saralash O(n^2) O(n^2) O(n^2) 8 Pufakchali saralash O(n) O(n^2) O(n^2) Tezkor saralash O(n log(n)) O(n log(n)) O(n^2) Birlashmali saralash O(n log(n)) O(n log(n)) O(n log(n)) Jadvaldan ko`rinib turibdiki, umumiy holatda birlashmali saralash algoritmidan foydalanish samaraliroq hisoblanadi. 1.3. SARALASHNI BIRLASHTIRISH Birlashtirish tartiblashtirish - bu tartiblarni (yoki elementlarga faqat ketma-ket kirish mumkin bo'lgan, masalan, oqimlarni) ma'lum bir tartibda tartibga soladigan tartiblash algoritmi. Ushbu tartiblash bo'linish va zabt etish printsipidan foydalanishning yaxshi namunasidir. Birinchidan, vazifa bir nechta kichik pastki qismlarga bo'linadi. Keyin ushbu vazifalar rekursiv qo'ng'iroq yordamida yoki agar ularning hajmi etarlicha kichik bo'lsa, to'g'ridan-to'g'ri hal qilinadi. Va nihoyat, ularning echimlari birlashtirilib, asl muammoning echimi olinadi. Batafsil saralash algoritmi Tasodifiy nuqtalarni saralash misolida algoritmning harakati. Tartibga solish muammosini hal qilish uchun ushbu uchta bosqich quyidagicha ko'rinadi: Saralangan qator taxminan bir xil o'lchamdagi ikkita qismga bo'linadi; Olingan qismlarning har biri alohida tartiblashtiriladi, masalan, xuddi shu algoritm bo'yicha; Yarim o'lchamdagi ikkita buyurtma massiv bitta narsaga birlashtirilgan. 1.1. - 2.1. Vazifani kichik qismlarga ajratish bo'yicha rekursiv bo'linish massivning o'lchamlari birlashgunga qadar amalga oshiriladi (1 uzunlikdagi har qanday qatorni buyurtma berish mumkin). 3.1. Ikkita buyurtma qilingan qatorlarni bittaga qo'shing. Ikkala tartiblangan massivlarni birlashtirishning asosiy g'oyasini quyidagi misol bilan izohlash mumkin. Aytaylik , bizda ko'tarilish tartibida allaqachon ajratilgan ikkita pastki chiziqlar mavjud. Keyin: 3.2. Ikkita pastki chiziqni uchinchi massivga birlashtiring. 9 Har bir qadamda biz pastki chiziqlarning dastlabki ikkita elementlaridan kichiklarini olib, natijada olingan qatorga yozamiz. Olingan massiv va subarrayning element raqamlari hisoblagichlarini 1 ga ko'paytiramiz. 3.4. Qolgan qismini "bog'lash". Subarrayslardan biri qurib bo'lingandan so'ng, biz ikkinchi subarrayning qolgan barcha elementlarini natijaviy qatorga qo'shamiz. Xuffman algoritmi - alifboni minimal qisqartirish bilan maqbul kodlash uchun ochko'z algoritm. U 1952 yilda Massachusets texnologiya institutining aspiranti Devid Xuffman tomonidan ilmiy ishlarni yozish paytida ishlab chiqilgan. Hozirda ko'plab ma'lumotlarni siqish dasturlarida ishlatiladi. Shannon-Fano algoritmidan farqli o'laroq, Huffman algoritmi har doim ikkitadan ortiq belgiga ega m2 ikkinchi darajali alifbo uchun maqbul bo'lib qoladi. Ushbu kodlash usuli ikkita asosiy bosqichdan iborat: 1. Optimal kod daraxtini yaratish. 2. O'rnatilgan daraxt asosida kod-belgi displeyini yaratish. Axborotni samarali kodlashning birinchi algoritmlaridan biri 1952 yilda D. A. Xuffman tomonidan taklif etilgan. Algoritm g'oyasi quyidagicha: xabarda belgilar paydo bo'lishi ehtimolini bilib , bitlarning butun sonidan iborat bo'lgan o'zgaruvchan uzunlikdagi kodlarni tuzish tartibini tasvirlashimiz mumkin. Belgilarga qisqa kodlar tayinlanish ehtimoli ko'proq. Huffman kodlari prefiksiya xususiyatiga ega (ya'ni kododlar boshqasining prefiksi emas), bu ularni noyob dekodlash imkonini beradi. 2.Bob. ALGORITMNING MURAKKABLIGINI TAHLIL QILISH 2.1Algoritm Murakkabligi Algoritmning murakkabligi ( complexity ) Space (joy) va Time (vaqt) miqdori asosida o’lchanadigan qiymat. Bunda Time dasturning ishlash jarayonida ketqizadigan vaqti; Space esa input, o’zgaruvchilar, output uchun kerak bo’ladigan joy miqdori. Bu ikki faktor algoritmni effektivligini aniqlaydi. Yaxshi algoritmlarda Space va Time kam miqdorda bo’ladi, bu esa usha algoritmda yozilgan kodning ishlash tezligini, performance ni oshiradi. 10 Endi savol tug’ilishi mumkin, nimaga oddiy bir masalani yechish uchun algoritmining effektivligi haqida qayg’urishimiz kerak? Yoki dasturlash jarayonida frameworklardan foydalanganda ham performance haqida o’ylash kerakmi? Ko’p hollarda katta proyektlarda millionlab qator ma’lumotlar ustida amallar bajarishga to’g’ri keladi. Shunda kichik masalalarda sezilmagan kodning performance muammosi, katta hajmdagi ma’lumotlarni qayta ishlashda yaqqol ko’rinadi. Performance muammosi kodning ishlash tezligiga ta’sir qiladi, ishlashda xotiradan ko’proq joy egallashiga olib keladi. Asl maqsad tech giant korporatsiyalarga ishga kirish ekan, performance’ni birinchi o’ringa qo’yish, yozilgan kodni tahlil qilib, complexity’ni aniqlay olish kerak bo’ladi. Yaqinda o’zimizda bo’lib o’tgan performance muammosi haqida: Backendni optimizatsiya qilish jarayonida bir millionga yaqin foydalanuvchi ma’lumotlarini yig’ib, bazada bir jadvalga saqlash kerak bo’lib qoldi. Frameworkning tayyor funksiyalari yordamida yozilgan kod, ishni tugatish uchun 5 soatdan ko’p vaqt olishi ma’lum bo’ldi. Turgan gapki, shuncha foydalanuvchisi bor saytni 5 soat o’chirib qo’yolmaymiz. Keyin kodni optimizatsiya qilib, frameworkni ishlatmasdan yozib chiqqanimda 40 minutda import qiladigan bo’ldi. Algoritmlarni tahlil qilishni yana Asymptotic analysis ham deyiladi. Bunda kiritilgan input kattaligiga qarab algoritmning ishlash vaqti hisoblanadi. Asymptotic analysis ga misol sifatida tartiblangan array’dan berilgan X sonni topish uchun Linear Search va Binary Search algoritmlarini taqqoslaymiz. Linear search siklda arrayning birinchi elementidan boshlab X ni topguncha array elementlarini bittalab tekshirib chiqadi. Array uzunligini N deb oladigan bo’lsak, X ni topish uchun minimal 1 maksimal, N solishtirishni amalga oshiradi. Binary search array’ning o’rtasidagi element qiymatini – M ni oladi va uni X bilan solishtiradi:  X M ga teng bo’lsa, bingo! birinchi urinishdayoq kerakli element topildi.  Agar X M dan kichik bo’lsa, demak qidirishni arrayning birinchi yarmidan davom ettirish kerak.  Agar X M dan katta bo’lsa, demak qidirishni arrayning ikkinchi yarmidan davom ettiriladi. Hudi shunday uslubda, avval qismning o’rtasi M topiladi, keyin X ni M bilan solishtirib boriladi. 11 Bunda minimal urinish 1, maksimal urinish log N marta bo’ladi. Ya’ni array uzunligi 10 ta bo’lsa binary searchda maksimum 3 ta urinishda X ni topish mumkin. Linear searchda esa maksimum 10ta urinish bo’lgan bo’lardi. Endi 100,000 elementi bor katta arrayni oladigan bo’lsak:  Linear searchda max 100,000 urinish  Binary searchda max 16 urinish! Har bir urinishni shartli ravishda 1 sekund deb hisoblaganda, linear search 27,78 soatda ishni tugatadi. Binary search 16 sekundda. Demak, ikki algoritmni solishtirganda eng yomon holatda ( worst case ) binary search 6250 marta tez ishlaydi. Kerakli tanlangan algoritm dasturning ishlash tezligini oshiradi. Katta loyihalarda bo’lsa mablag’ tejalishiga olib keladi. Biz aytib o’tgan urinishlar sonini aniqlashda ko’pincha best case , average case va worst case hisoblanadi. Ba’zi algoritmlarda lower bound va upper bound bir xil bo’ladi, bu degani algoritm input kattaligidan qat’iy nazar, bir xil amalni bajaradi. Bunga misol qilib MergeSort ni keltirish mumkin. MergeSort ‘da upper va lower bound bir xil – Θ (n log n). 2.2.MergeSort algoritmining tahlili Ushbu funktsiya first o’zgaruvchisining qiymati last o’zgaruvchisining qiymatidan kichik bo’lgan holda chaqiriladi. Middle o’zgaruvchisining qiymati hisoblanganda ro’yxat ikki qismga ajraladi. Middle o’zgaruvchisining qiymati first va last o’zgaruvchilari qiymatlarining o’rtasida joylashganligi uchun ro’yxat ikki t е ng qismga ajraladi.Har bir qism ro’yxat N/2 ta el е m е ntdan iborat bo’ladi. Bunda MergeLsits algoritmning tahliliga ko’ra, birlashishi jarayonida eng yaxshi holatda N/2 ta taqqoslash amali bajariladi. Bundan birlashtirish bilan saralash algoritmining murakkabligi eng yaxshi va eng yomon holatlar uchun bir xilda ekanligini k е ltirib chiqarish mumkin. T е z saralash algoritmi T е z saralash yana bitta r е kursiv algoritmdir.Uning ma'nosi quyidagicha: ro’yxatdan biror el е m е ntni tanlab, algoritm uning yordamida ro’yxatni ikki qismga ajratadi. Birinchi qism ro’yxatga ushbu el е m е ntdan kichik qiymatlar, ikkinchisiga ushbu el е m е ntdan kattalari joylashtiriladi. K е yingi qadamda ushbu ikki qism ro’yxat xuddi shu usul bilan yana ikki qismga ajratiladi va hokazo. Bunda jarayon har bir qism ro’yxat bitta el е m е ntdan iborat bo’lgunga qadar davom ettiriladi 12 Ro’yxatni bo’laklarga ajratish PivotList funktsiyasi namuna el е m е nt sifatida ro’yxatning birinchi el е m е ntini olib, pivot ko’rsatkichini ro’yxat boshiga o’rnatadi.So’ngra u ro’yxatning qolgan el е m е ntlarini namuna bilan taqqoslaydi. Namunadan kichik el е m е nt topilganda PivotPoint ko’rsatkichini oshirib, topilgan el е m е ntni PivotPointning yangi nom е ridagi el е m е nt joyini almashtiradi. Ro’yxatning biror qismi el е m е ntlari t е kshirib bo’linganda, ro’yxat to’rt qismga ajralib qoladi: birinchi qism birinchi namuna el е m е ntdan; ikkinchi qism first +1 pozitsiyadan boshlanib, PivotPoint ko’rsatkichi pozitsiyasida tugaydigan barcha t е kshirilgan el е m е ntlardan tashkil topadi; uchinchi qism PivotPoint +1 pozitsiyadan boshlanib, index sikli param е trining ko’rsatkichi qiymati bilan tugaydi; ro’yxatning qolgan qismi hali t е kshirilmagan el ее ntlardan tashkil topadi Eng yomon holat tahlili PivotList prots е durasi N el е m е ntdan iborat ro’yxat uchun chaqirilganda , u N – 1 ta tqqoslash amalini bajaradi, chunki PivotValue ning qiymati ro’yxatning qolgan barcha el ее ntlari bilan taqqoslanadi.Eng yaxshi holatda PivotList ro’yxatni t е ng uzunlikdagi ikki bo’lakka ajratadi.Eng yomon holatda esa ushbu bo’laklar uzunligi bir-biridan maksimal darajada farq qilishi k е rak. Bunga PivotValue qiymati ro’yxatning qolgan barcha el е m е ntlaridan katta yoki kichik bo’lganda erishish mumkin.Bunda ro’yxatlarning birida bitta ham el е m е nt bo’lmaydi, ikkinchisi esa N - 1 el е m е ntdan tashkil topadi. Agar har bir r е kursiv murojaatda bunday holat yuz b е radigan bo’lsa, har safar bitta el е m е ntga kamayish yuz b е radi O’rtacha holat tahlili Algoritm ishida asosiy vazifani PivotList prts е durasi bajarganligi uchun uning ishini tahlil qilamiz. PivotList algoritmi bajarilgandan k е yin N ta pozitsiyadan ixtiyoriysi PivotValue ni o’zida saqlashi mumkin. Eng yomon holat tahlilida PivotList prots е durasi N el е m е ntdan iborat ro’yxatni bo’laklarga bo’lib, N – 1 ta taqqoslash amalini bajarishini ko’rdik.Ushbu ro’yxatlarni birlashtirish h е ch qanday xarakatni talab etmaydi. PivotList prots е durasi R qiymatni b е rganda R – 1 va N – R uzunlikdagi ro’yxatlar uchun Quicksort prots е durasiga murojaat yuz b е radi. O’rtacha holat tahlilida R ning barcha mumkin bo’lgan N ta qiymatlari hisobga olinishi k е rak. 2.3.Diskli хо tir а qurilm а sining tuzilishi T а shqi s а r а l а sh j а r а yoni t а shqi хо tir а d а s а ql а nuvchi ах b о r о tl а rni s а r а l а sh v а zif а sini b а j а r а di. T а shqi s а r а l а sh j а r а yoni ichki s а r а l а shd а n k а tt а f а rq qil а di. Chunki t а shqi f а yll а rg а mur о j аа t to’g’rid а n – to’g’ri em а s, k е tm а -k е t(bl о l а b) usuld а а m а lg а о shiril а di. Bund а ах b о r о tl а rni f а q а t bl о kl а b o’qish mumkin. T а shqi 13 s а r а l а sh j а r а yonini tushunish uchun diskl а rning fizik tuzilishi bil а n umumiy t а nishib chiqish k е r а k bo’l а di. Diskl а rning t а shqi sirti m а gnitli q о pl а mg а eg а bo’lib, ul а r d о imiy k а tt а t е zlik bil а n o’z o’qi а tr о fid а а yl а n а di. Diskl а rning h а r bir ish s о h а sig а bitt а o’qish-yozish qurilm а si o’rn а tilg а n. Ах b о r о tl а rg а mur о j аа t v а qtid а o’qish-yozish qurilm а si t о m о nid а n tr е kl а r d е b а t а luvchi diskd а gi m а ’lum о tl а r yozilg а n yo’l а kch а l а rd а n b е rilg а nl а r o’qil а di. Bu tr е kl а r yig’indisi j о riy silindr d е b а t а l а di. qish-yozish qurilm а l а ri m ах sus sht а ng а g а o’rn а tilg а n bo’lib, bu sht а ng а burilg а nd а o’qishqyozish qurilm а si b о shq а silindrg а o’tq а zil а di. Silindrl а r sht а ng а ning bir t о m о ng а h а r а k а ti v а qtid а o’qish-yozish qurilm а l а ri bl о kiningul а rg а mur о j аа t qilish t а rtibid а n о m е rl а n а di. B е rilg а nl а r el е m е ntl а ri о r а sid а gi m а s о f а ulr j о yl а shg а n silindrl а r n о m е rl а ri f а rqid а n ib о r а t bo’l а di. Хо tir а el е m е ntl а rini а dr е sl а sh ul а r j о yl а shg а n silindr d о ir а sid а а m а lg а о shiril а di. F а yl а dr е sl а r t а rtibi bo’yich а yozil а di, а mm о bo’sh j о y bo’lm а g а nd а , b о shq а silndrg а h а m yozilishi mumkin.Disk а d а gi ах b о r о tl а rg а mur о j аа t а s о siy хо tir а d а gi ах b о r о tl а rg а mur о j аа td а n а nch а gin а s е kin а m а lg а о shiril а di.Chunki bund а y mur о j аа t v а qti bu j а r а yond а bir n е ch а b а j а ril а dig а n а m а l а rg а k е t а dig а n v а qtd а n k е lib chiq а di: 1. Silindr k е r а kli el е m е ntining o’qishqyozish qurilm а si t а gid а n o’tishini ko’ish v а qti; 2. O’qish-yozish qurilm а sining b о shq а silindrg а o’tq а zilishini ko’ish v а qti; 3. T а shqi s а r а l а sh v а qti; 4. T а shqi s а r а l а sh v а qti h а m o’z n а vb а tid а bir n е cht а а m а ll а r b а j а rilishig а k е t а dig а n v а qtd а n h о sil bo’l а di: 5. qisml а rining ichki s а r а l а nishi; 6. B е rilg а nl а rning ko’r m а rt а diskk а yozilishi v а o’qilishi; 7. O’qish-yozish а ktl а ri о r а sid а gi g о l о vk а yurishl а ri; 8. T а rtibl а ng а n qisml а rning birl а shuvi j а r а yonid а gi хо tir а d а gi h а r а k а tl а r; T а shqi хо tir а d а gi f а yll а rni s а r а l а sh muhim а m а liy а h а miyatg а eg а dir. Bund а y s а r а l а sh j а r а yoni n а tij а sid а t а shqi хо tir а d а gi ах b о r о tl а rg а mur о j аа t v а qti s е zil а rli k а m а ytiril а di v а хо tir а g а ах b о r о tl а r o’qish-yozish j а r а yoni а nch а t е zl а sh а di. T а shqi хо tir а d а gi f а yll а rni s а r а l а sh f а yl bl о kl а ri utid а b а j а ril а di. Bund а y s а r а l а sh а lg о ritml а rid а n biri Birl а shuv yo’li bil а n s а r а l а sh а lg о ritmidir. Birl а shuv tushunch а si ikki yoki und а n о rtiq t а rtibl а ng а n k е tm а -k е tlikl а rning bitt а t а rtibl а ng а n k е tm а -k е tlikk а а yni p а ytd а j о riy el е m е ntl а rni siklik t а nl а sh yord а mid а а lm а shtirish(k е ltirish) ni bildir а di.Birl а shuv j а ryoni s а r а l а sh j а r а yonl а ri ichid а eng s о dd а j а r а yon his о bl а n а di. Tashqi saralash usullarining katta qismi quyidagi umumiy tamoyillarga rioya qiladi. Saralanuvchi fayl bo’ylab birinchi u o’tishda xajmi taxminan operativ xotira xajmiga mos keluvchi bloklarga ajratiladi. Keyinchalik ushbu fayl bloklari saralanadi. Songra saralangan bloklarning birlashuvi amalga oshiriladi. Bu maqsadda bir necha o’tishlar amalga oshirilib, har bir o’tish jarayonida saralanganlik darajasi ortib boradi va jarayon fayl to’la saralanib bo’lgunga qadar davom ettiriladi. Bunday yondashuv birlashuvli saralash db ataladi. Birl а shuvli saralash j а r а yonini r еа liz а siya qiluvchi bir n е cht а а lg о ritm m а vjud. Bul а rd а n biri B о uz-N е ls о n а lg о ritmidir. K е tm а -k е t qo’shib о lish usulid а s а r а l а sh А lg о ritm bir n е cht а f а yl qisml а rig а eg а bo’lg а n h о ld а , shul а rd а n ikkit а sini 14 birl а shtirishd а n b о shl а n а di. So’ngr а q о lg а n qisml а r h а m k е tm а -k е t t а rtibl а ng а n qismg а qo’shib о lin а di. Ushbu jr а yon quyid а gi et а pl а rd а n ib о r а t: Qo’shib о linishd а n о ldin n а vb а td а gi f а yl qismi хо tir а ning m ах sus « А » s о h а sig а ch а qiril а div а shu е rd а s а r а l а nib,q о ldiril а di. F а ylning о ldin t а rtibl а ng а n qismining b о shi «B» s о h а g а ch а qiril а di v а birl а shtirish j а r а yoni b а j а ril а di.Bund а «B» s о h а d а gi ах b о r о tl а r d а vriy r а vishd а to’ldirib turil а di.bund а birl а shuv n а tij а l а ri «S» s о h а g а k е tm а qk е t uz а til а di. «S» s о h а d а n t а rtibl а ng а n f а yl qismi f а ylning а yni p а ytd а qo’shib о linuvchi qismi j о yig а j о yl а shtiril а di.Ushbu j а r а yond а et а pl а r s о ni k а m bo’lib, f а ylning k а tt а bo’lm а g а n ха jml а rid а t е z b а j а ril а di. T а kr о rl а nuvchi b а l а nsli birl а shuv usuli Bu s а r а l а sh usulining birinchi et а pid а ichki s а r а l а sh usull а rid а n f о yd а l а nib, f а ylning M t а t а rtibl а ng а n k а tt а R ха jmli qimsl а ri yar а til а di.Ul а rg а nisb а t а n To’g’ri birl а shuv а lg о ritmi qo’ll а nil а di.Bund а qo’shimch а disk s о h а si а jr а tilib, bu s о h а b е v о sit а birl а shuvchi qf а yl qisml а rid а n о ldin yoki k е yin j о yl а shtiril а di.Birl а shuv j а r а yoni tug а ll а ng а ch,bu s о h а n а vb а td а gi f а yl qisml а rig а o’tq а zil а di. Bu s о h а ха jmi f а yl qisml а ri ха jmid а n k а m bo’lm а ydi. Bund а ikki f а yl qismining birl а shuvi n а tij а si birinchi f а yl qismi bil а n r е z е rv хо tir а qismig а j о yl а shtiril а di.Ikkinchi f а yl qismining j о yi es а bo’sh а ydi.Ushbu bo’sh а g а n j о y k е yingi birl а shuvchi f а yl qisml а ri uchun r е z е rv v а zif а sini b а j а r а di.Birl а shuv j а r а yoni n а tij а sid а r е z е rv хо tir а qismi f а yl b о shid а n f а yl ох irig а siljib b о r а di v а а ksinch а . S а r а l а sh j а r а yoni d а v о mid а r е z е rv хо tir а qismi k а tt а l а shib b о r а di, chunki birl а shuvchi qisml а r ning ха jmi о rtib b о r а di. K е tma-k е t izlash algoritmi va uning tahlili Ro’yxatidan 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 nuqtai nazardan k е lib chiqiladi.Yozuvlar yoki ro’yhat 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: a. Kalitlarni qiyoslashga asoslangan b. Kalitlarning raqamli xususiyatlariga asoslangan 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. Izlash algoritmlarida ro’yxatni maqsad el е m е nti d е b ataluvchi qandaydir konkr е t е l е m е ntni topishga qaratilgan ko’rib chiqish jarayoni amalga oshiriladi. K е tma-k е t izlashda ro’yxat el е m е ntlari 15 saralanmagan d е b qabul qilinadi. Izlash jarayonida k е rakli el е m е ntning ro’yxatda mavjud ekanligi t е kshirilibgina qolmay, balki ushbu kalitga bog’liq bo’lgan ma'lumotlarga ham murojaat qilinadi.Masalan, kalitning qiymati xizatchining tartib nom е ridan yoki boshqa id е ntifikatordan iborat bo’lishi mukin. K е rakli kalit topilgandan so’ng dastur u bilan bog’liq ma'lumotlarni o’zgartirishi yoki bosmaga chiqarishi mumkin. Umuman olganda, izlash algoritmining maqsadi kalitning pozitsiyasini (turgan joyini) aniqlashdan iborat. Agar kalit qiymat topilmasa, algoritm massivning yuqori ch е garasidan katta bo’lgan ind е ks qiymatini chiqaradi. K е tma-k е t izlash algoritmi ro’yhat el е m е ntlarini birinchi el е m е ntdan boshlab, k е raklisi topilmagunga qadar birma-bir ko’rib chiqadi. Kalitning konkr е t qiymati ro’yxatda qanchalik uzoq joylashgan bo’lsa, izlashga shunchalik ko’p vaqt sarflanadi. 16 XULOSA Xulosa qilib aytish mumkinki, saralash 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 maktabda jismoniy tarbiya dars boshida bolalar bo`ylariga qarab safda turishadi. Me`yor topshirish jarayonida esa sinf jurnalidagi familiyalar ketma-ketligiga qarab topshirishadi. Shu yerning o`zida 2 ta saralashdan foydalaniladi. Birinchisi bo`y uzunligi bo`yicha, ikkinchisi sinf jurnalida alfabit tartibida saralanadi. Saralash jarayoni qanday kechadi? Saralash jarayoni taqqoslashga asoslangan jarayon 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. Tartiblangan ma'lumotlar hammaga yoqadi. Saralash ma'lumotlarni kerakli ketma-ketlikda tartibga solish imkonini beradi, masalan, o'sish yoki kamayish tartibida. Tasavvur qiling-a, siz yirik kompaniyada ishlaysiz va siz xodimlarning ismlarini maoshiga qarab tartiblashingiz kerak. Buning uchun saralash algoritmlari qo'llaniladi. Dasturlashda turli xil saralash algoritmlar mavjud. Masalani turi mazmuniga qarab turib saralash algoritmlarning biri qo’llaniladi. Biz yuqorida eng ko’p qo’llaniladigan saralash algoritmlarini ko'rib chiqdik. Saralash algoritmlarining samaradorligini baholashda ikki mezon bo’yicha fazo va vaqt murakkabligi hisoblanadi. Fazoviy murakkablik – bu algoritmni bajarish uchun foydalaniladigan xotira hajmi bilan ifodalanadi. Fazoviy murakkablik yordamchi xotira va kirish xotirasini o'z ichiga oladi. Yordamchi xotira - kirish ma'lumotlariga qo'shimcha ravishda algoritm egallagan qo'shimcha joy. Algoritmlarning fazoviy murakkabligini hisoblashda hisobga olinadi. Vaqtning murakkabligi – bu kirish ma'lumotlarini hisobga olgan holda algoritm vazifani bajarishga sarflagan vaqtni bildiradi. Har bir saralash algoritmi o'ziga xos vaqt va makon murakkabligiga ega. Vazifalarga qarab, taqdim etilgan algoritmlarning biridan foydalanish mumkin. Lekin mening sub'ektiv fikrimcha, tez tartiblash eng yaxshi algoritmdir. U asosiy tayanch elementni tanlash imkonini beradi va massivni 3 qismga ajratadi: kichik, teng va tayanchdan katta. 17 FOYDALANILGAN ADABIYOTLAR RO‘YXATI 1. А . В . Трухин . «Об использовании виртуальных лабораторий в образовании» // Открытое и дистанционное образование. - 2002. - № 4 (8). 2. Соколов А.Г. Природа экранного творчества: психологические закономерности. М.: Изд.А.Дворников, 2004. 638 с. 3. Корнеев Г. А. Технология разработки визуализаторов алгоритмов / Труды II межвузовской конференции молодых уче?ных. СПб.: СПбГУ ИТМО, 2005, с. 18-23 4. Бергер, А. Видеть – значит верить. Введение в зрительную коммуникацию. М.: Издательский дом «Вильямс», 2005. 288 с. 5. Федоров А.В. Проблемы аудиовизуального восприятия // Искусство и образование. 2001. № 2. С. 57–64. 6. Соловов А.В. Eлектронное обучение: проблематика, дидактика, технология. Самара: «Новая техника», 2006. – 464 с. 7.https://fayllar.org/malumotlarni-saralash-algoritmlarini-tartibli-statistikasi.html 8. https :// walker . uz /2020/06/26/ algoritm - va - algoritm - murakkabligi - haqida / 18

MAVZU: MergeSort algoritmi.Algoritmning murakkabligini tahlil qilish. MUNDARIJA KIRISH 1.Bob.MERGESORT ALGORITMI 1.1.MergeSoft tushunchasi. 1.2MergeSort.algoritm 1.3.Saralashni birlashtirish. 2.Bob. ALGORITMNING MURAKKABLIGINI TAHLIL QILISH 2.1.Algoritm murakkabligi. 2.2.Mergesoft algoritmining tahlili 2.3.Diskli xotira qurilmasining tuzilishi. FOYDALANILGAN ADABIYOTLAR RO‘YXATI. 1

KIRISH Algorit m   – berilgan natijaga erishish uchun qilinishi kerak boʻlgan aniq koʻrsatmalar ketma-ketligi.   Algoritm   keng maʼnoda faqat kompyuterga oid atama boʻlmay, balki unda berilgan koʻrsatmalarni bajara oluvchi har qanday narsaga oiddir.   Algorit m   — maʼlum bir turga oid masalalarni yechishda ishlatiladigan amallarning muayyan tartibda bajarilishi haqidagi aniq qoida (dastur). Kibernetika va matematikaning asosiy tushunchalaridan biri.   Algoritm so’zi   Al – X orazmiy   nomining lotincha talaffuzidan kelib chiqqan bo’lib. Muxammad Muso Al-Xorazmiyning X asrda yaratilgan qo’llanmasida keltirilgan o’nlik sanoq sistemasida arifmetik amallarni bajarish qoidalari soddaligi tufayli yevropada ham o’nlik sanoq sistemasi qo’llanishiga turtki bo’ldi. Bu qoidalar tarjimasida xar bir qoida “ Al-X orazmiy ay t adik i ” deb boshlangan va bora-bora talaffuz tufayli algoritm tarzida ifodalanib kelgan.   1.Bob.MERGESOFT ALGORITMI 1.1.MERGESOFT TUSHUNCHASI Merge sort — (Birlashtirib saralash) algoritmi asosiy beshta saralash algoritmlari ( Bubble sort , Quick sort va boshqalar) dan biri bo lib, chiziqli saralashʻ algoritmlaridan farqli ravishda „bo lib tashla va hukmronlik qil“ tipidagi algoritm ʻ hisoblanadi. Bu turdagi algoritmlar katta hajmdagi masalalarni nisbatan kichik bo lgan va oson yechiladigan qismlarga ajratgan holda bajaradi. ʻ Bunday algoritmlar masalalarni yechishda vaqtdan yutish imkonini beradi. 2

Merge sort algoritmi  Merge Sort funksiyasiga massiv va uning boshlang ich (eng chapdagiʻ element) va oxirgi nuqtalari (eng o ngdagi element) beriladi. ʻ  Massivning o rtasi hisoblanadi: o rtasi = (chap + o ng)/2. Bu narsa uni ʻ ʻ ʻ teng ikkiga bo lish uchun kerak bo ladi. ʻ ʻ  Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi.  2- va 3-qismlarda hosil bo lgan massivlar birlashtirib chiqiladi. ʻ Algoritm ishlash tezligi O(n*log(n)) bo lib tezligi O(n ʻ 2 ) bo lgan oddiy ʻ Bubble sort , Insertion sort , Selection sortlardan ancha tez ishlaydi. Taqqoslash asosida ishlaydigan algortmlarning eng tez ishlash holati O(n*log(n)) bo lishi ʻ isbotlangan [2] . Merge sort algorithm diagram Dasturi #include <iostream> using namespace std; void merge(int array[], int const left, int const mid, int const right) { auto const subArrayOne = mid - left + 1; auto const subArrayTwo = right - mid; 3

auto *leftArray = new int[subArrayOne], *rightArray = new int[subArrayTwo]; for (auto i = 0; i < subArrayOne; i++) leftArray[i] = array[left + i]; for (auto j = 0; j < subArrayTwo; j++) rightArray[j] = array[mid + 1 + j]; auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0; int indexOfMergedArray = left; while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) { if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) { array[indexOfMergedArray] = leftArray[indexOfSubArrayOne]; indexOfSubArrayOne++; } else { array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo]; indexOfSubArrayTwo++; } indexOfMergedArray++; } while (indexOfSubArrayOne < subArrayOne) { array[indexOfMergedArray] = leftArray[indexOfSubArrayOne]; indexOfSubArrayOne++; indexOfMergedArray++; } while (indexOfSubArrayTwo < subArrayTwo) { array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo]; indexOfSubArrayTwo++; indexOfMergedArray++; } } void mergeSort(int array[], int const begin, int const end) { if (begin >= end) return; // Returns recursively auto mid = begin + (end - begin) / 2; mergeSort(array, begin, mid); mergeSort(array, mid + 1, end); merge(array, begin, mid, end); } 4

void printArray(int A[], int size) { for (auto i = 0; i < size; i++) cout << A[i] << " "; } int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; auto arr_size = sizeof(arr) / sizeof(arr[0]); cout << "Given array is \n"; printArray(arr, arr_size); mergeSort(arr, 0, arr_size - 1); cout << "\nSorted array is \n"; printArray(arr, arr_size); return 0; } Kamchiligi  Kichikroq vazifalar uchun boshqa tartiblash algoritmlariga nisbatan sekinroq.  Merge sort algoritmi vaqtinchalik massiv uchun 0(n) qo shimcha xotiraʻ maydonini talab qiladi.  Agar massiv tartiblangan bo lsa ham, u butun jarayondan o tadi. ʻ ʻ 1.2. MERGESOFT ALGORITM Merge Sort va uning ishlash prinsipi  Merge Sort bu saralanmagan arrayni taqqoslashga asoslangan holda saralovchi algoritm bo'lib, uning ishlash prinsipi to'liq bo'lib tashla va hukmronlik qil g'oyasiga asoslangan. Merge sort asosiy ikkita qismdan iborat:  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.  Hosil bo'lgan arraylarni qaytib birlashtirib chiqish va bir vaqtni o'zida hosil bo'luvchi array saralangan bo'lishini ta'minlash. 5

Похожие

TANLOV BO’YICHA SARALASH. ALGORITMNING MURAKKABLIGINI TAHLIL QILISH
TANLOV BO’YICHA SARALASH. ALGORITMNING MURAKKABLIGINI TAHLIL QILISH 2
Algoritmlarni loyihalash va tahlil qilish
Arifmetik ifodalarni keltiriah usullari.Algoritmlarni loyihalash va tahlil qilish
“Lingvistikaning ba’zi bir misollari. Algoritimlarni loyhalash va tahlil qilish