Solved

Asking a Iterative merge sort...... pls help

Posted on 2004-08-18
23
381 Views
Last Modified: 2010-04-01
#include<iostream.h>
#include<stdlib.h>
void mergesort(int[],int,int,int &,int &,int &);
void merge(int[],int,int,int,int &,int &,int &);
void main ()
{
      const int size=8;
      int no[size], x, y, z, data=0, compare=0, recursion=0;
      
      for (x=0; x<=size; x++)
      
      {
            no[x]=rand() % 50;
      }


      cout<<"*To start this Mergesort, PC will randomly choose the array from 0 to 50*"<<endl<<endl;;
      cout<<"Random Array Choose by PC are: "<<endl;
      
      for (y=0; y<=size; y++)
      
      {
            if (y<size)
                  cout<<no[y]<<",";
            else
                  cout<<no[y]<<endl<<endl;
      }

      
      mergesort(no,0,size,data,compare,recursion);

      cout<<"Mergesort Done: "<<endl;
      
      for (z=0; z<=size; z++)
      {
            if(z<size)
                  cout<<no[z]<<",";
            else
                  cout<<no[z]<<endl<<endl;
      }

      cout<<"Total of Data Move for this MergerSort: "<<data<<endl<<endl;
      cout<<"Total of Comparison for this MergerSort: "<<compare<<endl<<endl;
      cout<<"Total of Recursive for this MergerSort: "<<recursion<<endl<<endl;


}


const int Max_Size = 9;

void merge(int theArray[], int first, int mid, int last,int &data,int &compare, int &recursion)
{
      int tempArray[Max_Size];
      int first1=first;
      int last1=mid;
      int first2=mid+1;
      int last2=last;
      int index=first1;
      compare=compare+1;
      for(; (first1<=last1) && (first2<=last2); ++index)
      {
                        data=data+1;
            if (theArray[first1] < theArray[first2])
                  {  
                        tempArray[index] = theArray[first1];
                        ++first1;

                  }
            else
                  {  
                        tempArray[index] = theArray[first2];
                        ++first2;
                        
                  }
      }
      for (; first1<=last1; ++first1, ++index)
            tempArray[index] = theArray[first1];
      for (; first2<=last2; ++first2, ++index)
              tempArray[index] = theArray[first2];
      for (index = first; index<=last; ++index)
              theArray[index] = tempArray[index];

}

void mergesort (int theArray[], int first, int last,int &data, int &compare, int &recursion)
{
      recursion=recursion+1;
      if (first<last)
      {
            int mid = (first + last)/2;
            mergesort (theArray, first, mid,data,compare,recursion);
                  
            mergesort (theArray, mid+1, last,data,compare,recursion);

            merge (theArray, first, mid, last,data,compare,recursion);
                        

      }
}


this is my recursion merge sort source code...
can i ask....
how to i make it to iterative version for merge sort?
somebody can teach me the way ??
thanks you...
waiting reply.......
0
Comment
Question by:wcpon
  • 13
  • 9
23 Comments
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 11840383
Look at that:

void merge(int array[], int size)
{
    // need temp array to move parts in-place
    int* temparray = new int[size-1];

    int siz    = 1;            // current size of buckets to merge
    int nparts = size/2;   // number of buckets
    int f1     = 0;            // index of left bucket
    int f2     = 1;            // index of right bucket
    int l1     = 1;            // max of left bucket
    int l2     = 2;            // max of right bucket
    int n2     = 1;           // next index of right bucket
    int mv     = 0;          // positions to move

    // binary loop
    for (siz = 1; siz <= size; siz *= 2)
    {
        nparts = size/siz;  // number of buckets
        // merge pairs of buckets
        for (int n = 0; n < nparts; n+=2)
        {
            f1 = n*siz;
            f2 = f1 + siz;
            l1 = f2;
            l2 = (f2 + siz <= size)? f2 + siz : size;
            // as both buckets are sorted we are thru if either left or right bucket is done
            while (f1 < l1 && f2 < l2)
            {
                n2 = f2;
               // check number of right bucket positions to move
                while (n2 < l2 && array[f1] > array[n2])
                    n2++;
                if (n2 > f2)
                {
                    mv = (n2 - f2);
                    // copy smaller numbers of right bucket  to temp array
                    memcpy(temparray, &array[f2], mv*sizeof(int));
                    // move intermediate part to the right
                    memmove(&array[f1+mv], &array[f1], (f2 - f1)*sizeof(int));
                    // get temp data back
                    memcpy(&array[f1], temparray, mv*sizeof(int));
                    f2 = n2;
                }
                else
                    f1++;
            }
        }
    }
    delete [] temparray;
}

