C++Builder Easily Learn To Use Merge Sort Algorithm In C++ On Windows

FireWind

Свой
Регистрация
2 Дек 2005
Сообщения
1,957
Реакции
1,199
Credits
4,009
Easily Learn To Use Merge Sort Algorithm In C++ On Windows
February 26, 2021 By Yilmaz Yoru

Для просмотра ссылки Войди или Зарегистрируйся Algorithm, in another efficient sorting algorithm that divides the input array into two parts and it calls itself recursively for the two parts. Then merges these two sorted parts. It is a Divide and Conquer algorithm. Merge function used to merge two parts of array. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

Merging algorithm function runs by array with left, mid and right indexes, it should be be as given below:
C++:
void my_merge(int array[], int l, int m, int r)
{
 int i, j, k, n1 = m-l+1, n2 = r-m, L[n1], R[n2];
 for (i = 0; i < n1; i++) L[i] = array[l + i];      // Copy to Left temp
 for (j = 0; j < n2; j++) R[j] = array[m + 1 + j];  // Copy to Right temp
 
 i = 0; j = 0; k = l;
 while (i < n1 && j < n2)
 {
 if (L[i] <= R[j]) { array[k] = L[i];  i++; } else { array[k] = R[j]; j++; }
 k++;
 }
 // Let's copy the final sorted elements of Left & Right
 while (i < n1) { array[k] = L[i]; i++; k++; }
 while (j < n2) { array[k] = R[j]; j++; k++; }
}
and my_mergesort() functions runs by array, start and end indexes as below:
C++:
void my_mergesort(int array[], int start, int end)
{
 if (start < end)
 {
 int mid = start + (end - start) / 2;
 my_mergesort(array, start, mid);
 my_mergesort(array, mid + 1, end);
 my_merge(array, start, mid, end);
 }
}
Full code of Merge Sort Algorithm will be as below in C++ Builder Console VCL application.
C++:
#include <vcl.h>
#include <tchar.h>
#include <stdio.h>
#include <windows.h>
 
#pragma hdrstop
#pragma argsused
 
void my_merge(int array[], int l, int m, int r)
{
 int i, j, k, n1 = m-l+1, n2 = r-m, L[n1], R[n2];
 for (i = 0; i < n1; i++) L[i] = array[l + i];      // Copy to Left temp
 for (j = 0; j < n2; j++) R[j] = array[m + 1 + j];  // Copy to Right temp
 
 i = 0; j = 0; k = l;
 while (i < n1 && j < n2)
 {
 if (L[i] <= R[j]) { array[k] = L[i];  i++; } else { array[k] = R[j]; j++; }
 k++;
 }
 // Let's copy the final sorted elements of Left & Right
 while (i < n1) { array[k] = L[i]; i++; k++; }
 while (j < n2) { array[k] = R[j]; j++; k++; }
}
 
void my_mergesort(int array[], int start, int end)
{
 if (start < end)
 {
 int mid = start + (end - start) / 2;
 my_mergesort(array, start, mid);
 my_mergesort(array, mid + 1, end);
 my_merge(array, start, mid, end);
 }
}
 
int _tmain(int argc, _TCHAR* argv[])
{
 int i,n=5, mat[5] = { 3, 30, 34, 5, 9 };
 my_mergesort( mat, 0, n-1);
 for (i=0; i<n; i++) printf ("%d,",mat[i]);
 getchar();
 return 0;
}