Stavo - 1 year ago 87
C Question

# Properly Partitioning QuickSort Array

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;
}
``````

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;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download