Member Avatar for 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 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 by Nick Evan because: Added code-tags
  • 2 Contributors
  • 3 Replies
  • 293 Views
  • 12 Hours Discussion Span
  • Latest Post Latest Post by MyrtleTurtle

Dani AI

Generated

Two concrete bugs explain the “first and last elements unsorted” symptom: out‑of‑bounds I/O and incorrect index math in the insertion‑sort fallback. In the original snippets the input/output loops use <= on the array size (reading 16 values into a 15‑element array), which corrupts memory. The hybrid decision uses expressions like (p - r) instead of r - p + 1, so the insertion fallback runs with the wrong range. The insertion loop also uses 1‑based indices and i > 0 so the first element (index p) is never considered. There are also undefined/duplicated variables (double partition calls, r used where pivot was intended) and void main(); each of these can cause compile/runtime errors or wrong results. correctly flagged the off‑by‑one I/O issue.

Suggested fixes and a corrected hybrid quicksort implementation follow. Key rules applied: use zero‑based indices consistently, compute subarray length as r - l + 1, switch to insertion sort only for the current subarray (l..r), call partition once, and avoid reading/writing past 0..n-1.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void insertion_sort(int a[], int l, int r) {
    for (int j = l + 1; j <= r; ++j) {
        int key = a[j];
        int i = j - 1;
        while (i >= l && a[i] > key) { a[i+1] = a[i]; --i; }
        a[i+1] = key;
    }
}

int partition(int a[], int l, int r) {
    int pivot = a[r], i = l - 1;
    for (int j = l; j < r; ++j)
        if (a[j] <= pivot) { ++i; swap(a[i], a[j]); }
    swap(a[i+1], a[r]);
    return i + 1;
}

void hybrid_quicksort(int a[], int l, int r, int threshold = 10) {
    while (l < r) {
        if (r - l + 1 <= threshold) { insertion_sort(a, l, r); break; }
        int q = partition(a, l, r);
        if (q - l < r - q) { hybrid_quicksort(a, l, q - 1, threshold); l = q + 1; }
        else { hybrid_quicksort(a, q + 1, r, threshold); r = q - 1; }
    }
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];
    hybrid_quicksort(v.data(), 0, n - 1);
    for (int i = 0; i < n; ++i) cout << v[i] << (i+1<n ? ' ' : '\n');
    return 0;
}

Troubleshooting tips: compile with warnings enabled (-Wall -Wextra), test with small arrays where the correct result is known, and insert temporary prints to validate index ranges before/after partition. Replacing raw arrays with std::vector (as above) and using int main() removes several common C/C++ pitfalls. The changes address the issues raised by and the indexing concerns noted by .

Recommended Answers

All 3 Replies

Member Avatar for 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.

Edited by MyrtleTurtle because: n/a
Member Avatar for 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");
}
Edited by Faiza_Iqbal because: n/a
Member Avatar for 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 . It seems to work just fine without the partition.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.