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

[MyrtleTurtle]

Well, for one thing, you are asking for (and later printing) 16 inputs from the user, not 15. Also, meaningful variable names (and indenting) would be nice. :)

Here's an insertion sort I found interesting, and thought it may be helpful to you.

[Faiza_Iqbal]

Now look at this..this is still not sorting the first input..

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

[MyrtleTurtle]

The first code seems to be better, to me. The second one won't even compile for me, as is. You're trying to use the variable r without passing it into the functions, and I cannot see where you declare startindex or pivot.

Also you still have the same issue as before. a[10] means there are ten spots in the array, right? And it starts with 0. So the last spot will be a[9], not a[10].

It seems to me as if you're making this a little more complicated than it really needs to be. I wouldn't even do the partition part.

Here's another example of an insertion sort. It seems to work just fine without the partition.