# Thread: HELP me with my Qsort Program

1. ## HELP me with my Qsort Program

Code:
```#include <stdio.h>
#define maxsize 10

void quicksort (int a, int b);
//void mergesort ();

float ES26[11];
int i, j, k, x=1, mean, median, mode;
float *ptr, sum;

int main ()
{
printf("Input at most 10 floating point numbers, each entry followed by ENTER. \nInput 0 if you want to stop:\n");
for (i=1, j=1; j==1 || i==10; i++)
{
printf("%d) ", i);
scanf("%f", &ES26[i]);
ptr=&ES26[i];

if (*ptr==0)
{
x=i-1;
j=2;
}
if (i==10)
{
x=i;
j=2;
}
}

if (x==2 || x==4 || x==6 || x==8 || x==10)
{
printf("\nYou entered %i valid entries.", x);
ptr = &ES26[i];
quicksort(0, x-1);

printf("\nSupposed to Quicksort.");
}

if (x==1 || x==3 || x==5 || x==7 || x==9)
{
printf("\nYou entered %i valid entries.", x);
//meregesort

printf("\nSupposed to Mergesort.");
}

//ptr = &ES26[i];

for (i=1; i<=x; i++) //for printing
{
ptr=&ES26[i];
printf("\nEntry %i is %f", i, *ptr);
sum = sum + *ptr;
}
printf("\nThe mean is %f", sum/x);

getchar();
getchar();
getchar();
getchar();
}

void quicksort(int a, int b)
{
ptr=&ES26[a];
//*ptr=ES26[a];
int rtidx=0, ltidx=0, k=a, l=0;
float leftarr[maxsize], rtarr[maxsize];
//float pivot = ES26[a];

if (a==b) return;
while (k<b)
{
++k;

if(ptr[k] < ptr[a])
{
leftarr[ltidx] = ptr[k];
ltidx++;
}

else
{
rtarr[rtidx] = ptr[k];
rtidx++;
}
}

k=a; //reset k to a

*ptr=ES26[a];
for(l=0; l<ltidx; ++l)

ptr[k++] = leftarr[l];
ptr[k++] = *ptr;

for(l=0; l<rtidx; ++l)
ptr[k++] = rtarr[l];

if(ltidx>0)
quicksort(a, a+ltidx-1);

if(rtidx>0)
quicksort(b-rtidx+1, b);
}```
here is an example of what I get if i run my program:

Input at most 10 floating point numbers, each entry followed by ENTER.
Input 0 if you want to stop:
1> 11.23
2> 43.553
3> 196.4673
4> 0.8874
5> 23.67
6> 90.5
7> 0

You entered 6 valid entries.
Supposed to Quicksort.
Entry 1 is 11.230000
Entry 2 is 11.230000
Entry 3 is 23.670000
Entry 4 is 11.230000
Entry 5 is 196.467300
Entry 6 is 90.500000

Can somebody help me point out where the mistake is? Thanks a lot!

2. Let's start with a nice Quicksort example, and I strongly suggest you use this as a template for any Quicksort program you use, in the future. It's clear, it's FAST, and easy to optimize further, if you desire.

Code:
```//Quicksort w/o a separate compare function :)
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--;
/*swap(A, i, j);   //this line works fine, if you want a separate swap function.
Oddly, on large N, using swap() gives the same time, as
using the swap code below
*/
if (i<=j) {        //we need to swap two values
temp= A[i];
A[i]= A[j];
A[j]=temp;
i++;
j--;
}
} while (i<=j);

/* select the smaller sub array to finish sorting, first - prevents stack overflow */
if (lo < j) quicksort(A, lo, j);
if (i < hi) quicksort(A, i, hi);
}```
What do you notice, right off - there are very few variables involved:

i, j, pivot, and temp, and that's it. Just the required 3 parameters for the function.

There are no pointers involved - other than the array name, which is being passed in (so it's always a pointer). The compiler will handle the pointer conversions that are used by C, "under the hood". For heaven's sake, as a beginner, don't go there!

You don't need (and shouldn't use), auxiliary arrays (left and right arrays in your code), in Quicksort. That just throws more data, out of the fast cache memory, and again, make the programming waters, murky. You're thinking of a version of Merge sort - and this is no Merge sort.

<< This is Sparta!! >>

OK, back to the program.

Try this Quicksort template, and you'll soon have it working for you. Glad to assist there.

3. You'll no doubt learn the most by stepping through your own code.
Start learning to use your debugger. You cant get very far in programming without learning how to use a debugger.

If you have trouble doing that, tell us what you're using and what the problem is.