-
-
Save mycodeschool/9678029 to your computer and use it in GitHub Desktop.
| /* Merge sort in C */ | |
| #include<stdio.h> | |
| #include<stdlib.h> | |
| // Function to Merge Arrays L and R into A. | |
| // lefCount = number of elements in L | |
| // rightCount = number of elements in R. | |
| void Merge(int *A,int *L,int leftCount,int *R,int rightCount) { | |
| int i,j,k; | |
| // i - to mark the index of left aubarray (L) | |
| // j - to mark the index of right sub-raay (R) | |
| // k - to mark the index of merged subarray (A) | |
| i = 0; j = 0; k =0; | |
| while(i<leftCount && j< rightCount) { | |
| if(L[i] < R[j]) A[k++] = L[i++]; | |
| else A[k++] = R[j++]; | |
| } | |
| while(i < leftCount) A[k++] = L[i++]; | |
| while(j < rightCount) A[k++] = R[j++]; | |
| } | |
| // Recursive function to sort an array of integers. | |
| void MergeSort(int *A,int n) { | |
| int mid,i, *L, *R; | |
| if(n < 2) return; // base condition. If the array has less than two element, do nothing. | |
| mid = n/2; // find the mid index. | |
| // create left and right subarrays | |
| // mid elements (from index 0 till mid-1) should be part of left sub-array | |
| // and (n-mid) elements (from mid to n-1) will be part of right sub-array | |
| L = (int*)malloc(mid*sizeof(int)); | |
| R = (int*)malloc((n- mid)*sizeof(int)); | |
| for(i = 0;i<mid;i++) L[i] = A[i]; // creating left subarray | |
| for(i = mid;i<n;i++) R[i-mid] = A[i]; // creating right subarray | |
| MergeSort(L,mid); // sorting the left subarray | |
| MergeSort(R,n-mid); // sorting the right subarray | |
| Merge(A,L,mid,R,n-mid); // Merging L and R into A as sorted list. | |
| free(L); | |
| free(R); | |
| } | |
| int main() { | |
| /* Code to test the MergeSort function. */ | |
| int A[] = {6,2,3,1,9,10,15,13,12,17}; // creating an array of integers. | |
| int i,numberOfElements; | |
| // finding number of elements in array as size of complete array in bytes divided by size of integer in bytes. | |
| // This won't work if array is passed to the function because array | |
| // is always passed by reference through a pointer. So sizeOf function will give size of pointer and not the array. | |
| // Watch this video to understand this concept - http://www.youtube.com/watch?v=CpjVucvAc3g | |
| numberOfElements = sizeof(A)/sizeof(A[0]); | |
| // Calling merge sort to sort the array. | |
| MergeSort(A,numberOfElements); | |
| //printing all elements in the array once its sorted. | |
| for(i = 0;i < numberOfElements;i++) printf("%d ",A[i]); | |
| return 0; | |
| } |
Dynamic memory is used to so that we can de-allocate (free) the left and the right sub-array memory space once the process completes. A good programming practice indeed.
void merge(int a[], int low, int mid, int high)
{
int b[10000];
int i = low, j = mid + 1, k = low;while (i <= mid && j <= high) { if (a[i] <= a[j]) b[k++] = a[i++]; else b[k++] = a[j++]; } while (i <= mid) b[k++] = a[i++]; while (j <= high) b[k++] = a[j++]; for(i=low;i<=high;i++) a[i]=b[i]; }}
void mergesort(int a[], int low, int high)
{
if (low < high) {
int m = (high + low)/2;
mergesort(a, low, m);
mergesort(a, m + 1, high);
merge(a, low, m, high);
}
}
why are we not implementing this code?
Following issues with the above mentioned method -
- What if the array size if more than 10000 ?
- There can be lot of empty cells in array 'b[]', and wastage of memory is costly !
- What happens to array 'b[]' when the merge() finishes execution for the last time ? After that we don't need the array 'b[]' again, as the elements are in sorted order in array 'a[]', right ? See, we need to free the memory allocated to array 'b[]', which is not done here. :(
Java Implementation of the Merge Sort!
public class MergeSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = {2,10,7,5,1,3,0,11};
mergeSort(arr);
for(int i : arr) {
System.out.print(i+" ");
}
}
static void mergeSort(int A[]) {
int n = A.length;
int mid = n/2;
if(n<2) {
return ;
}
int left[] = new int[mid];
int right[] = new int[n-mid];
for(int i = 0 ; i < mid ; i++) {
left[i] = A[i];
}
for(int i = mid ; i < n ; i++) {
right[i-mid] = A[i];
}
mergeSort(left);
mergeSort(right);
merge(left,right,A);
}
// this merges the sorted left and right array into one array;
static void merge(int left[],int right[], int arr[]){
int l = 0;
int r = 0;
int k = 0;
while(l < left.length && r < right.length) {
if(left[l] <= right[r]) {
arr[k] = left[l];
l++;
}else{
arr[k] = right[r];
r++;
}
k++;
}//end of while
while(l<left.length) {
arr[k] = left[l];
k++;
l++;
}
while(r<right.length) {
arr[k] = right[r];
k++;
r++;
}
}
}// end of class
why are we taking arrays as pointers?
// c++code!
#include
using namespace std;
void mergearrays(int A, int Left,int leftcount, int* Right, int rightcount){
int i,ii,jj;
i=0;ii=0;jj=0;
while(i< leftcount+rightcount){
if(ii == leftcount) A[i++] = Right[jj++];
else if(jj == rightcount) A[i++] = Left[ii++];
else{
A[i++] = (Right[jj] > Left[ii]) ? Left[ii++]: Right[jj++];
}
}
}
void mergeSort(int* A, int n){
int mid = n/2;
if(n<2)return;
int* Left= new int[mid];
int* Right= new int[n-mid];
for(int i=0;i<mid;i++)Left[i] = A[i];
for(int i=mid;i<n;i++)Right[i-mid] = A[i];
mergeSort(Left, mid );
mergeSort(Right, n-mid);
mergearrays(A, Left, mid, Right, n-mid);
delete(Left);
delete(Right);
}
int main() {
cout << "Hello World!\n";
int A[]={1,3,4,24,6,7};
int sizel= sizeof(A)/sizeof(A[0]);
mergeSort(A, sizel);
for( int p=0;p<sizel;p++) cout<< A[p]<< endl;
}
Java Code
public class MergeSort {
public static void main(String args[]) {
int[] a = {100,9,7,4,3,1,11,89,65,43,05,54,21,0,};
a=ms(a);
for(int x : a) {
System.out.print(x+" ");
}
}
private static int[] ms(int[] a) {
int n = a.length;
if(n<2) {
return a;
}
else {
int mid = n/2;
int[] l = new int[mid];
int[] r = new int[n-mid];
for(int i=0;i<mid;i++) {
l[i]=a[i];
}
for(int i=mid;i<n;i++) {
r[i-mid]=a[i];
}
ms(l);
ms(r);
merge(l,r,a);
return a;
}
}
private static void merge(int[] l, int[] r, int[] a) {
int nl = l.length;
int nr = r.length;
int i =0,j=0,k=0;
while(i<nl && j<nr) {
if(l[i]<=r[j]) {
a[k]=l[i];
i++;
}
else {
a[k]=r[j];
j++;
}
k++;
}
while(i<nl) {
a[k]=l[i];
k++;i++;
}
while(j<nr) {
a[k]=r[j];
k++;j++;
}
}
}
Java Code!
public class Test {
public static void main(String[] args) {
int[] arr = {6,2,3,1,9,10,15,13,12,17};
Test.sort(arr);
for (int i : arr){
System.out.print(i+ " ");
}
}
public static void Merge(int[] left, int[] right, int[] arr){
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length){
if (left[i] < right[j]){
arr[k] = left[i];
i++;
}
else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < left.length){
arr[k] = left[i];
k++; i++;
}
while (j < right.length){
arr[k] = right[j];
k++; j++;
}
}
public static void sort(int[] arr){
int n = arr.length;
if(n < 2) return;
int mid = n/2;
int[] left = Arrays.copyOfRange(arr,0, mid);
int[] right = Arrays.copyOfRange(arr, mid, n);
sort(left);
sort(right);
Merge(left, right, arr);
}
}
Thank you so much, sir.
Thanks alot sir, best explanation on internet.
Python implementation, did variables with much wordings for a simpler follow-along,
def mergeSort(array):
arrayLength = len(array)
if arrayLength<2:
return
#cmpute array mid-point
mid = arrayLength//2
# create two lists/array and initialize with default values
leftArray= list(range(mid))
rightArray= list(range(arrayLength-mid))
# populate the two arrays with values from original array/list
for idx in range(mid):
leftArray[idx] = array[idx]
for idx in range(mid, arrayLength):
rightArray[idx-mid] = array[idx]
# call a mergeSort method recursively until the base case of len <2 is reached
# means one element is remaining in a given list
mergeSort(leftArray)
mergeSort(rightArray)
#then start merging picking left and right array from call stack
merge(leftArray,rightArray,array)
# meged array
return array
def merge(leftArray,rightArray,array):
leftArrayLength = len(leftArray)
rightArrayLength = len(rightArray)
leftIdx=rightIdx=arrayIdx=0
# loop until the len of either array
while(leftIdx < leftArrayLength and rightIdx < rightArrayLength):
if leftArray[leftIdx] <= rightArray[rightIdx]:
array[arrayIdx] = leftArray[leftIdx]
leftIdx +=1
else:
array[arrayIdx] = rightArray[rightIdx]
rightIdx +=1
arrayIdx +=1
# case when right array is exhausted before the left one
while leftIdx < leftArrayLength:
array[arrayIdx] = leftArray[leftIdx]
leftIdx +=1
arrayIdx +=1
# case when left array is exhausted before the left one
while rightIdx < rightArrayLength:
array[arrayIdx] = rightArray[rightIdx]
rightIdx +=1
arrayIdx +=1
# tests
testArray =[6,2,3,1,9,10,15,13,12,17]
expected = [1, 2, 3, 6, 9, 10, 12, 13, 15, 17]
assert mergeSort(testArray) == expected
Merge sort in java
`class mergeSortAlgorithms{
public void merge(int arr[], int start , int mid , int end){
//find the size of right and left halves
int n1 = mid - start +1;
int n2 = end - mid;
//make the temporary array equal to right and left halve
int left[] = new int[n1];
int right[] = new int[n2];
//fill the right and left halves
for(int i=0;i<n1;i++){
left[i] = arr[i+start];
}
for(int j=0;j<n2;j++){
right[j] = arr[mid+1+j];
}
//intialize variable
int i = 0 ,j=0, k = start;
//sort the array
while(i<n1 && j <n2){
if(left[i] < right[j]){
arr[k] = left[i];
i++;
}
else{
arr[k] = right[j];
j++;
}
k++;
}
//copying the reamaining value of right and left halves
while(i<n1){
arr[k] =left[i];
i++;
k++;
}
while(j<n2){
arr[k] = right[j];
j++;
k++;
}
}
public void mergeSort(int arr[], int start ,int end){
//check if start greater than end
if(start < end){
int mid = (start+end)/2;
//divide into two halves recursively
mergeSort(arr,start,mid);
mergeSort(arr,mid+1,end);
//merge into two halves
merge(arr,start,mid,end);
}
}
public static void main(String[] args) {
//random array
int arr[] = {25,20,4,24};
//object of same class
mergeSortAlgorithms array = new mergeSortAlgorithms();
//call the mergesort function
array.mergeSort(arr,0,arr.length-1);
//display sorted array
for (int i=0;i<arr.length ;i++ ) {
System.out.println(arr[i]);
}
}
}
`
To compile and run online same program : click on this link :
https://debuggingsolution.blogspot.com/2021/09/mergesort.html
To see code :
https://debuggingsolution.blogspot.com/2021/09/mergesort.html
i did the array split in 1 loop
for(i = 0;i<mid;i++){
L[i] = A[i];
R[i] = A[mid+i];
}
if(n%2)R[i] = A[mid+i];
I had implemented the Merge sort class for the divide and conquer method. The main method is written different.
public class divideandconquer {
//Implement the sorting algorithm Merge Sort, which you will have to use in the
//algorithm for solving Closest-Points. (25%)
//**************
//Not implemented the sort() function. Instead of that
//Merge sort class
class Merge{
private static int k;
static void mergeSort(ArrayList A, int start, int end) {
//check condition if start greater than end
if(start < end) {
//using a formula
int mid = (start + (end-1)) / 2;
//Now we divide into two valves for multiple times
mergeSort(A, start, mid);
mergeSort(A, mid+1, end);
//merge into two valves
merge(A, start, mid, end);
}
}
public static void merge(ArrayList A, int startpoint, int midpoint, int endpoint ) {
//Calculate the size of left and right halves
int lefthalve = midpoint - startpoint + 1 ;
int righthvalve = endpoint - midpoint ;
//create a temporary sub-arrays and assigned to calculated left halves
int [] left = new int[lefthalve];
//create a temporary sub-arrays and assigned to calculated right halves
int [] right = new int [righthvalve];
//We fill our sorted right sub-arrays into temporaries
for (int leftIndex = 0; leftIndex < lefthalve; ++leftIndex) {
left[leftIndex] = A.get(startpoint+leftIndex);
}
//We fill our sorted left sub-arrays into temporaries
for (int rightIndex = 0; rightIndex < righthvalve; ++rightIndex) {
right[rightIndex] = A.get(midpoint + 1 + rightIndex);
}
//Initialize the variables, iterators containing current index of temp sub-arrays
int leftIndex = 0; int rightIndex = 0; int k=startpoint;
// copying from leftArray and rightArray back into array
//for (int i = start; i < end + 1; i++) {
while(leftIndex < lefthalve && rightIndex < righthvalve) {
if(left[leftIndex]<right[rightIndex]) {
A.set(k, left[leftIndex]);
leftIndex++;
}
else {
A.set(k, right[rightIndex]);
rightIndex++;
}
k++;
}
// if all the elements have been copied from rightArray, copy the rest of leftArray
while (leftIndex < lefthalve) {
A.set(k, left[leftIndex]);
leftIndex++;
k++;
}
// if all the elements have been copied from leftArray, copy the rest of rightArray
while (rightIndex < righthvalve) {
A.set(k, right[rightIndex]);
rightIndex++;
k++;
}
}
//applying getters and setters of defined k value
public static int getK() {
return k;
}
public static void setK(int k) {
Merge.k = k;
}
}
}
thanks
https://codegcloudonline.blogspot.com/2019/12/merge-sort.html
#include<stdio.h>
int merge(int *,int ,int ,int);
void mergesort(int *,int ,int);
main()
{
int n,a[40],i,p,r;
printf("Enter total no of element in an array\n");
scanf("%d",&n);
printf("Enter total %d element in an array\n",n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("\nElement Before sorting\n");
for(i=1;i<=n;i++)
printf("%d\t",a[i]);
p=1;
mergesort(a,p,n);
printf("\nElement After sorting\n");
for(i=1;i<=n;i++)
printf("%d\t",a[i]);
}
void mergesort(int *a,int p,int r)
{
int q;
if(p<r)
{
q=(p+r)/2;
mergesort(a,p,q);
mergesort(a,q+1,r);
merge(a,p,q,r);
}
}
int merge(int *a,int p,int q,int r)
{
int n1,n2,l[30],m[30],i,j,k;
n1=q-p+1;
n2=r-q;
for(i=1;i<=n1;i++)
l[i]=a[p+i-1];
for(j=1;j<=n2;j++)
m[j]=a[q+j];
l[n1+1]=1234567897;
m[n2+1]=1234567898;
i=1;j=1;
for(k=p;k<=r;k++)
{
if(l[i]<=m[j])
{
a[k]=l[i];
i=i+1;
}
else
{
a[k]=m[j];
j=j+1;
}
}
return a;
}