1,105,197 Community Members

between merge sort and binary insertion sort graph whose slope is greater

Member Avatar
poojabi
Newbie Poster
23 posts since Aug 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

between merge sort and binary insertion sort which is more efficient?i know that theoritically both are nlogn search bt practically which will be better.that means if we plot the graph of number of comparison vs number of element in the list hose slope wll be slightly more than the other.and how will i count the comparison of binary insertion sort?for counting comparison in two different manner two different result are coming. if if i take the comparison of first and last then comparison of binary sort is greater than the merge sort bt if i take the comparison of the element with mid then merge has greater comparison.
this is my program

actually i am asked to plot graph for bubble,merge,insertion,binary insertion,shell sort when the number of element in the list is in the powe of 2 and list is randomly generated by rand function.pls help me i am really confused about this comparison thing,pls reply as soon as possible.tomorrow i have to show the program and i dont know what to do.

#include<stdio.h>
 #include<stdlib.h>
 int global;
 int bubble(int p[],int);
 void partition(int c[],int,int);
 void sort(int a[],int,int,int);
 int insert(int p[],int);
 int binary(int p[],int);
 int shell(int p[],int);
 void pri(int p[],int);
 void main()
 {
 global=0;
 int i=0,n;
unsigned long int com;
 int *b,*m;
 char resp;
 FILE *fp;
 fp=fopen("sort.csv","w");
 fprintf(fp,"n,bubble,merge,insertion,binary,shell,\n");
 do
 {
 printf("pls enter the number of element int the array-> n\n");
 printf("the value of n should in the power of 2");
 scanf("%d",&n);
 fprintf(fp,"%d,",n);
 b=(int*)malloc(n*sizeof(int));
 m=(int*)malloc(n*sizeof(int));

 srand(time(0));
 for(i=0;i<n;i++)
 {
 b[i]=rand()%100;
 }


 printf("the given array is \n");
 for(i=0;i<n;i++)
 {
 printf("%d\t",b[i]);
 }
 printf("\n");

 /*    bubble sort */
 printf("---------------bubble sort--------------        \n");
 for(i=0;i<n;i++)
 {
 m[i]=b[i];
 }
 pri(b,n);
 com=bubble(m,n);
 fprintf(fp,"%d,",com);
 /*                     mergesort                 */
 printf("---------------mergesort---------------\n          ");

 for(i=0;i<n;i++)
 {
 m[i]=b[i];
 }
pri(b,n);
partition(m,0,n-1);
 printf("    the sorted array using merge sort is\n ");
 for(i=0;i<n;i++)
 {
 printf("%d\t",m[i]);
 }
 printf("\n");
 fprintf(fp,"%d,",global);
 global=0;


 /*        insertion sort               */
 printf("---------------insertion sort---------------\n         ");
 for(i=0;i<n;i++)
 {
 m[i]=b[i];
 }
 pri(b,n);
 com=insert(m,n);
 fprintf(fp,"%d,",com);
 /*                      binary insertion sort       */
 printf("---------------binary insertion sort---------------      \n");
 for(i=0;i<n;i++)
 {
 m[i]=b[i];
 }
 pri(b,n);
 com=binary(m,n);
fprintf(fp,"%d,",com);
              /*             shell sort*/
 printf("---------------shell sort---------------\n");
 for(i=0;i<n;i++)
 {
 m[i]=b[i];
 }
 pri(b,n);
 com=shell(m,n);
 fprintf(fp,"%d,",com);
 fprintf(fp,"\n");
 fclose(fp);

 printf("enter ur choice y/n \n");
 getchar();
 resp=getchar();
 getchar();
 if(resp=='y')
 fopen("sort.csv","a");

 free(b);
 free(m);
 }
 while(resp=='y');
 }


void pri(int p[],int n)
{
printf("the original array is--------------------->\n");
int i;
for(i=0;i<n;i++)

{
printf("%d\t",p[i]);

}
printf("\n");
}
 int bubble(int p[],int n)
 {
 int i,j,space;
unsigned long int com=0;
 for(i=0;i<=n-2;i++)
  {
     for(j=0;j<=n-2-i;j++)
     {
    com++;

    if(p[j]>p[j+1])
        {
        space=p[j];
        p[j]=p[j+1];
         p[j+1]=space;
         }
    }
 }

  printf(" the sorted array using bubble sort\n");
  for(i=0;i<n;i++)
  {
  printf("%d\t",p[i]);
  }
  printf("\n");
  return com;
  }
  int insert(int p[],int n)
  {
  unsigned long int com=0;
  int i,j,temp;
  for(i=1;i<n;i++)
  {
     temp=p[i];
     for(j=i;j>0&&p[j-1]>temp;j--)
     {
     com++;
     p[j]=p[j-1];

     }
       p[j]=temp;
       com++;
      }
      printf("the sorted array using insertion sort is\n");
      for(i=0;i<n;i++)
      {
      printf("%d\t",p[i]);
      }
      printf("\n");
      return com;
      }


