logo

Ko’p oqimli birlashtirish saralash algoritimi

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

460.3369140625 KB
Ko’p oqimli birlashtirish saralash algoritimi
   
I Bob. Ko’p oqimli birlashtirib saralashning nazariy qismi. ........................... 2
1.2. Saralash tushunchasi ................................................................................. 3
1.3.Birlashtirish saralash ish jarayoni: ............................................................ 5
ADABIYOTLAR RO’YXATI ...................................................................... 20
ILOVA 1. Modul N1 boshlang’ich kod. ....................................................... 21 KIRISH
Saralash   algoritmlari   hozirgi   kunda   hayotimizda   juda   ko’p   qo’llaniladi.
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 ketmaketligiga qarab topshirishadi. Shu yerning o`zida 2 ta saralashdan
foydalaniladi.   Birinchisi   bo`y   uzunligi   bo`yicha,   ikkinchisi   sinf   jurnalida   alvabit
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.
1 I Bob. Ko’p oqimli birlashtirib saralashning nazariy qismi.
1.1. Saralash tarixi
Uch kishini bir necha yillardan buyon uzoq kosmosda olis sayyoralar tomon
olib ketayotgan kosmik kema g‘alati oltinrang bulut orasidan uchib o‘tdi. Kemada
tug‘ilgan   va   bir   yosh   bo‘lgan   Век   ismli   bola   hali   yurishni   o‘rganmagani   uchun
g‘ildirakli   aravachasida   katta   doira   shaklidagi   xonasida   bir   o‘zi   aylanib   yurishni
yoqtirardi. U aravachasini g‘ildiratib borib o‘yinchoqlarini egilib olar, o‘ynab yana
otib   yuborar   edi.   Век   oltinrang   bulut   ta‘sirida   o‘zida   bir   necha   xil   o‘zgarishlami
sezdi.   Birinchi   o‘zgarish   zehni   bilan   bog‘liq   bo‘lib,   u   endi   bola   bo‘lsa   ham
arifmetik amaUarni juda tez bajarar, har xil narsalarni turli ko‘rinishdagi miqdorini
bir   qarashda   juda   tez   aniqlab,   taqqoslay   olardi.   Ikkinchisi,   u   tajanglashganligi   va
endi   bolalar   o‘yinchoqlarini   o‘ynagisi   kelmay   qolganligi   edi.   Xonada   bir   o‘zi
zerikib qolganligidan chinqirib yig‘lay boshladi. 0 ‘g‘lini ovutishga kelgan ota-ona
bolani   qunt   bilan   ota-onasining   suhbatini   tinglayotganiga   e’tibor   berishdi.   0
‘g'lidagi   o‘zgarish]arni   sezgach,   zehni   o‘tkir   o‘g‘lini   ovutish   uchun   ota-onasi
xonani boshqacha jihozlab, faqat bir qo‘li bor hamda g'ildirakda yiiradigan sodda
dasturli   Saralovchi   I   nomli   robot   yasab   berishdi.   Keyin   robotni   boshqarishga
mo‘Ijallangan   dastur   tuzishga   yo‘naltirilgan   turli   boshqotirmali   masalalami   ayta
boshlashdi. Biz endi Век bilan birga shu masalalarni ko’rib chiqamiz. Avval xona
haqida.   Aytganimizdek,   doira   shakJidagi   devorlari   bo‘ylab   bir   xil   balandlikda
tokchalar   o'rnatildi.   Har   bir   tokchaga   tartib   raqami   berildi,   xonani   bir   qismining
ko‘rinishi 8.1-rasmda ifodalangan.
Kerak boisa, tokchalarni bir nechtasini qoldirib, qolganlarini yopib q o ‘yish
mumkin   edi.   Har   bir   tokchani   qulaylik   uchun   quyidagicha   nom   bilan   belgilab
olamiz: tokcha(I), tokcha(2), ..., tokcha(7), tokcha(21), ..., tokcha(1963), ... va shu
asosida   ixtiyoriy  A   tokchadagi   buyumni   tokcha(A)   orqali   belgilay   olamiz.  Ya’ni,
tokcha(A) deganda Век va Saralovchi I tokchani emas, shu tartib raqamli tokcha 
buyumni   tushunadi.   Tokchalar   sonining   quyi   chegarasi   —   INF,   yuqori
chegarasi   —   SUP   kabi   belgilanadi.   Yuqoridagi   belgilashlarga   ko‘ra   INF=1,   SUP
2 esa masala shartlarida aniqlab boriladi. Avval, tokchalarni alifbo bo‘yicha А, B, D
kabi   belgilamoqchi   boMdik.   Lekin   tokchalar   soni   ko‘payganda   harflar   ikkitalab,
uchtalab   va   shu   kabi   qo‘shib   yozilishi   anchagina   qiyinchilik   keltirib   chiqarishi
noqulaylikka sabab  boMardi. Shuning uchun tokchalar  soni  10 tadan kam bo‘lsa,
biz haflardan ham foydalanaveramiz. Ya’ni, A harfi tokcha(l) ni, В harfi tokcha (2)
ni va shu kabi tushunilaveradi. Bu ma’lumotlarning hammasi Век va Saralovchi I
ga tushunarli ekan. Yangi Ijrochimiz Saralovchi 1 sonlar ustida arifmetik amallarni
bajara   oladi   va   tekshirilayotgan   quyidagi   shartlami   ROST   yoki   YOLG‘ON
ekanligini   biladi,   ya'ni   bu   shartlarni   tekshira   oladi   hamda   shu   asosida   mantiqiy
xulosa chiqara oladi:
=   (teng),   O   (tengem   as),   <   =   (katta   emas),   >(katta).   >   =   (kichik   emas).   Sodda
dasturli  Ijrochi  Saralovchi  I ning ko‘rsatmasi  faqatbitta:  o‘tkaz tokcha(N), tokcha
(M)   Bu   amalni   bajarganda   Saralovchi   I   qoMi   bilan   tokcha   (N)   dagi   buyumni
ko‘tarib,   tokcha   (M)   ga   olib   qo‘ya   oladi.   Agar   bu   jarayonda   tokcha(M)   bo‘sh
bo‘lmasa, undagi buyumni surib tushirib yuborib, bo‘shatadi  va so‘ng tokcha (N)
dagi   buyumni   q   °‘ya   oladi.   Umuman,   buyum   qo‘yilayotgan   tokchani   bo‘sh   deb
hisoblash   mumkin,   baribir   undagi   buyumlar   tashlab   yuboriladi.   Век   faqat   shu
axborotlar   asosida   Saralovchi   1   ni   boshqarish   dastunni   tuzishi   kerak.   Bu   yerda
qiziq  bir  usulni   ko‘rish  mumkin  miqdorni  o‘zgartinb  uning  awalgi   nomini   saqlab
qoldik. Bundan qiymati o ‘zgaradigan miqdor tushunchasi paydo bo‘ladi
1.2. Saralash tushunchasi
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 ketmaketligiga qarab topshirishadi. Shu yerning o`zida 2 ta saralashdan
foydalaniladi.   Birinchisi   bo`y   uzunligi   bo`yicha,   ikkinchisi   sinf   jurnalida   alvabit
tartibida   saralanadi.   Saralash   jarayoni   qanday   kechadi?   Saralash   jarayoni
taqqoslashga   asoslangan   jarayon   hisoblanadi.   Biror   bir   ma’lumotni   saralash   yoki
3 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. Quyida saralash algoritmlarining asosiy turlarini
ko'rib   chiqiladi.   Avvalambor   saralash   algoritmi   nima   ekanligini   aniqlab   olaylik.
Saralash   algoritmlari   taqqoslash   operatorlari   yordamida   ro'yxatlar   va   massivlarda
berilgan   ma'lumotlarni   tartiblab   beradi.   Bu   operatorlar   massiv   elementlariga
qo’llaniladi   va   ularning   ma’lumotlar   strukturasidagi   tartibini   belgilaydi.   Misol
uchun, quyidagi belgilar (1-rasm) ASCII kodi bo'yicha o'sish tartibida saralangan.
Saralash   jarayonida   elementlar   bir-biri   bilan   taqqoslanadi.   ASCII   jadvalidagi
belgining qiymati qanchalik katta bo'lsa, u ro'yxat boshidan shunchalik uzoqroqda
joylashgan bo'ladi. [1] Dasturlashda turli xil saralash algoritmlar mavjud. Masalani
turi   mazmuniga   qarab   turib   saralash   algoritmlarning   biri   qo’llaniladi.   Keling   eng
ko’p qo’llaniladigan saralash algoritmlarini ko'rib chiqamiz.
1.3.   Birlashtirish saralash
Birlashtirish saralash   – massivni kichikroq kichik massivlarga bo‘lish, har
bir   kichik   massivni   saralash   va   so‘ng   saralangan   pastki   massivlarni   birlashtirib,
yakuniy tartiblangan massivni hosil qilish orqali ishlaydigan tartiblash algoritmi.
Oddiy qilib aytganda, birlashtirish tartiblash jarayoni massivni ikki yarmiga
bo'lish,   har   bir   yarmini   tartiblash   va   keyin   tartiblangan   yarmini   yana
birlashtirishdir.   Bu jarayon butun massiv saralanmaguncha takrorlanadi.
Sizni   qiziqtirgan   narsa   bu   algoritmning   o'ziga   xosligi   nimada.   Bizda
allaqachon   bir   qator   tartiblash   algoritmlari   bor,   nega   bizga   bu   algoritm
kerak?   Birlashtirishning   asosiy   afzalliklaridan   biri   shundaki,   u   vaqt   murakkabligi
O(n  log n)ga  ega, ya’ni   u katta  massivlarni   nisbatan  tez  saralay  oladi.   Bu  turg'un
tartibdir,   ya'ni   tartiblash   jarayonida   teng   qiymatli   elementlarning   tartibi   saqlanib
qoladi.
4 Birlashtirish saralash katta ma'lumotlar to'plamlarini saralash uchun mashhur
tanlovdir,   chunki   u   nisbatan   samarali   va   amalga  oshirish   oson.   U  tez-tez   saralash
tartibining   umumiy   ish   faoliyatini   yaxshilash   uchun   tez   saralash   kabi   boshqa
algoritmlar bilan birgalikda ishlatiladi.
1.3.Birlashtirish saralash ish jarayoni:
Buni rekursiv algoritm sifatida tasavvur qiling-a, massivni keyingi bo'linib 
bo'lmaguncha doimiy ravishda yarmiga bo'ladi.   Bu shuni anglatadiki, agar massiv
bo'sh bo'lib qolsa yoki faqat bitta element qolsa, bo'linish to'xtaydi, ya'ni bu 
rekursiyani to'xtatish uchun asosiy holatdir.   Agar massiv bir nechta elementga 
ega bo'lsa, massivni ikkiga bo'ling va har bir yarmida birlashma tartibini rekursiv 
ravishda chaqiring.   Nihoyat, ikkala yarmi tartiblanganda, birlashtirish 
operatsiyasi qo'llaniladi.   Birlashtirish operatsiyasi - bu ikkita kichikroq 
tartiblangan massivlarni olish va ularni kattaroq qilish uchun birlashtirish 
jarayoni.
II Bob. Ko’p oqimli birlashtirish saralash algoritimini ishlab
chiqish.
2.1. Birlashtirib saralash algoritmi.
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 yechimlari birlashtirilib, asl muammoning echimi olinadi.
2.2. “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
5 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.
“Birlashtirish bosqichi”.
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
2.3. Merge Sort algoritmining ishlash prinsipi
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.  Unda amallar tartibi ham ko'rsatib qo'yilgan
6 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
7 8 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.
13-rasmda   ko rsatilgandek,   birlashtirib   saralash   algoritmi   1   elementliʻ
massivning   asosiy   holatiga   kelgunimizcha   massivni   rekursiv   ravishda   ikkiga
bo ladi.   So ngra   birlashtirish   funksiyasi   saralangan   ichki   massivlarni   tanlaydi   va	
ʻ ʻ
butun qatorni asta-sekin saralash uchun ularni birlashtiradi.
9 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. 	
ʻ
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.	
ʻ ʻ ʻ ʻ
#include 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; 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]; 
10 i++; 
}
 else { 
Array[k] = R[j]; 
j++;
 }
 k++;
 }
