hybrid quick sort

This is a discussion on hybrid quick sort within the C++ Programming forums, part of the General Programming Boards category; first i had partioned my array into two subarrays. Then the quick sort switches to insertion sort for sorting the ...

  1. #1
    Registered User
    Join Date
    Feb 2010
    Location
    Pakistan
    Posts
    6

    hybrid quick sort

    first i had partioned my array into two subarrays. Then the quick sort switches to insertion sort for sorting the small sized subarrays. But the error is logic error, because when i enter 15 inputs, the first and the last inputs are not sorted at all..I think error is in my loop.so please guide me to remove this.


    Code:
    #include<iostream>
    using namespace std;
    void quicksort(int a[],int p,int r);
    int partition(int a[],int p,int r);
    void quicksort(int a[],int p,int r)
    {
    	if(p<r)
    	{
    		int q;
    		q=partition(a,p,r);
    			if((p-r)<(r+1))
    			{
    				int i=0;
    				int key;
    
    				for(int j=1;j<(r+1);j++)
    				{
    	       			key=a[j];
    					i=j-1;
    					while(i>0&&a[i]>key)
    					{
    						a[i+1]=a[i];
    						i=i-1;
    					}
    			
    					a[i+1]=key;
    	    		}
    		}
    		else
    		{
    			q=partition(a,p,r);
    			quicksort(a,p,q-1);
    			quicksort(a,q+1,r);
    		}
    	}
    }
    
    int partition(int a[],int p,int r)
    {
    int x=a[r];
    int i=p-1;
    int j;
    	for(j=p;j<r;j++)
    	{
    		if(a[j]<=x)
    		{
    			i++;
    			int temp;
    			temp=a[i];
    			a[i]=a[j];
    			a[j]=temp;
    		}
    	}
    int temp1;
    temp1=a[i+1];
    a[i+1]=a[r];
    a[r]=temp1;
    return i+1;
    }
    void main()
    {
    int a[15],p=0,r=14;
    	for(int b=0;b<=15;b++)
    	{
    		cin>>a[b];
    	}
    quicksort(a,p,r);
    	for(int c=0;c<=15;c++)
    	{
    		cout<<" "<<a[c];
    	}
    system("pause");
    }
    Last edited by Faiza Iqbal; 03-12-2010 at 05:50 AM.

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    112
    Kindly Indent your code , and use code tags.

  4. #4
    Registered User
    Join Date
    Feb 2010
    Location
    Pakistan
    Posts
    6
    now tagging have been done...i was new here.....now anybody will tell me code error????

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Faiza Iqbal View Post
    now tagging have been done...i was new here.....now anybody will tell me code error????
    Be patient. You may get help easier if you can focus on and explain your problem better.

    If this were my code I would want to throw in some printf's to watch the process and see if I can discern what is actually happening.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    First of all you are storing 16 values in an array for 15 ints. If the sort function is correct, I'd indeed expect the extra one to be left there.

    I don't follow your criteria for switching to insertion sort either. I've heard that it might be better to use insertion-sort instead of quicksort on ranges up to 16 or so items. In your example, since p-r will always be negative(?), it will always be less than r + 1?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    Registered User
    Join Date
    Feb 2010
    Location
    Pakistan
    Posts
    6
    Thanks..I have corrected the error of input which was extra...and this code will be used for larger inputs but i am trying this for small value of input just for check..I have corrected but still there is one number unsorted in output array...


    Code:
    #include<iostream>
    using namespace std;
    void quicksort(int a[],int startindex,int pivot);
    int partition(int a[],int startindex,int pivot);
    void quicksort(int a[],int startindex,int pivot)
    {
    	if(startindex < pivot)
    	{
    		int q;
    		q=partition(a, startindex, pivot);
    			if((startindex - pivot)<4)
    			{
    				int i=0;
    				int key;
    
    				for(int j=1;j<10;j++)
    				{
    	       			key=a[j];
    					i=j-1;
    					while(i>0&&a[i]>key)
    					{
    						a[i+1]=a[i];
    						i=i-1;
    					}
    			
    					a[i+1]=key;
    	    
    				}
    				
    		}
    
    			
    		else
    		{
    			q=partition(a, startindex, pivot);
    			quicksort(a, startindex,q-1);
    			quicksort(a,q+1, pivot);
    		}
    	}
    }
    
    int partition(int a[],int startindex,int pivot)
    {
    int x=a[pivot];
    int i= startindex -1;
    int j;
    	for(j= startindex;j< pivot;j++)
    	{
    		if(a[j]<=x)
    		{
    			i++;
    			int temp;
    			temp=a[i];
    			a[i]=a[j];
    			a[j]=temp;
    		}
    	}
    int temp1;
    temp1=a[i+1];
    a[i+1]=a[r];
    a[r]=temp1;
    return i+1;
    }
    void main()
    {
    int a[10],p=0,r=9;
    	for(int b=0;b<=10;b++)
    	{
    		cin>>a[b];
    	}
    quicksort(a, startindex, pivot);
    	for(int c=0;c<10;c++)
    	{
    		cout<<" "<<a[c];
    	}
    system("pause");
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Help me on Quick Sort algorithm
    By chatterjee in forum C Programming
    Replies: 21
    Last Post: 07-19-2009, 01:40 PM
  3. Questions on basic Quick Sort
    By Weng in forum C++ Programming
    Replies: 4
    Last Post: 12-16-2003, 09:06 AM
  4. Sorting
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 11-10-2003, 04:21 PM
  5. radix sort and radix exchange sort.
    By whatman in forum C Programming
    Replies: 1
    Last Post: 07-31-2003, 12:24 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21