Regards, Alex

0
 

Author Comment

by:wcpon
ID: 11842180
is it ur source code is a iterative version ???

only change the merge function ??
why my frenz told me....
suppose to change the mergesort function... other function jz keep it as same.... ?
am i my frenz right?
or???

can you tell me ?
thanks you....
waiting your reply .... thx
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 11842320
>> only change the merge function ??

No, better rename my function merge() to mergesort1:

    void merge(int array[], int size)
-->
    void mergesort1(int array[], int size)


Use it like that:

void main()
{
   int arr[] = { 19, 21, 5, 3, 17, 34, 61, 4, 97, 1, 10, };
   mergesort1(arr, sizeof(arr)/sizeof(int));
}

Regards, Alex


0
 

Author Comment

by:wcpon
ID: 11842543
so

void mergesort (int theArray[], int first, int last,int &data, int &compare, int &recursion)
{
     recursion=recursion+1;
     if (first<last)
     {
          int mid = (first + last)/2;
          mergesort (theArray, first, mid,data,compare,recursion);
               
          mergesort (theArray, mid+1, last,data,compare,recursion);

          merge (theArray, first, mid, last,data,compare,recursion);
                   

     }
}


this one remain the same is it??? no change?
thanks you ..
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 11842788
recursive mergesort has two functions:

   void mergesort (int theArray[], int first, int last,int &data, int &compare, int &recursion);
   void merge(int theArray[], int first, int mid, int last,int &data,int &compare, int &recursion);


iterative mergesort has one function:

   void mergesort1(int array[], int size);


I made a test  where  mergesort1 didn't sort correctly. I'll fix it and post you the final solution.

Regards, Alex





0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 11842961
Ok, i found the bug: i had to increase f1 and l1 after moving...

void show(int a[], int siz)
{
   for (int i = 0; i < siz -7; i+= 8 )
   {
       cout << a[i] << ' ' << a[i+1] << ' '  << a[i+2] << ' '  << a[i+3] << ' '  
            << a[i+4] << ' ' << a[i+5] << ' '  << a[i+6] << ' '   << a[i+7] << endl;
   }

   cin >> i;
}

void mergesort1(int array[], int size)
{
    int* temparray = new int[size/2 + 1];

    int siz    = 1;
    int nparts = size/2;
    int f1     = 0;
    int f2     = 1;
    int l1     = 1;
    int l2     = 2;
    int n2     = 1;
    int mv     = 0;

    for (siz = 1; siz <= size; siz *= 2)
    {
        nparts = size/siz;
        for (int n = 0; n < nparts; n+=2)
        {
            f1 = n*siz;
            f2 = f1 + siz;
            l1 = f2;
            l2 = (f2 + siz <= size)? f2 + siz : size;
            while (f1 < l1 && f2 < l2)
            {
                n2 = f2;
                while (n2 < l2 && array[f1] > array[n2])
                    n2++;
                if (n2 > f2)
                {
                    mv = (n2 - f2); ;
                    memcpy(temparray, &array[f2], mv*sizeof(int));
                    memmove(&array[f1+mv], &array[f1], (f2 - f1)*sizeof(int));
                    memcpy(&array[f1], temparray, mv*sizeof(int));
                    f2  = n2;
                    f1 += mv;
                    l1 += mv;
                    // show(array, size);
                }
                else
                    f1++;
            }
        }
    }
}

