Stavo - 9 months ago 69

C Question

I'm a beginner in C and I've been trying to code a Quicksort program that can take a randomly generated array of real numbers and its size as its argument, and then sorts the elements in ascending order. I cannot figure out what to put in the array size field in the first recursive call of the function QuickSort, which is meant to represent the subarray A[0...q-1]. As far as I can tell, the rest of the code is fine because when linked to a driver program that generates the random numbers, the program returns the elements, albeit in the incorrect order. I appreciate any help/suggestions.

`int Partition(float *,int);`

int QuickSort(float *A,int n)

{

int q;

if(n>1){

q = Partition(A,n);

QuickSort(&A[],q); //Trying to figure out what to put in here.

QuickSort(&A[q+1],(n-1)-q); //This recursion sends the subarray A[q+1...n-1] to QuickSort, I think it works fine.

}

}

int Partition(float *A,int n){

int i,j;

float x;

x = A[n-1];

i=0;

for(j=0;j<=n-2;j++){

if(A[j] <= x){

A[i]=A[j];

i = i+1;

}

}

A[i]=A[n-1];

return i;

}

Answer Source

You're only problem is you seem to confuse:

```
A[i]=something;
```

with swapping `A[i]`

and `something`

. Add an auxiliary tmp, or write a swap function:

```
#include<stdio.h>
int Partition(float *,int);
void QuickSort(float *A,int n) {
int q;
if(n>1){
q = Partition(A,n);
QuickSort(A,q); //Trying to figure out what to put in here.
QuickSort(A+q+1,(n-q-1)); //This recursion sends the subarray A[q+1...n-1] to QuickSort, I think it works fine.
}
}
int Partition(float *A,int n){
int i,j;
float x;
float tmp;
x = A[n-1];
i=0;
for(j=0;j<=n-2;j++){
if(A[j] <= x){
tmp = A[i];
A[i]=A[j];
A[j]=tmp;
i = i+1;
}
}
tmp = A[i];
A[i]=A[n-1];
A[n-1]=tmp;
return i;
}
int main() {
float A[] = {3, 4, -5, 10, 21, -9, -1, 7, 8, 10};
QuickSort(A,10);
for(int i = 0; i < 10; i ++)
printf("%f ",A[i]);
return 0;
}
```