logo

MergeSort algoritmi.Algoritmning murakkabligini tahlil qilish

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

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