Oʻzbekiston respublikasi oliy va o‘rta maxsusta’lim vazirligi




Download 29,81 Mb.
bet14/16
Sana15.11.2023
Hajmi29,81 Mb.
#99092
1   ...   8   9   10   11   12   13   14   15   16
Bog'liq
Dilshoda Algoritm mustaqil

Tasvir:


Merge sortning ishlashini bilish uchun massivni ko'rib chiqaylik
arr[] = {38, 27, 43, 3, 9, 82, 10}

  • Dastlab, massivning chap indeksi o'ng indeksdan kichik ekanligini tekshiring, agar shunday bo'lsa, uning o'rta nuqtasini hisoblang.



  • Biz allaqachon bilganimizdek, birlashma tartiblash birinchi navbatda butun massivni atom qiymatlariga erishilmasa, iterativ ravishda teng yarmiga ajratadi. 

  • Bu erda biz 7 ta elementdan iborat massiv mos ravishda 4 va 3 o'lchamli ikkita massivga bo'linganligini ko'ramiz.



  • Endi, chap indeks ikkala massiv uchun o'ng indeksdan kichik ekanligini yana toping, agar topilsa, ha, keyin ikkala massiv uchun yana o'rta nuqtalarni hisoblang.



  • Endi, massivning atom birliklariga erishilgunga qadar va keyingi bo'linish mumkin bo'lmaguncha, bu ikki massivni qo'shimcha yarmiga bo'ling.



  • Massivni eng kichik birliklarga bo'lgandan so'ng, elementlarning o'lchamlarini taqqoslash asosida elementlarni yana birlashtirishni boshlang.

  • Birinchidan, har bir ro'yxat uchun elementni solishtiring va keyin ularni tartiblangan tarzda boshqa ro'yxatga birlashtiring.



  • Yakuniy birlashtirgandan so'ng, ro'yxat quyidagicha ko'rinadi:


Quyidagi diagrammada {38, 27, 43, 3, 9, 82, 10} misol massivi uchun toʻliq Merge sort saralash jarayoni koʻrsatilgan. 
Agar diagrammaga yaqinroq nazar tashlasak, massiv o‘lchami 1 bo‘lgunga qadar rekursiv ravishda ikkiga bo‘linishini ko‘ramiz. O‘lcham 1 ga aylangandan so‘ng, birlashtirish jarayonlari ishga tushadi va massiv to‘liq bo‘lguncha massivlarni birlashtira boshlaydi. birlashtirildi.


// C# program for Merge Sort
using System;
class MergeSort {
// 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)
{
// Find sizes of two
// subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays
int[] L = new int[n1];
int[] R = new int[n2];
int i, j;

// Copy data to temp arrays
for (i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
// Merge the temp arrays
// Initial indexes of first
// and second subarrays
i = 0;
j = 0;
// Initial index of merged
// subarray array
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 remaining elements
// of L[] if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements
// of R[] if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Main function that
// sorts arr[l..r] using
// merge()
void sort(int[] arr, int l, int r)
{
if (l < r) {
// Find the middle
// point
int m = l + (r - l) / 2;

// Sort first and
// second halves
sort(arr, l, m);
sort(arr, m + 1, r);

// Merge the sorted halves
merge(arr, l, m, r);
}
}

// A utility function to
// print array of size n */
static void printArray(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n; ++i)
Console.Write(arr[i] + " ");
Console.WriteLine();
}

// Driver code
public static void Main(String[] args)
{
int[] arr = { 12, 11, 13, 5, 6, 7 };
Console.WriteLine("Given Array");
printArray(arr);
MergeSort ob = new MergeSort();
ob.sort(arr, 0, arr.Length - 1);
Console.WriteLine("\nSorted array");
printArray(arr);
}
}

Download 29,81 Mb.
1   ...   8   9   10   11   12   13   14   15   16




Download 29,81 Mb.

Bosh sahifa
Aloqalar

    Bosh sahifa



Oʻzbekiston respublikasi oliy va o‘rta maxsusta’lim vazirligi

Download 29,81 Mb.