int main()
{
   //int a[] = { 19, 21, 5, 3, 17, 34, 61, 4, 97, 1, 10, };
   int a[240];
   srand(time(NULL));
   for (int i = 0; i < sizeof(a)/sizeof(int); ++i)
       a[i] = rand()%100000;

   mergesort1(a, sizeof(a)/sizeof(int));
   
   show(a, sizeof(a)/sizeof(int));
   return 0;
}

Regards, Alex
0
 

Author Comment

by:wcpon
ID: 11843155
oh thx q....

C:\Documents and Settings\Chee\Desktop\New Folder\mm.cpp(44) : error C2065: 'memcpy' : undeclared identifier
C:\Documents and Settings\Chee\Desktop\New Folder\mm.cpp(45) : error C2065: 'memmove' : undeclared identifier
C:\Documents and Settings\Chee\Desktop\New Folder\mm.cpp(63) : error C206

3 errors occur....

dunno where i miss it....
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 11843219
you need

#include <string>        // STL

or

#include <string.h>    // no STL

Try STL variant first but you have to replace

 #include <iostream.h>

by

#include <iostream>

as well.

Regards, Alex
0
 

Author Comment

by:wcpon
ID: 11843250
the last one

C:\Documents and Settings\Chee\Desktop\New Folder\mm.cpp(64) : error C2065: 'time' : undeclared identifier


????
sorry.... disturb u
me is a beginner ....
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 11843344
>> me is a beginner ....

i'm an expert but it was my fault not yours...

add

#include <time.h>

and it should compile. Are you using STL or not?

Regards, Alex


0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 11843382
The  time()  function is used to seed srand() with a different number each time.  

Then, rand() function gives different random numbers to fill the array.

Regards, Alex


0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 

Author Comment

by:wcpon
ID: 11843431
yes....

C:\Documents and Settings\Chee\Desktop\New Folder\textQ2.cpp(123) : error C2065: 'memcpy' : undeclared identifier
C:\Documents and Settings\Chee\Desktop\New Folder\textQ2.cpp(125) : error C2065: 'memmove' : undeclared identifier


is it this two is a functions ??
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 11843450
time(NULL) returns the number of seconds elapsed since 1/1/1970. So every time you start the prog it should be different.

However, if you always want to test the same array, simply replace

  time(NULL)

by any odd number you want,

  e. g. 7857281.

Regards, Alex
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 11843487
Also in textQ2.cpp  (not only in mm.cpp) you must have these includes

#include <string>
#include <iostream>
#include <time.h>


Regards, Alex


0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 11843621
you also may create two source files  mergesort1.h and mergesort1.cpp:

// mergesort1.h

#ifndef MERGESORT1_H
#define MERGESORT1_H

   void showArray(int array[], int size);
   void mergesort1(int array[], int size);

#endif

// mergesort1.cpp

#include <string>
#include <iostream>
#include <time.h>


void showArray(int a[], int siz)
{
   for (int i = 0; i < siz; i+= 8 )
   {
       cout << a[i] << ' ' << a[i+1] << ' '  << a[i+2] << ' '  << a[i+3] << ' '  
            << a[i+4] << ' ' << a[i+5] << ' '  << a[i+6] << ' '   << a[i+7] << endl;
   }

   cin >> i;
}

