Richtig Partitionieren QuickSort Array

Question

Ich bin ein Anfänger in C und ich habe versucht, ein Quicksort-Programm, das eine zufällig generierte Reihe von reellen Zahlen und seine Größe als Argument nehmen kann, und sortiert dann die Elemente in aufsteigender Reihenfolge . Ich kann nicht herausfinden, was im ersten rekursiven Aufruf der Funktion QuickSort, die das Subarray A [0 ... q-1] darstellen soll, in das Array-Größenfeld geschrieben werden soll. Soweit ich das beurteilen kann, ist der Rest des Codes in Ordnung, denn wenn er mit einem Treiberprogramm verknüpft wird, das die Zufallszahlen erzeugt, gibt das Programm die Elemente zurück, wenn auch in der falschen Reihenfolge. Ich schätze jede Hilfe/Vorschläge.

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 1

Sie einziges Problem ist, sind Sie scheinen zu verwechseln:

A[i]=something; 

mit Swapping A[i] und something. Fügen Sie einen Hilfs-tmp hinzu oder schreiben Sie eine Tauschfunktion:

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