|
Oʻzbekiston respublikasi oliy va o‘rta maxsusta’lim vazirligi
|
bet | 14/16 | Sana | 15.11.2023 | Hajmi | 29,81 Mb. | | #99092 |
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);
}
}
|
| |