1. ## quick sort program

hey friends!!!! Quicksort algorithm is simple but its implementation is really confusing. I have tried to write a program for quick sort with some help of textbook but the program has some logical error and am not able to find it out.
Can you help it out.The code is:
Code:
```#include<stdio.h>
#include<stdlib.h>
void printlist(int *x,int n);
void quicksort(int *x,int lower,int upper);
void swap(int *a,int *b);
int main()
{
int *arr,n,i,resp;
printf("\nHOW MANY ELEMENTS?\t");
scanf("%d",&n);
arr=(int*)malloc(n*sizeof(int));
printf("\n\nWOULD YOU LIKE TO GENERATE NUMBERS RANDOMLY OR YOURSELF?\n");
printf("PRESS 1 FOR RANDOM NUMBERS\n      2	FOR INPUTTING NUMBERS\n");
gen:
scanf("%d",&resp);
switch(resp)
{
case 1:
printf("\nOK THEN. NOW GENERATING RANDOM NUMBERS.....\n");
for(i=0;i<n;i++)
{
arr[i]=rand()/100;
//printf("\nELEMENT NO. %d:\t%d ",i+1,arr[i]);
}
break;
case 2:
for(i=0;i<n;i++)
{
printf("\nELEMENT NO. %d: ",i+1);
scanf("%d",&arr[i]);
}
break;
default:
printf("\nERROR-UNEXPECTED INPUT");
goto gen;
break;
}
printf("\n\nTHE LIST BEFORE SORTING IS(UNSORTED LIST):\n");
printlist(arr,n);
quicksort(arr,0,n-1);
printf("\n\nTHE LIST AFTER SORTING IS(SORTED LIST):\n");
printlist(arr,n);
return 0;
}

void printlist(int *x,int n)
{
int i;
for(i=0;i<n;i++)
{
printf("%d  ",x[i]);
}
}
void quicksort(int *x,int lower,int upper)
{
int lo,hi,i,pivot;
pivot=x[lower];
lo=lower+1;
hi=upper;
while(lo<=hi)
{
while(x[lo]<pivot)
lo++;
while(x[hi]>pivot)
hi--;
if(lo<hi)
swap(&x[lo],&x[hi]);
}
swap(&x[lower],&x[hi]);
quicksort(x,lower,hi-1);
quicksort(x,hi+1,upper);
return;
}
void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}```
Can u find out any fault in the code???

2. Not sure if you're qsort'ng the array index or the contents?
Code:
```if(lo<hi)
swap(&x[lo],&x[hi]);```

3. Originally Posted by itCbitC
Not sure if you're qsort'ng the array index or the contents?
Code:
```if(lo<hi)
swap(&x[lo],&x[hi]);```
But that doesn't seems to be the part of the problem. I tried it out but no effect....

4. Originally Posted by rakeshkool27
But that doesn't seems to be the part of the problem. I tried it out but no effect....
What did you change it to?

5. Originally Posted by tabstop
What did you change it to?
I changed to x[lo]<x[hi].

6. Originally Posted by rakeshkool27
I changed to x[lo]<x[hi].
What you had the first time is correct -- lo points to the first high element in the low half, and hi points to the last low element in the high half, and as long as lo hasn't passed hi (i.e., if lo < hi) you want to swap.

Also at some point you need to do a "hey I'm out of data" check -- running your code led to a segfault when the recursive call reached lower = 0, upper = -2389.

7. Change the hi in red, to lo. I'd also add the //added statement.

I put a big question mark on that last call to swap(), before the recursive calls, because you didn't actually move the pivot, so you don't need to replace it.

Also, when you call swap, I would use just the same parameters you are using for quicksort() - the name of the array(which is an address), and two INDECES. NOT addresses, or values, but indeces!

Code:
```//Your code:
void quicksort(int *x,int lower,int upper)
{
int lo,hi,i,pivot;
return;
pivot=x[lower];
lo=lower+1;
hi=upper;
while(lo<=hi)
{
while(x[lo]<pivot)
lo++;
while(x[hi]>pivot)
hi--;
if(lo<hi)
swap(x, lo,hi);
}
//?????   =====>>>  swap(x, lower, hi);  //Why?
if(lower < hi) quicksort(x,lower,hi-1);
if(lo < upper) quicksort(x,hi+1,upper);
return;
}

//88888888888888888888
//Quicksort
void quicksort(int A[], int lo, int hi) {
int i, j, pivot, temp;

if(lo == hi) return;
i=lo;
j=hi;
pivot= A[(lo+hi)/2];

/* Split the array into two parts */
do {
while (A[i] < pivot) i++;
while (A[j] > pivot) j--;
if (i<=j) {
swap(A, i, j);   //this line works fine.

/*
temp= A[i];
A[i]= A[j];
A[j]=temp;
^^^^^ This is what your swap function should be doing
*/
i++;
j--;
}
} while (i<=j);

if (lo < j) quicksort(A, lo, j);
if (i < hi) quicksort(A, i, hi);
}```
The idea behind Quicksort is simple, but it is "brittle" - very easy to break. I applaud your version of it, however. I've seen some real doozie's lately - barely recognize them as Quicksort, at all.

8. It can help if you break it up into separate steps:
• Checking for an array that is too small to need to do anything with
• Picking a pivot point
• Partitioning according to the pivot (which has swapping as a sub-task)
• Performing the recursive calls

Each one of these points can be written on its own and tested in isloation. You can get each bit correct and then start putting them together.