int binary(int p[],int n)
{
int first,last,mid,i,j,temp;
unsigned long int comp=0;
for(i=1;i<n;i++)
{
temp=p[i];
first=0;
last=i-1;
while(first<=last)
{
comp++;
mid=(first+last)/2;
if(temp>p[mid])
first=mid+1;
else
last=mid-1;

}
comp++;
for(j=i;j>first;j--)
{
p[j]=p[j-1];
}
p[j]=temp;
}
printf("the sorted array using binary insertion sort is \n");
for(i=0;i<n;i++)
{
printf("%d\t",p[i]);
}
printf("\n");
return comp;
}
void partition(int c[],int low,int high)
{
int mid;

if(low<high)
{
mid=(low+high)/2;
partition(c,low,mid);
partition(c,mid+1,high);
sort(c,low,mid,high);
}
}
void sort(int a[],int low,int mid,int high)
{


 int i,j,k,l;
 int *b;
 b=(int*)malloc((high+1)*sizeof(int));

 l=low;
 i=low;
 j=mid+1;
 while((l<=mid)&&(j<=high))

 {   global++;

     if(a[l]<=a[j])
     {
    b[i]=a[l];
    l++;
    }
      else
      {
      b[i]=a[j];
      j++;
      }
      i++;
      }
      if(l>mid)
      {
      for(k=j;k<=high;k++)
      {
      b[i]=a[k];
      i++;
      }
      }
      else
      {
      for(k=l;k<=mid;k++)
      {
      b[i]=a[k];
      i++;
      }

      }

      for(k=low;k<=high;k++)
      {
      a[k]=b[k];

      }

      free(b);
      }

int shell(int p[],int n)

{
int span;
int j=0,k,temp;
unsigned long int com=0;


if(n!=1)
{
for(span=7;span>0;span=span-2)
{
for(j=span;j<n;j++)
{
temp=p[j];
for(k=j-span;k>=0&&p[k]>temp;k=k-span)
{
com++;
p[k+span]=p[k];

}
com++;
p[k+span]=temp;
}
}
}
printf(" the sorted array using shell sort is\n");
for(j=0;j<n;j++)
{
printf("%d\t",p[j]);

}
printf("\n");
return com;
}
Member Avatar
Adak
Posting Virtuoso
1,711 posts since Jun 2008
Reputation Points: 419 [?]
Q&As Helped to Solve: 207 [?]
Skill Endorsements: 10 [?]
 
0
 

Multi merge sorting can be optimized to fit the architecture of a computer system, to produce an outstanding sorter.

An example is the champion sorting program "Psort", which you can read more about by Googling it.

In my testing, Binary insertion is better than the normal Insertion sort, and both will beat anything else, with small or almost sorted, data.

With random data, both Insertion sorts will beat anything else, but that applies only to random int arrays with fewer than about 100 numbers. After that, Quicksort, Merge sort, Comb sort 11, and Shell sort (with an optimal series), begin to sort just as fast as either type of Insertion sort.

Where their sort times are equal will vary from system to system, and with specifics of the randomized data. The best numerical sorters (Quicksort Merge sort, and Heap sort), don't begin to really pull away, until you have tens or hundreds of thousands of numbers to be sorted. Again, that point depends on your system, but it will be reached, if you repeat the sorting, sequentially, for large arrays. (That is, I use arrays of 20,000 or so, and set it up so I can test it by having it sort any number of 20k arrays of changing randomized numbers, with the time being measured for ALL the arrays to be sorted).

Having either type of Insertion sort handle the smaller sub arrays of Quicksort, gives Quicksort a nice speed up. That is my fastest numerical sorter, atm. I don't have a version of a multi-merge sorter yet, to try out. So for me, it's optimized Quicksort + Insertion sort as #1, and Merge sort is #2, with Heap sort #3, on large randomized integer arrays.

Binary Insertion sort, falls ways behind on really large sorts. I'm not sure that it's really an n log n sorter.

If you want help with your code, say what has you stumped, and what the problems are! You have to be specific about the problem, to get specific advice to fix it. Saying just "HELP" is like going to the doctor, but refusing to tell him where it hurts. ;)

And please, USE CODE TAGS!!. It's crazy difficult to read/study code that has been posted without using code tags around it.

Member Avatar
poojabi
Newbie Poster
23 posts since Aug 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

that means at first binary sort will proceed and after 100 merge sort will proceed?
here i am taking the no of the list from 1 to 1024(power of 2).that means after after 256 merge sort will lead?to compare this sorts i am using number of basic operation of the algorithm instead of running time.
say i am taking a integer say com
int com=0;
now it will count the basis operation for binary insertion sort.
now in my opinion here basic operation is comparing the element which we want to insert with the mid of the sorted array in the left side.
now my code will be like below


