Stavo Stavo - 1 month ago 17
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;
}

Answer

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