4-§ Birlashtirib saralash algoritmlari Merge sort algoritmi. Birlashtirib saralash (Merge sort)

Birlashtirib saralash algoritmi uchun dastur kodi 
#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; 

---

67 
 
 
// Ikkinchi kichik massivning boshlangʻich koʻrsatkichi 
 
int j = 0; 
 
 
// Birlashtirilgan ichki massivning dastlabki koʻrsatkichi 
 
int k = l; 
 
 
while (i < n1 && j < n2) { 
 
 
if (L[i] <= R[j]) { 
 
 
 
Array[k] = L[i]; 
 
 
 
i++; 
 
 
} 
 
 
else { 
 
 
 
Array[k] = R[j]; 
 
 
 
j++; 
 
 
} 
 
 
k++; 
 
} 
 
 
// L [] ning qolgan elementlarini nusxalash, 
 
//agar mavjud boʻlsa 
 
while (i < n1) { 
 
 
Array[k] = L[i]; 
 
 
i++; 
 
 
k++; 
 
} 
 
 
// Agar mavjud boʻlsa, R [] ning 
 
//qolgan elementlarini nusxalash 
 
while (j < n2) { 
 
 
Array[k] = R[j]; 
 
 
j++; 
 
 
k++; 
 
} 
} 
 
// l chap indeks uchun, 
//r esa tartiblangan ichki massivning oʻng indeksidir 
void mergeSort(int Array[],int l,int r){ 

---

68 
 
if(l>=r){ 
 
 
return;//rekursiv ravishda qaytadi 
 
} 
 
int m =l+ (r-l)/2; 
 
mergeSort(Array,l,m); 
 
mergeSort(Array,m+1,r); 
 
merge(Array,l,m,r); 
} 
 
// Massivni chop etish funksiyasi 
void printArrayay(int A[], int size) 
{ 
 
for (int i = 0; i < size; i++) 
 
 
cout << A[i] << " "; 
} 
int main() 
{ 
 
int Array[] = { 12, 11, 13, 5, 6, 7 }; 
 
int Array_size = sizeof(Array) / sizeof(Array[0]); 
 
 
cout << "Berilgan massiv \n"; 
 
printArrayay(Array, Array_size); 
 
 
mergeSort(Array, 0, Array_size - 1); 
 
 
cout << "\n Tartiblangan massiv \n"; 
 
printArrayay(Array, Array_size); 
 
return 0; 
} 
 
14-rasm. Merge Sort algoritmi dastur natijasi 

---

69 
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 log
2
n ga teng, chunki har bir qadamda boshlangʻich massiv 
n/2 uzunlikdagi ikkita ichki massivga boʻlinadi. Ajratishdan soʻng, 
birlashtirish operatsiyasi amalga oshiriladi. Birlashtirish jarayoni n 
taqqoslashni, navbati bilan logn marta, ya‘ni daraxtning har bir darajasi 
uchun 1 marta takrorlashni talab qiladi. Keyin algortim asimptotikasi O 
(nlogn) boʻladi. 
 
15-rasm. Merge Sort algoritmining turli xil tiplar uchun ishlash 
vaqti (elementlar soni 50000 ta) 
 
Mavzu yuzasidan savollar: 
1. Merge sort algoritmining murakkabliklarini baholang 
2. Merge sort algoritmida ―Boʻlib tashlash‖da nimalarga e‘tibor 
berish kerak 

---

70