// Agar mavjud bo lsa, R [] ning ʻ
//qolgan elementlarini nusxalash 
while (j < n2) { 
Array[k] = R[j];
 j++; 
k++; 
} 
}
// l chap indeks uchun, 
//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) 
{ 
11 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; 
}
12 #include <iostream>
using namespace std;
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays
int L[n1], R[n2];
// Copy data to temp arrays L[] and R[]
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// Merge the temp arrays back into arr[l..r]
// Initial index of first subarray
int i = 0;
// Initial index of second subarray
int j = 0;
// Initial index of merged subarray
13 int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of
// L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of
// R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
14 }
// l is for left index and r is
// right index of the sub-array
// of arr to be sorted */
void mergeSort(int arr[],int l,int r){
if(l>=r){
return;//returns recursively
}
int m =l+ (r-l)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
// UTILITY FUNCTIONS
// Function to print an array
void printArray(int A[], int size)
{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
}
// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
15 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;
}
2.4.Merge sort algoritmi qadamlari.
Merge   Sort   funksiyasiga   array   va   uning   boshlang'ich   ( left )   va   oxirgi
nuqtalari ( right ) beriladi.
Arraynining   o'rtasi   hisoblanadi:   mid   =   (left   +   right)/2.   Bu   narsa   uni   teng
ikkiga bo'lish uchun kerak bo'ladi.
Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi.
16 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.
2.5.Birlashtirib saralash algortimini baholash.
Algoritmning murakkabligini taxmin qilaylik. Har qanday rekursiv funksiya
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   funksiya   chaqiruvlarini   aks   ettiradi.   Shoxlari
bo lmagan   daraxt   tugunlari   rekursiyani   tugatadigan   funksiya   chaqiruvlarini
ʻ
anglatadi. Birlashtirish tartibida daraxtning balandligi log2n 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 logn marta, ya‘ni daraxtning har bir darajasi
uchun   1   marta   takrorlashni   talab   qiladi.   Keyin   algortim   asimptotikasi   O   (nlogn)
bo ladi.	
ʻ
17 18 XULOSA
Birlashtirib saralash algoritimi bu boshqa algoritmlarga qaraganda kuchliroq
algoritm.   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. 	
ʻ
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 kerak ekan.	
ʻ ʻ
19 ADABIYOTLAR RO’YXATI
1.  Misty   E   Vermaat,   Susan   L   Sebok,   Steven   M   Freund.   Discovering   Computers
(C)2016 (2016 edition). Textbook.USA, 2016.
2.  Mamarajabov M., Tursunov S. Kompyuter grafikasi va Web dizayn: Darslik.  T.:
Cho‘lpon, 2013.
3.  A . A .   Xoidjigitov   ,     Sh . f . Madraximov ,   U . E . Adamboyev     “ Informatika     va
programmalash   ” . O ` quv    qo ` llanma ,  O ` z . MU  .  2005-yil.
4.  B. Straustrop. “Yazik  programmirovaniya  C++. ” Binom  press, 2006-yil.
5.  https://library.ziyonet.uz/uz/book/126181   
https://library.ziyonet.uz/uz/book/index?Book%5Blevel_id%5D=&Book
%5Btype_id%5D=1&Book%5Bcategory_id%5D=53&Book%5Btitle
%5D=&Book%5Bdescription%5D=&Book%5Blanguage_id%5D=&yt0=Qidiruv
20 ILOVALAR
ILOVA 1. Modul N1 boshlang’ich kod.  
#include 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; 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++;
21  }
 k++;
 }
// Agar mavjud bo lsa, R [] ning ʻ
//qolgan elementlarini nusxalash 
while (j < n2) { 
Array[k] = R[j];
 j++; 
k++; 
} 
}
// l chap indeks uchun, 
//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 }; 
22 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; 
}
23

Ko’p oqimli birlashtirish saralash algoritimi I Bob. Ko’p oqimli birlashtirib saralashning nazariy qismi. ........................... 2 1.2. Saralash tushunchasi ................................................................................. 3 1.3.Birlashtirish saralash ish jarayoni: ............................................................ 5 ADABIYOTLAR RO’YXATI ...................................................................... 20 ILOVA 1. Modul N1 boshlang’ich kod. ....................................................... 21

KIRISH Saralash algoritmlari hozirgi kunda hayotimizda juda ko’p qo’llaniladi. 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 ketmaketligiga qarab topshirishadi. Shu yerning o`zida 2 ta saralashdan foydalaniladi. Birinchisi bo`y uzunligi bo`yicha, ikkinchisi sinf jurnalida alvabit 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. 1