int binary(int p[],int n)
{
int first,last,mid,i,j,temp;
unsigned long int comp=0; counter variable
for(i=1;i<n;i++)
{
temp=p;
first=0;
last=i-1;
while(first<=last) binary search start
{
comp++; increasing the counter
mid=(first+last)/2;
if(temp>p[mid])
first=mid+1;
else
last=mid-1;

}
/*comp++;*/should i include this step also
for(j=i;j>first;j--)
{
p[j]=p[j-1];
}
p[j]=temp;
}

return comp;
}
now some time i fill that the basic operation of this algorithm is comparison of high with low.this is the main confusion pls clear it.
for merge sort sort i am taking an global variable global
and taking it as a counter.
and here the problem is same i mean i am confused about what is the basic operation here?
the comparison between l and mid and j and high or comparison between a[l]and a[j]?
void partition(int c[],int low,int high)
{
int mid;

if(low<high)
{
mid=(low+high)/2;
partition(c,low,mid);
partition(c,mid+1,high);
sort(c,low,mid,high);
}
}
void sort(int a[],int low,int mid,int high)
{


int i,j,k,l;
int *b;
b=(int*)malloc((high+1)*sizeof(int));

l=low;
i=low;
j=mid+1;
while((l<=mid)&&(j<=high))

{ global++;

if(a[l]<=a[j])
{
b=a[l];
l++;
}
else
{
b=a[j];
j++;
}
i++;
}
if(l>mid)
{
for(k=j;k<=high;k++)
{
b=a[k];
i++;
}
}
else
{
for(k=l;k<=mid;k++)
{
b=a[k];
i++;
}

}

for(k=low;k<=high;k++)
{
a[k]=b[k];

}
/* global++;*/should i include this step also?
free(b);
}
bt the whatever i am doing like the are 4 cases
i am referring here the increment of the counter outside the while loop
1)comp++ only
2)comp++, global++
3)global++ only
4)none
there is no change in the nature of the final value of global and comp
i mean if one is leading then it is always leading.
like for case 1 comp will be always greater than global.
for case 2 and 4 global is bigger.
so i am totally hopeless and dont know what to do.pls help me as soon as u can. my only hope is that i will get a correct answer from here.

Member Avatar
Adak
Posting Virtuoso
1,711 posts since Jun 2008
Reputation Points: 419 [?]
Q&As Helped to Solve: 207 [?]
Skill Endorsements: 10 [?]
 
0
 

Checked on the big O (efficiency) rating for Binary Insertion sort. It is log2 n, not n log n, like Quicksort and Merge Sort.

I can't study your code - you still don't use the [CODE ] tags [/COD E] around your code.

With random integers, and less than 20 numbers, Insertion sorts win the sorting race,
packed behind it VERY tightly, are all the other sorting algorithms, including Quicksort and Mergesort. To detect any differences, you need to sort 100's of these small randomized arrays of integers, in a timed run. In one run, your computer may not see any difference in time - reporting 0.0000 seconds for the sort.

50 to 100, several of them tie: Quicksort, Mergesort, Insertion sort (both of them), Shell sort, Comb sort 11, Heap sort, Bubble sort, Selection sort. The computer shows no time was used, by any of the sorting runs. Again, if you want to see any differences at all, you have to make several runs of these small arrays, into one timed event. A single sort of 50 to 100 integers will still show 0.0000 elapsed seconds. (depending on your timing hardware and software)

With 1,000 random int's or more, you can see:

*Quicksort, Merge sort, Heap sort, are tied with Comb sort 11 and Shell sort, for first place.

  • Binary Insertion starts to edge out regular Insertion sort, enough that the computer can detect the difference (sometimes) in timed runs. Both of these are just a small amount ahead of Selection sort, here.

*Bubble sort begins to fall behind.

This pattern continues as more numbers are added to the array. Quicksort, Merge sort, and Heap sort, finally emerge as the best sorters, with Comb sort 11 and Shell sort, taking up the second tier of sorts. In the third group is Binary Insertion sort. Fourth group is Insertion sort (regular), and Selection sort. Bubble sort is in last place.

This is the code I use for Binary Insertion sort:

Notice how easy it is to study when it's BETWEEN THE CODE TAGS!

//Binary Insertion Sort
void insertionBinary(int A[], int n)
{
    register int i, m;
    int hi, lo, tmp;

    for (i = 1; i < n; i++) {
        lo = 0, hi = i;
        m = i / 2;

        do {
            if (A[i] > A[m]) {
                lo = m + 1;
            } else if (A[i] < A[m]) {
                hi = m;
            } else
                break;

            m = lo + ((hi - lo) / 2);
        } while (lo < hi);

        if (m < i) {
            tmp = A[i];
            memmove (A + m + 1, A + m, sizeof (int) * (i - m));
            A[m] = tmp;
        }
    }
}

