QOJxKj - Online C++ Compiler & Debugging Tool - Ideone.com please tell me what changes i should do in this quicksort program
You should call the functions on line 20, 21 and 22 as
int pindex=partition(a,start,end-1);
pindex=partition(a,start,pindex-1);
pindex=partition(a,pindex+1,end);
That is just a
instead of a[]
.
Next, define you array as
static int a[1000001];
before your main()
( that is, define it as a global variable )
Also, change your second scanf()
to
scanf(" %d",&a[i]);
You are also trying to access one value which is not present in the array. Let’s explain that.
You accept t
as the number of values to be inserted into the array. Then you send it as an argument to the function qiucksort()
. That means you have an array of indices 0 to ( t - 1 ) or ( end - 1 ). But later you are trying to access a[end]
, which clearly does not have any value you stored in it.
You also have many variables in main()
, namely
b,pindex,start,end
which are not even used in your main()
.
Next, in your function partition()
you have
int partition(int a[],int start,int end)
{
int pivot;
pivot=a[end];
int pindex=a[start];
for(int i=start;i<end;i++)
{
if(a[i]<=pivot)
{
int temp;
temp=pivot;
pivot=a[i];
a[i]=temp;
pindex=pindex+1;
}
swap(a[pindex],a[end])
{
int temp;
temp=a[pindex];
a[pindex]=a[end];
a[end]=temp;
}
return pindex;
}
}
I hope you didn’t mean std::swap
in there ( line 41 on your ideone link ). And I don’t even know why you are using that return
statement inside your for loop.
These are just some of the mistakes I noticed. I have not yet checked the logic of your code ( simply put, your program ran for me, but it didn’t give the expected output ).
In case you need more help, read this . By reffering to this link, you should understand that your code does not even look like a quicksort algorithm.
Here’s a working quicksort algorithm
#include <iostream>
using namespace std;
void quicksort(int [],int,int);
static int a[1000001];
int main() {
int t,i;
scanf("%d", &t);
for(i=0;i<t;i++)
scanf(" %d",&a[i]);
quicksort( a , 0 , t-1 );
for(i=0;i<t;i++)
printf("%d\n",a[i]);
return 0;
}
void quicksort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
/* partition */
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
}
This code will help you. If u can not understand, please comment.
#include #include using namespace std; int partition(int arr[], int start, int end) { int pivotValue = arr[start]; int pivotPosition = start; for (int i=start+1; i<=end; i++) { if (pivotValue > arr[i]) { swap(arr[pivotPosition+1], arr[i]); swap(arr[pivotPosition] , arr[pivotPosition+1]); pivotPosition++; } } return pivotPosition; } void quickSort(int arr[], int low, int high) { if (low < high) { /* pi is partitioning index, arr[p] is now at right place */ int pi = partition(arr, low, high); // Separately sort elements before // partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } int main() { int arr[10],n; cin>>n; for(int i=0; i<n; i++) { cin>>arr[i]; } quickSort(arr, 0, n-1); for(int k = 0; k<n; k++) cout<<arr[k]<<" "; return 0; }
what problems are you getting ?
this program is showing error i m not able to correct it
thanks arjun i will try to again