I Bob. Ko’p oqimli birlashtirib saralashning nazariy qismi. 1.1. Saralash tarixi Uch kishini bir necha yillardan buyon uzoq kosmosda olis sayyoralar tomon olib ketayotgan kosmik kema g‘alati oltinrang bulut orasidan uchib o‘tdi. Kemada tug‘ilgan va bir yosh bo‘lgan Век ismli bola hali yurishni o‘rganmagani uchun g‘ildirakli aravachasida katta doira shaklidagi xonasida bir o‘zi aylanib yurishni yoqtirardi. U aravachasini g‘ildiratib borib o‘yinchoqlarini egilib olar, o‘ynab yana otib yuborar edi. Век oltinrang bulut ta‘sirida o‘zida bir necha xil o‘zgarishlami sezdi. Birinchi o‘zgarish zehni bilan bog‘liq bo‘lib, u endi bola bo‘lsa ham arifmetik amaUarni juda tez bajarar, har xil narsalarni turli ko‘rinishdagi miqdorini bir qarashda juda tez aniqlab, taqqoslay olardi. Ikkinchisi, u tajanglashganligi va endi bolalar o‘yinchoqlarini o‘ynagisi kelmay qolganligi edi. Xonada bir o‘zi zerikib qolganligidan chinqirib yig‘lay boshladi. 0 ‘g‘lini ovutishga kelgan ota-ona bolani qunt bilan ota-onasining suhbatini tinglayotganiga e’tibor berishdi. 0 ‘g'lidagi o‘zgarish]arni sezgach, zehni o‘tkir o‘g‘lini ovutish uchun ota-onasi xonani boshqacha jihozlab, faqat bir qo‘li bor hamda g'ildirakda yiiradigan sodda dasturli Saralovchi I nomli robot yasab berishdi. Keyin robotni boshqarishga mo‘Ijallangan dastur tuzishga yo‘naltirilgan turli boshqotirmali masalalami ayta boshlashdi. Biz endi Век bilan birga shu masalalarni ko’rib chiqamiz. Avval xona haqida. Aytganimizdek, doira shakJidagi devorlari bo‘ylab bir xil balandlikda tokchalar o'rnatildi. Har bir tokchaga tartib raqami berildi, xonani bir qismining ko‘rinishi 8.1-rasmda ifodalangan. Kerak boisa, tokchalarni bir nechtasini qoldirib, qolganlarini yopib q o ‘yish mumkin edi. Har bir tokchani qulaylik uchun quyidagicha nom bilan belgilab olamiz: tokcha(I), tokcha(2), ..., tokcha(7), tokcha(21), ..., tokcha(1963), ... va shu asosida ixtiyoriy A tokchadagi buyumni tokcha(A) orqali belgilay olamiz. Ya’ni, tokcha(A) deganda Век va Saralovchi I tokchani emas, shu tartib raqamli tokcha buyumni tushunadi. Tokchalar sonining quyi chegarasi — INF, yuqori chegarasi — SUP kabi belgilanadi. Yuqoridagi belgilashlarga ko‘ra INF=1, SUP 2