Any post with code outside code tags henceforth, will be ignored.

<< USE THE CODE TAGS >> AROUND YOUR CODE. Click on [CODE] icon, in the editor, on the top bar. Paste your code between the code tags that you are given.

Member Avatar
poojabi
Newbie Poster
23 posts since Aug 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 
int binary(int p[],int n)
{
int first,last,mid,i,j,temp;
unsigned long int comp=0;
for(i=1;i<n;i++)
{
temp=p[i];
first=0;
last=i-1;
while(first<=last)
{
comp++;
mid=(first+last)/2;
if(temp>p[mid])
first=mid+1;
else
last=mid-1;

}
comp++;
for(j=i;j>first;j--)
{
p[j]=p[j-1];
}
p[j]=temp;
}

return comp;
}
void partition(int c[],int low,int high)
{
int mid;

if(low<high)
{
mid=(low+high)/2;
partition(c,low,mid);
partition(c,mid+1,high);
sort(c,low,mid,high);
}
}
void sort(int a[],int low,int mid,int high)
{


 int i,j,k,l;
 int *b;
 b=(int*)malloc((high+1)*sizeof(int));

 l=low;
 i=low;
 j=mid+1;
 while((l<=mid)&&(j<=high))

 {   global++;

     if(a[l]<=a[j])
     {
    b[i]=a[l];
    l++;
    }
      else
      {
      b[i]=a[j];
      j++;
      }
      i++;
      }
      if(l>mid)
      {
      for(k=j;k<=high;k++)
      {
      b[i]=a[k];
      i++;
      }
      }
      else
      {
      for(k=l;k<=mid;k++)
      {
      b[i]=a[k];
      i++;
      }

      }

      for(k=low;k<=high;k++)
      {
      a[k]=b[k];

      }
      global++;
      free(b);
      }
Member Avatar
poojabi
Newbie Poster
23 posts since Aug 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 
int binary(int p[],int n)
{
int first,last,mid,i,j,temp;
unsigned long int comp=0;
for(i=1;i<n;i++)
{
temp=p[i];
first=0;
last=i-1;
while(first<=last)
{
comp++;
mid=(first+last)/2;
if(temp>p[mid])
first=mid+1;
else
last=mid-1;

}
comp++;
for(j=i;j>first;j--)
{
p[j]=p[j-1];
}
p[j]=temp;
}

return comp;
}
void partition(int c[],int low,int high)
{
int mid;

if(low<high)
{
mid=(low+high)/2;
partition(c,low,mid);
partition(c,mid+1,high);
sort(c,low,mid,high);
}
}
void sort(int a[],int low,int mid,int high)
{


 int i,j,k,l;
 int *b;
 b=(int*)malloc((high+1)*sizeof(int));

 l=low;
 i=low;
 j=mid+1;
 while((l<=mid)&&(j<=high))

 {   global++;

     if(a[l]<=a[j])
     {
	b[i]=a[l];
	l++;
	}
      else
      {
      b[i]=a[j];
      j++;
      }
      i++;
      }
      if(l>mid)
      {
      for(k=j;k<=high;k++)
      {
      b[i]=a[k];
      i++;
      }
      }
      else
      {
      for(k=l;k<=mid;k++)
      {
      b[i]=a[k];
      i++;
      }

      }

      for(k=low;k<=high;k++)
      {
      a[k]=b[k];

      }
      global++;
      free(b);
      }
Member Avatar
poojabi
Newbie Poster
23 posts since Aug 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

hey now i have tagged the code.pls check it .and tell that how to increment global and comp to get correct comparison

Member Avatar
poojabi
Newbie Poster
23 posts since Aug 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

what is the meaning of log2n?is it log of n base 2 or log of 2n base 2?bt whatever may be the case log2n is always less than nlogn isnt it?this imply that binary insertion sort will always lead.because the real growth funtion of binary insrtion sort cant cross log2n,(i think that is the meaning of big o notation).so there is no question of leading of merge sort.bt u told that after n=100 merge will lead.this is increasing my confusion more and more.pls just tell me clearly that between comp and global who will be greater.today i have to show the code and i am now spending a sleepless night for this.

Member Avatar
poojabi
Newbie Poster
23 posts since Aug 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

i want to ask that should i include line 23 and 95 in my code?

Member Avatar
Adak
Posting Virtuoso
1,711 posts since Jun 2008
Reputation Points: 419 [?]
Q&As Helped to Solve: 207 [?]
Skill Endorsements: 10 [?]
 
0
 

log n is just that: log n.

n log n is: n(log n)

Line 23 should stay. I don't know what "global" does.

You have code for a merge sort, labeled as binary sort!

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article