hybrid quick sort

[Faiza Iqbal]

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.

#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");
}

[MK27]

Please read:
<< !! Posting Code? Read this First !! >>

[Fatima Rizwan]

Kindly Indent your code , and use code tags.

[Faiza Iqbal]

now tagging have been done...i was new here.....now anybody will tell me code error????

[MK27]

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.

[anon]

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?

[Faiza Iqbal]

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...

#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");
}