MergeSort algoritmi.Algoritmning murakkabligini tahlil qilish
![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](https://docx.uz/documents/d3e079a9-fa1e-4ab2-9e52-4be3e162ed43/page_3.png?v=1)
![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](https://docx.uz/documents/d3e079a9-fa1e-4ab2-9e52-4be3e162ed43/page_4.png?v=1)
![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](https://docx.uz/documents/d3e079a9-fa1e-4ab2-9e52-4be3e162ed43/page_5.png?v=1)
![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](https://docx.uz/documents/d3e079a9-fa1e-4ab2-9e52-4be3e162ed43/page_6.png?v=1)
![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](https://docx.uz/documents/d3e079a9-fa1e-4ab2-9e52-4be3e162ed43/page_7.png?v=1)
MergeSort algoritmi.Algoritmning murakkabligini tahlil qilish