void mergesort1(int array[], int size)
{
    int* temparray = new int[size/2 + 1];

    int siz    = 1;
    int nparts = size/2;
    int f1     = 0;
    int f2     = 1;
    int l1     = 1;
    int l2     = 2;
    int n2     = 1;
    int mv     = 0;

    for (siz = 1; siz <= size; siz *= 2)
    {
        nparts = size/siz;
        for (int n = 0; n < nparts; n+=2)
        {
            f1 = n*siz;
            f2 = f1 + siz;
            l1 = f2;
            l2 = (f2 + siz <= size)? f2 + siz : size;
            while (f1 < l1 && f2 < l2)
            {
                n2 = f2;
                while (n2 < l2 && array[f1] > array[n2])
                    n2++;
                if (n2 > f2)
                {
                    mv = (n2 - f2); ;
                    memcpy(temparray, &array[f2], mv*sizeof(int));
                    memmove(&array[f1+mv], &array[f1], (f2 - f1)*sizeof(int));
                    memcpy(&array[f1], temparray, mv*sizeof(int));
                    f2  = n2;
                    f1 += mv;
                    l1 += mv;
                    // showArray(array, size);
                }
                else
                    f1++;
            }
        }
    }
}

// end of file


Then, add mergesort1.cpp to your project.

In all cpp files where you want to use it, you now only need one include statement

#include "mergesort1.h"


Note, i renamed show() function to showArray() as show()  was a too common name.

Regards, Alex









0
 

Author Comment

by:wcpon
ID: 11843623
the program is worked.... now

but i dunno what is that ???
so confuse me .........

why the results coming out.....
not i want ???


i want to come out random array....
use 10 array enuf...  not so big...

then sorted in accending order....
why ur results coming out.... me not understand?
sorry ~
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 11843741
show() function - resp. showArray() - shows the whole sorted array in ascending order.

if you want only a shorter array, simply change the array size in main():

   int a[240];

-->

   int a[24];


But size it to  a multiple of 8 as the show function always shows full rows of 8 items.

if you want to see the unsorted array first, do this:

   void main()
   {
        int a[24];

        // fill with random numbers
 ]      srand(time(NULL));  // or srand(1234567);
        for (int i = 0; i < sizeof(a)/sizeof(int); ++i)
             a[i] = rand()%100000;

        show(a, sizeof(a)/sizeof(int));   // show unsorted

        mergesort1(a, sizeof(a)/sizeof(int));
   
        show(a, sizeof(a)/sizeof(int));   // show sorted
   }

BTW, you have to type a digit after show. That is only to keep the console window up.  

Regards, Alex
 
0
 

Author Comment

by:wcpon
ID: 11843890
it works.....
thx q alex

can Alex...
explain to me the program ? line by line??
some line.. i not so understand... what it does....

really thx you very much....
0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 300 total points
ID: 11844579
Ok!

// function mergesort1 takes an integer array AND the size of the array
// The size couldn't be evaluated from array using sizeof(array) here because
// array is only a pointer (to the first array element) when passed as an argument.

