Birlashtirib saralash algoritmi uchun dastur kodi

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 
log
n 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.

Download 4,61 Mb.