GIDForums  

Go Back   GIDForums > Computer Programming Forums > C Programming Language
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read
 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 03-Oct-2015, 11:57
b15026649 b15026649 is offline
New Member
 
Join Date: Oct 2015
Posts: 1
b15026649 is on a distinguished road
Thumbs down

Can you help explain this Merge sort code to me please ?


I'm new at programming so please bare with me. I understand the concept of the Merge sort, we're sorting an array by dividing it, using an other array. but what I dont get is the MergeSort function and what those instructions do exactly. Can you explain the steps in plain English for me please ?
Thank you


CPP / C++ / C Code:
void partition(int arr[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }
   
    for(k=low;k<=high;k++){
         arr[k]=temp[k];
    }
}
  #2  
Old 07-Oct-2015, 09:59
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,160
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Can you help explain this Merge sort code to me please ?


In a nutshell...
The function named partition() is called recursively to subdivide the original array into subarrays with one element each and then recombine the subarrays back into the original array in sorted order.

Now...
You could instrument the code by placing print statements at strategic places in the functions to show values of the arguments and contents of the original array and the temp array at each step.

Then create a main() function something like
CPP / C++ / C Code:
#include <stdio.h>

void partition(int arr[], int low, int high);
void mergeSort(int arr[], int low, int mid, int high);

#define SIZE 5
#define MAX SIZE

int main()
{
    int i;
    int original[SIZE] = {1, -2, 5, 4, 3};
    printf("Original   : ");
    for (i = 0; i < SIZE; i++) {
        printf(" %d", original[i]);
    }
    printf("\n");

    partition(original, 0, SIZE);

    printf("After sort: ");
    for (i = 0; i < SIZE; i++) {
        printf(" %d", original[i]);
    }
    printf("\n");

    return 0;
}

/* Code for the two functions goes here. */


Output could look something like

Original : 1 -2 5 4 3
.
. Results of print statements sprinkled throughout the functions.
.
After sort: -2 1 3 4 5



On the other hand...
Considering that some books devote an entire chapter to the topic, maybe instead of having someone try to figure out how to help you see how to drill down to the bottom of the code, it would be better to get code from a place that also offers some explanation. Maybe even some comments in the code itself.

For example Wikipedia - Merge sort. The first example, Top-down Implementation, has code that is similar to the code in your post.


Regards,

Dave
__________________
Sometimes I just can't help myself...
 


Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Cheapest Comodo Code Signing Certificate at $70/yr from CheapSSLSecurity sslsecurity Webmaster / Web Designing Advertisements & Offers 0 12-Sep-2013 05:37
Merge sort on a linked list Temujin_12 C++ Forum 1 06-Mar-2008 21:33
Could Someone Please Explain This Code To Me HelpMePlease C Programming Language 3 26-May-2004 22:46
can someone explain this code (Pointers and addresses) tommy69 C Programming Language 1 10-Mar-2004 17:57
Explain code in MS STL's binary_search rom C++ Forum 11 07-Mar-2004 21:11

Network Sites: GIDNetwork · GIDApp · GIDBlog · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 03:19.


vBulletin, Copyright © 2000 - 2017, Jelsoft Enterprises Ltd.