void mergesort1(int array[], int size)
{
    // need temp array to move parts in-place
    // later we have to 'merge' two sorted parts (buckets) of the array
    //
    //  e. g. [ 56 12 27 96 19 45 40 17 ]
    //
    // we start with bucket size == 1
    //  [56] [12] [27] [96] [19] [45] [40]  [17]
    //
    // that means we sort all pairs to that
    // [12 56] [27 96] [19 45 ] [ 17 40 ]
    //
    // Note, the [] are only for illustration
    //
    //  for bucket size == 4 we have that:
    //
    //    bucket 0             bucket 1
    //  [ 12 27 56 95 ] [ 17 19 40 45 ] ....
    //
    // Now we are 'merging' bucket 0 and bucket 1
    //  
    // 1.  we find out that [ 17 19 ] must be merged before 27
    // 2.  we copy  [ 17 19 ] to temp array  [17 19] ....
    // 3.  we move [ 27 56 95 ] two positions to the right (overwriting the two saved numbers)
    //      --> [ 12  .   .  [ 27 56 95 ] 40 45 ]
    // 4.  we copy [17 19 ] from temp array to the free positions
    //      --> [ 12 [ 17 19 ] [ 27 56 95 ] 40 45 ]
    //
    // 5.  now we continue to merge by comparing 27 with 45 ... nothing to merge
    // 6.  we find out that [ 40 45 ] must be moved before 56
    // 7.  save [40 45] to temp array
    // 8. move [56 95] two positions to the right
    // 9. copy saved [40 45] to free positions
    //  
    // finally we got:
    // [ 12 17 19 27 40 45 56 95 ]
    // that is a sorted bucket of siz == 8  (the next iteration)
    //

    // create a temporary array to save integers that got overwritten by moving parts in-place
    int* temparray = new int[size-1];

    int siz    = 1;            // current size of buckets to merge
    int nparts = size/2;   // number of buckets
    int f1     = 0;            // index of left bucket
    int f2     = 1;            // index of right bucket
    int l1     = 1;            // max of left bucket
    int l2     = 2;            // max of right bucket
    int n2     = 1;           // next index of right bucket
    int mv     = 0;          // positions to move

    // binary loop  1, 2, 4, 8, 16, 24, ... is bucket size
    for (siz = 1; siz <= size; siz *= 2)
    {
        // number of buckets
        nparts = size/siz;        

        // loop any second bucket (step == 2) and merge bucket n and bucket n+1
     
        for (int n = 0; n < nparts; n+=2)
        {
            f1 = n*siz;        // first index of left bucket
            f2 = f1 + siz;    // first index of right bucket
            l1 = f2;            // upper range of left bucket
            l2 = (f2 + siz <= size)? f2 + siz : size;   // upper range of right bucket
                                                                      // (but not bigger than size)

            // as both buckets are already sorted we are thru (means that the buckets are merged)
            // if either left or right bucket is done
            while (f1 < l1 && f2 < l2)
            {
                // n2 is the index of right bucket we use to check the number
                // of items in the right bucket that are less than the current
                // item of the left bucket
                n2 = f2;
               // check number of right bucket positions to move
                while (n2 < l2 && array[f1] > array[n2])
                    n2++;    

                // check if there numbers to move
                if (n2 > f2)
                {
                    mv = (n2 - f2);  // calculate the number of items to move
                    // save these items to temp array as they get overwritten when shifting right
                    memcpy(temparray, &array[f2], mv*sizeof(int));

                    // move intermediate sequence to the right
                    // note, memmove could handle overlapping buffers, memcpy not
                    memmove(&array[f1+mv], &array[f1], (f2 - f1)*sizeof(int));

                    // get temp data back
                    memcpy(&array[f1], temparray, mv*sizeof(int));

                    // increment f2
                    f2 = n2;
                    // increment f1 and l1 (because that sequence was shifted to the right)
                    f1 += mv;
                    l1 += mv;
                }
                else
                    f1++;     // if right number isn't less we simply go to next item of left bucket
            }
        }
    }
    // release allocation of temporary buffer
    delete [] temparray;
}


Hope, it's understandable

Regards, Alex

0
 

Author Comment

by:wcpon
ID: 11844708
Thanks you very much..
i try to understand it......

i want to sleep.... here already 2.30 am.....
anything i dun understand..
can i ask you...
thx for your help ..
thanks you Alex..
0
 

Author Comment

by:wcpon
ID: 11863072
#include<iostream.h>
#include<stdlib.h>

void mergesort(int[], int, int, int & ,int & ,int &);
void merge(int[], int, int, int, int &, int &, int &);

void main ()

