Problem beim Quicksort-Algorithmus in C

[cmann]

Hallo Leute,

ich habe die Aufgabe bekommen ein zweidimensionales int Array, das zufällig mit rand() gefüllt wird, mit dem Quicksort-Verfahren zu sortieren.
Wie viele Zahlen mit rand() erstellt werden soll durch die Konstante X_SIZE bestimmt werden können.
Ein kleines Bsp. wie die Ausgabe des Arrays vor und nach dem Sortieren aussehen soll, findet ihr im Anhang.

Grundsätzlich funktioniert mein Programm. Allerdings ergibt sich ein merkwürdiges Problem.
Wenn X_SIZE auf 10 gesetzt wird passt alles...aber sobald ich X_SIZE größer oder kleiner 10 setze sortiert Quicksort falsch.

Hat jemand eine Idee woran das liegen könnte? Google spuckt nichts aus und ich bin mit meinem (recht spärlichen) Latein am Ende

LG Kai

Hier der Code:

Main:

Code: Alles auswählen

#include "print_array.h"
#include "quicksort.h"

int main() {
    int puffer[X_SIZE][DIMENSIONS];
    int k = 1;
    for (int i = 0; i < X_SIZE; i++) {
        puffer[i][0] = k;
        puffer[i][1] = rand();
        k++;
    }
    printf("\n");
    print_array(puffer);
    quicksort(puffer, 0, X_SIZE);
    print_array(puffer);
    return 0;
}

Quicksort:

Code: Alles auswählen

#include "defines_includes.h"

void quicksort(int puffer[][DIMENSIONS], int start, int end){
    int i, j, x, y, z;
    i = start;
    j = end-1;
    x = puffer[(start+end)/2][1];
    do {
        while (puffer[i][1] < x && i < end)i++;
        while (x < puffer[j][1] && j > start)j--;

        if (i <= j) {
            y = puffer[i][1];
            z = puffer[i][0];
            puffer[i][1] = puffer[j][1];
            puffer[i][0] = puffer[j][0];
            puffer[j][1] = y;
            puffer[j][0] = z;
            i++;
            j--;
        }
    }while(i<=j);

        if(start<j) quicksort(puffer, start, j);
        if(i<end) quicksort(puffer, i, end);

}

Ausgabe des Arrays (print_array):

Code: Alles auswählen

#include "defines_includes.h"

void print_array(int puffer[][DIMENSIONS]){
    printf("Index\tZufallszahl\n");
    for (int m = 0; m < X_SIZE; m++) {
        for (int n = 0; n < DIMENSIONS; n++) {
            printf("%d\t\t", puffer[m][n]);
        }
        printf("\n");
    }
    printf("\n");
}

Includes & defines:

Code: Alles auswählen

#include <stdlib.h>
#include <stdio.h>

#define DIMENSIONS 2
#define X_SIZE 10

[cmann]

EDIT: Habe der Quicksort-Funktion nun X_SIZE-1 als end übergeben und in der Funktion selbst das j=end-1 wieder zu j=end geändert und es läuft einwandfrei. Aber vielleicht kann mir ja jemand erklären wieso es einen Unterschied macht ob ich die übergebene Variable in der Funktion ändere oder bevor ich sie der Funktion übergebe?

LG

[nufan]

Hallo cmann

Habe der Quicksort-Funktion nun X_SIZE-1 als end übergeben und in der Funktion selbst das j=end-1 wieder zu j=end geändert und es läuft einwandfrei. Aber vielleicht kann mir ja jemand erklären wieso es einen Unterschied macht ob ich die übergebene Variable in der Funktion ändere oder bevor ich sie der Funktion übergebe?

Du verwendest "end" nicht nur zur Bestimmung von "j", sondern auch zur Berechnung des Pivot-Indexes sowie in verschiedenen Bedingungen. Außerdem wird die Subtraktion innerhalb der Funktion in jedem Rekursionsschritt ausgeführt. Falls du bereits in "main" den Wert abziehst, passiert das nur ein einziges Mal.

Falls du sie noch nicht gesehen hast, gibt es übrigens auch in unserem Wiki eine Erklärung zu Quicksort mit Beispielcode:
https://www.proggen.org/doku.php?id=algo:quicksort

[jomaber]

Es ist bestimmt sinnvoll, selbst einmal einen Sortieralgorithmus zu programmieren. Mir fehlt hier an dieser Stelle der Hinweis auf die Standardfunktion qsort(), der lediglich eine Vergleichsfunktion zur Verfügung gestellt werden muss.

Code: Alles auswählen

int cmp(const void *frst, const void *scnd)
{
    int rc = 0;
    int (*f)[DIMENSIONS] = ( int (*)[DIMENSIONS]) frst;
    int (*s)[DIMENSIONS] = ( int (*)[DIMENSIONS]) scnd;

    if ( ((*f)[1]>(*s)[1]) )
        rc = 1;
    if ( ((*f)[1]<(*s)[1]))
        rc = -1;
    return rc;
}

int main()
{
    int puffer[X_SIZE][DIMENSIONS];
    init_array(puffer);
    qsort(puffer, sizeof puffer/ sizeof puffer[DIMENSIONS], sizeof puffer[DIMENSIONS], cmp);
    print_array(puffer);

    exit(EXIT_SUCCESS);
}