4-Mavzu: Kvadratik, logarifmik va chiziqli qiyinchilikdagi saralash algoritmlari Shell sort

Merge sort. Merge sort algoritmi bo’lib tashla hukmronlik qil strategiyasi bo’yicha ishlaydi:

• 
  Birlashtirish bu ikkita tartiblangan fayllarni aralashtirish orqali bitta katta saralangan fayl yaratish jarayonidir.
  
• 
  Tanlash bu faylni ikkita bo’lakka bo’lish jarayoni: k ta eng kichik elementlar va n-k ta eng katta elementlar.
  
• 
  Tanlash va birlashtirish teskari amallardir:
  

Tanlash faylni ikki qismga bo’ladi
Birlashtirish ikkita faylni bitta faylga birlashtiradi

• 
  Merge sort berilganlarga ketma ket tartibda murojat qiladi.
  
• 
  Bu algoritm bog’langan ro’yxatlarni tartiblash uchun foydalaniladi.
  
• 
  Merge sort berilganlarning boshlang’ich tartibiga bog’liqmas.
  
• 
  Quicksort algoritmida asosiy ish rekursiv murojatdan oldin bajariladi. Quicksortda eng katta qismfayl bilan boshlanadi va eng kichigi bilan tugaydi. Natija stekka zarurat tug’iladi. Merge sort ro’yxatni ikki qismga bo’ladi va har bir qism alohida boshqariladi. Merge sort ishni eng kichik qismfayldan boshlaydi va eng kattasi bilan tugatadi. Natijada stekka hojat qolmaydi.
  

void MergeSort(int a[], int temp[], int left, int right){

int mid;
if (right > left){
mid = (left + right) / 2;
MergeSort(a, temp, left, mid);
MergeSort(a, temp, mid + 1, right);
Merge(a, temp, left, mid + 1, right);
}
}

void Merge(int a[], int temp[], int left, int mid, int right){

int i, left_end, size, temp_pos;
left_end = mid - 1;
temp_pos = left;
size = right - left +1;
while (left <= left_end && mid <= right){
if (a[left] <= a[mid]){
temp[temp_pos] = a[left];
temp_pos = temp_pos + 1;
left = left + 1;
}
else{
temp[temp_pos] = a[mid];
temp_pos = temp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end){
temp[temp_pos] = a[left];
left = left + 1;
temp_pos++;
}
while (mid <= right){
temp[temp_pos] = a[mid];
mid = mid + 1;
temp_pos++;
}
for (i = 0; i <= size; i++){
a[right] = temp[right];
right--;
}

}
Samaradorligi:

• 
  Eng yomon holatdagi murakkablik: O(nlogn)
  
• 
  Eng yaxshi holatdagi murakkablik: O(nlogn)
  
• 
  O’rtacha holatdagi murakkablik: O(nlogn)