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

Edited 6 Years Ago by Nick Evan: Added code-tags

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.

Edited 6 Years Ago by MyrtleTurtle: n/a

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

Edited 6 Years Ago by Faiza_Iqbal: n/a

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.

This article has been dead for over six months. Start a new discussion instead.