esa masala shartlarida aniqlab boriladi. Avval, tokchalarni alifbo bo‘yicha А, B, D kabi belgilamoqchi boMdik. Lekin tokchalar soni ko‘payganda harflar ikkitalab, uchtalab va shu kabi qo‘shib yozilishi anchagina qiyinchilik keltirib chiqarishi noqulaylikka sabab boMardi. Shuning uchun tokchalar soni 10 tadan kam bo‘lsa, biz haflardan ham foydalanaveramiz. Ya’ni, A harfi tokcha(l) ni, В harfi tokcha (2) ni va shu kabi tushunilaveradi. Bu ma’lumotlarning hammasi Век va Saralovchi I ga tushunarli ekan. Yangi Ijrochimiz Saralovchi 1 sonlar ustida arifmetik amallarni bajara oladi va tekshirilayotgan quyidagi shartlami ROST yoki YOLG‘ON ekanligini biladi, ya'ni bu shartlarni tekshira oladi hamda shu asosida mantiqiy xulosa chiqara oladi: = (teng), O (tengem as), < = (katta emas), >(katta). > = (kichik emas). Sodda dasturli Ijrochi Saralovchi I ning ko‘rsatmasi faqatbitta: o‘tkaz tokcha(N), tokcha (M) Bu amalni bajarganda Saralovchi I qoMi bilan tokcha (N) dagi buyumni ko‘tarib, tokcha (M) ga olib qo‘ya oladi. Agar bu jarayonda tokcha(M) bo‘sh bo‘lmasa, undagi buyumni surib tushirib yuborib, bo‘shatadi va so‘ng tokcha (N) dagi buyumni q °‘ya oladi. Umuman, buyum qo‘yilayotgan tokchani bo‘sh deb hisoblash mumkin, baribir undagi buyumlar tashlab yuboriladi. Век faqat shu axborotlar asosida Saralovchi 1 ni boshqarish dastunni tuzishi kerak. Bu yerda qiziq bir usulni ko‘rish mumkin miqdorni o‘zgartinb uning awalgi nomini saqlab qoldik. Bundan qiymati o ‘zgaradigan miqdor tushunchasi paydo bo‘ladi 1.2. Saralash tushunchasi 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 ketmaketligiga qarab topshirishadi. Shu yerning o`zida 2 ta saralashdan foydalaniladi. Birinchisi bo`y uzunligi bo`yicha, ikkinchisi sinf jurnalida alvabit tartibida saralanadi. Saralash jarayoni qanday kechadi? Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Biror bir ma’lumotni saralash yoki 3

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. Quyida saralash algoritmlarining asosiy turlarini ko'rib chiqiladi. Avvalambor saralash algoritmi nima ekanligini aniqlab olaylik. Saralash algoritmlari taqqoslash operatorlari yordamida ro'yxatlar va massivlarda berilgan ma'lumotlarni tartiblab beradi. Bu operatorlar massiv elementlariga qo’llaniladi va ularning ma’lumotlar strukturasidagi tartibini belgilaydi. Misol uchun, quyidagi belgilar (1-rasm) ASCII kodi bo'yicha o'sish tartibida saralangan. Saralash jarayonida elementlar bir-biri bilan taqqoslanadi. ASCII jadvalidagi belgining qiymati qanchalik katta bo'lsa, u ro'yxat boshidan shunchalik uzoqroqda joylashgan bo'ladi. [1] Dasturlashda turli xil saralash algoritmlar mavjud. Masalani turi mazmuniga qarab turib saralash algoritmlarning biri qo’llaniladi. Keling eng ko’p qo’llaniladigan saralash algoritmlarini ko'rib chiqamiz. 1.3. Birlashtirish saralash Birlashtirish saralash – massivni kichikroq kichik massivlarga bo‘lish, har bir kichik massivni saralash va so‘ng saralangan pastki massivlarni birlashtirib, yakuniy tartiblangan massivni hosil qilish orqali ishlaydigan tartiblash algoritmi. Oddiy qilib aytganda, birlashtirish tartiblash jarayoni massivni ikki yarmiga bo'lish, har bir yarmini tartiblash va keyin tartiblangan yarmini yana birlashtirishdir. Bu jarayon butun massiv saralanmaguncha takrorlanadi. Sizni qiziqtirgan narsa bu algoritmning o'ziga xosligi nimada. Bizda allaqachon bir qator tartiblash algoritmlari bor, nega bizga bu algoritm kerak? Birlashtirishning asosiy afzalliklaridan biri shundaki, u vaqt murakkabligi O(n log n)ga ega, ya’ni u katta massivlarni nisbatan tez saralay oladi. Bu turg'un tartibdir, ya'ni tartiblash jarayonida teng qiymatli elementlarning tartibi saqlanib qoladi. 4