{


      int select;
      const int size=24;
      int no[size], x, y, z, data=0, compare=0, rec=0;
      
      cout<<"------------Merge Sort--------------"<<endl;
      cout<<"------------------------------------"<<endl;
      cout<<"1>User Input Data."<<endl;
      cout<<"2>Average Case."<<endl;
      cout<<"3>Worst Case."<<endl;
      cout<<"4>Random Access."<<endl;
      cout<<"------------------------------------"<<endl;

      cout<<"Please Input your selection (1 ~ 4): ";
      cin>>select;
      cout<<endl;



      switch (select){
      case 1:
                  {
            cout<<"User Please Input Your Numbers : ";
            for(int i=0; i<=size; i++)
                  {
                  cin>>no[i];
                  }      
                  cout<<"Your Input Numbers are : "<<no[i]<<endl<<endl;
                  }            
      break;

      case 2:
            {
            int accending=1;
            for(int i=0; i<=size; i++)
                  {
                  no[i]=accending;
                  accending=accending+2;
                  }
                  cout<<"Average Case Array :"<<endl<<endl;
            }
      break;

      case 3:
            {

            int desccending=300;
            for(int i=0; i<=size; i++)
                  {
                  no[i]=desccending;
                  desccending=desccending-10;
                  }
                  cout<<"Worst Case Array :"<<endl<<endl;
            }
      break;

      case 4:

      for (x=0; x<=size; x++)
      
      {
            no[x]=rand() % 100;
      }

      cout<<"Original Random Access Array :"<<endl<<endl;
      break;

}

      
      
            for (y=0; y<=size; y++)
      
            {
            if (y<size)
                  cout<<no[y]<<", ";
            else
                  cout<<no[y]<<endl<<endl;
            }

      
mergesort(no, 0, size, data, compare, rec);

      switch (select){
      case 1:
            cout<<endl;
            cout<<"Array after mergesort (Input Array):"<<endl<<endl;
            break;

      case 2:
            cout<<endl;
            cout<<"Array After mergesort (Average Case):"<<endl<<endl;
            break;

      case 3:
            cout<<endl;
            cout<<"Array After mergesort (Worst Case):"<<endl<<endl;
            break;
      case 4:
            cout<<endl;
            cout<<"Array After mergesort (Random Access):"<<endl<<endl;

            break;
      }      
      

      for (z=0; z<=size; z++)
      {
            if(z<size)
                  cout<<no[z]<<", ";
            else
                  cout<<no[z]<<endl<<endl;
      }


      cout<<endl;
      cout<<"Total of >>Data Move<< for this array: "<<data<<endl;
      cout<<"Total of >>Comparison<< for this array: "<<compare<<endl;
      cout<<"Total of >>Recursive<< for this array: "<<rec<<endl<<endl;
}


const int maxsize = 26;

void merge(int theArray[], int first, int mid, int last, int &data, int &compare, int &rec)
{
      int tempArray[maxsize];
      int first1=first;
      int last1=mid;
      int first2=mid+1;
      int last2=last;
      int index=first1;
      
      for(; (first1<=last1) && (first2<=last2); ++index)
      {
                        
            if (theArray[first1] < theArray[first2])
                  {  
                        tempArray[index] = theArray[first1];
                        ++first1;

                  }
            else
                  {  
                        tempArray[index] = theArray[first2];
                        ++first2;
                        
                  }
                  compare=compare+1;

      }
      for (; first1<=last1; ++first1, ++index)
      {
            tempArray[index] = theArray[first1];
            compare=compare+1;
      }

      for (; first2<=last2; ++first2, ++index)
      {
            compare=compare+1;
            tempArray[index] = theArray[first2];
      }

      for (index = first; index<=last; ++index)
      {
              theArray[index] = tempArray[index];
      }
      
      data=index;

}

void mergesort (int theArray[], int first, int last,int &data, int &compare, int &rec)
{
      rec=rec+1;
      if (first<last)
      {      

            int mid = (first + last)/2;
            mergesort (theArray, first, mid, data, compare, rec);
                  
            mergesort (theArray, mid+1, last, data, compare, rec);

            merge (theArray, first, mid, last, data, compare, rec);
      }
}



this is my code.... for recursive.....

can i know .... how to add counter inside???  i want to calculate the "data move, comparison & how many recursive call"  
am i correct ???? am i add wrong ??
pls help ..... where i want to add ?
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 11865358
Take that:

#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#include <time.h>

void mergesort(int[],int,int,int &,int &,int &);
void merge(int[],int,int,int,int &,int &,int &);
void mergesort1(int[], int , int& , int&, int& );


void main ()

{
   
   
    int select;
    const int size=24;
    int no[size+1], x, y, z, data=0, compare=0, rec=0, move=0;
    int no1[size+1];

    cout<<"------------Merge Sort--------------"<<endl;
    cout<<"------------------------------------"<<endl;
    cout<<"1>User Input Data."<<endl;
    cout<<"2>Average Case."<<endl;
    cout<<"3>Worst Case."<<endl;
    cout<<"4>Random Access."<<endl;
    cout<<"------------------------------------"<<endl;
   
    cout<<"Please Input your selection (1 ~ 4): ";
    cin>>select;
    cout<<endl;
   
   
   
    switch (select){
    case 1:
        {
            cout<<"User Please Input Your Numbers : ";
            for(int i=0; i<=size; i++)
            {
                cin>>no[i];
                no1[i] = no[i];
            }    
            cout<<"Your Input Numbers are : "<<no[i]<<endl<<endl;
        }          
        break;
       
    case 2:
        {
            int accending=1;
            for(int i=0; i<=size; i++)
            {
                no1[i] = no[i]=accending;
                accending=accending+2;
            }
            cout<<"Average Case Array :"<<endl<<endl;
        }
        break;
       
    case 3:
        {
           
            int desccending=300;
            for(int i=0; i<=size; i++)
            {
                no1[i] = no[i]=desccending;
                desccending=desccending-10;
            }
            cout<<"Worst Case Array :"<<endl<<endl;
        }
        break;
       
    case 4:
       
        for (x=0; x<=size; x++)
           
        {
            no1[x] = no[x]=rand() % 100;
        }
       
        cout<<"Original Random Access Array :"<<endl<<endl;
        break;
       
    }
   
   
   
    for (y=0; y<=size; y++)
       
    {
        if (y<size)
            cout<<no[y]<<", ";
        else
            cout<<no[y]<<endl<<endl;
    }
   
   
    mergesort(no, 0, size, data, compare, rec);
   
    switch (select){
    case 1:
        cout<<endl;
        cout<<"Array after mergesort (Input Array):"<<endl<<endl;
        break;
       
    case 2:
        cout<<endl;
        cout<<"Array After mergesort (Average Case):"<<endl<<endl;
        break;
       
    case 3:
        cout<<endl;
        cout<<"Array After mergesort (Worst Case):"<<endl<<endl;
        break;
    case 4:
        cout<<endl;
        cout<<"Array After mergesort (Random Access):"<<endl<<endl;
       
        break;
    }    
   
   
    for (z=0; z<=size; z++)
    {
        if(z<size)
            cout<<no[z]<<", ";
        else
            cout<<no[z]<<endl<<endl;
    }
   
   
    cout<<endl;
    cout<<"Total of >>Data Move<< for this array: "<<data<<endl;
    cout<<"Total of >>Comparison<< for this array: "<<compare<<endl;
    cout<<"Total of >>Recursive<< for this array: "<<rec<<endl<<endl;

    compare = 0;
    data    = 0;    
    move    = 0;
    mergesort1(no1, size+1, data, compare, move);

    cout<<"Mergesort1 Done: "<<endl;

    for (z=0; z<=size; z++)
    {
      if(z<size)
           cout<<no1[z]<<",";
      else
           cout<<no1[z]<<endl<<endl;
    }

    cout<<"Total of Data Move for this MergerSort1: "<<data<<endl<<endl;
    cout<<"Total of Comparison for this MergerSort1: "<<compare<<endl<<endl;
    cout<<"Total of Move Operations for this MergerSort1: "<<move<<endl<<endl;
}


const int maxsize = 26;

void merge(int theArray[], int first, int mid, int last, int &data, int &compare, int &rec)
{
     int tempArray[maxsize];
     int first1=first;
     int last1=mid;
     int first2=mid+1;
     int last2=last;
     int index=first1;
     
     for(; (first1<=last1) && (first2<=last2); ++index)
     {
                   
          if (theArray[first1] < theArray[first2])
               {  
                    tempArray[index] = theArray[first1];
                    ++first1;

               }
          else
               {  
                    tempArray[index] = theArray[first2];
                    ++first2;
                   
               }
               compare=compare+1;

     }
     for (; first1<=last1; ++first1, ++index)
     {
          tempArray[index] = theArray[first1];
          data++;
     }

     for (; first2<=last2; ++first2, ++index)
     {
          data++;
          tempArray[index] = theArray[first2];
     }

     for (index = first; index<=last; ++index)
     {
            theArray[index] = tempArray[index];    
            data++;
     }
     
     

}

void mergesort (int theArray[], int first, int last,int &data, int &compare, int &rec)
{
     rec=rec+1;
     if (first<last)
     {    

          int mid = (first + last)/2;
          mergesort (theArray, first, mid, data, compare, rec);
               
          mergesort (theArray, mid+1, last, data, compare, rec);

          merge (theArray, first, mid, last, data, compare, rec);
     }
}


void mergesort1(int array[], int size, int& data, int& compare, int& move)
{
    int* temparray = new int[size/2 + 1];

    int siz    = 1;
    int nparts = size/2;
    int f1     = 0;
    int f2     = 1;
    int l1     = 1;
    int l2     = 2;
    int n2     = 1;
    int mv     = 0;

    for (siz = 1; siz <= size; siz *= 2)
    {
        nparts = size/siz;
        for (int n = 0; n < nparts; n+=2)
        {
            f1 = n*siz;
            f2 = f1 + siz;
            l1 = f2;
            l2 = (f2 + siz <= size)? f2 + siz : size;
            while (f1 < l1 && f2 < l2)
            {
                n2 = f2;

                while (n2 < l2)
                {  
                    ++compare;
                    if (array[f1] < array[n2])
                        break;
                    n2++;
                }
                if (n2 > f2)
                {
                    data = data + mv + (f2 - f1) + mv;
                    move += 3;
                    mv = (n2 - f2); ;
                    memcpy(temparray, &array[f2], mv*sizeof(int));
                    memmove(&array[f1+mv], &array[f1], (f2 - f1)*sizeof(int));
                    memcpy(&array[f1], temparray, mv*sizeof(int));
                    f2  = n2;
                    f1 += mv;
                    l1 += mv;
                    // show(array, size);
                }
                else
                    f1++;
            }
        }
    }
}


Note:

1. I had to increase siize of arrays by 1 as all loops run from 0 to size, that is size+1 elements.
2. However, the size argument of mergesort _MUST_ be still 'size' and not 'size+1'. That's a bug or it's size-1 that has to be passed to mergesort.
    Look at value of maxsize==26: the temp array is sized properly.
3. The data value of mergesort isn't counted properly. 'data' is set to 'index' at end of merge ignoring any argument value of aa previous call to
    merge().  So, finally it is set to index value of the last call to merge that is the size value. The correct number of data moves is equal to the
    number of comparisions as it does no in-place move but moves _ALL_ data to a temp array. So, merge() always compares left and right
   bucket values and moves either the one or the other value to temp array.  The for loops after comparison copy the rest of either the left or
   right bucket. Finally all values are copied back after that.
4. mergesort1 does an inplace editing (not sorting to a temp array and copying all back) but using a temp array only to save these parts of
    the array that get overwritten by the next move operation in-place. I don't pass a recursive counter (as there isn't any recursion) but a
   'move' counter instead. 'data' counts the number of integers that are moved. 'move' counts the number of copy or move operations (by
    using memcpy or memmove).
5. The number of comparisions of mergesort1 normally is higher than these of mergesort. That is because mergesort1 always checks for
    a sequence of integers in the right bucket to move rather than checking only one value. In case of an already sorted array therefore we
    have no moves.

Regards, Alex

5.
             
0

Featured Post

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now