C Quicksort

#1
Hallo zusammen!

Ich versuche meine eigene Quicksort Funktion in C zu schreiben. Allerdings weiß ich gerade einfach nicht mehr weiter ( suche den Fehler seid mehreren Stunden...) Vielleicht sehe ich nach der ganzen Zeit auch den Wald vor lauter Bäumen nicht mehr und finde den Fehler deshalb nicht.

Ich lass den Code einfach mal hier und falls wer Lust hat, kann er ja mal drüber schauen :) (mir reichts grad nämlich...)
Bei manchen eingaben funktioniert alles, bei anderen leider nicht...

C:
int Feld[100];
void Quicksort(int links, int rechts){
 int i,j,x,save;

 i = links;
 j = rechts;
 x = Feld[(links+rechts) / 2];

 while (Feld[i] < x) {
   i = i + 1;
 }
 while (x < Feld[j]) {
   j = j - 1;
 }

do {
 if (i <= j){

  save = Feld[i];
  Feld[i] = Feld [j];
  Feld[j] = save;
  i=i+1;
  j=j-1;
}}
while (i < j);


if (links < j){
  Quicksort(links, j);
}

if (i < rechts){
  Quicksort(i, rechts);
}

return;

}


int main()
{
    int i=0, j=0;

    /* Einlesen der Liste */
    do
    {

        printf("Bitte geben Sie eine Zahl ein oder Null zum Abbruch: ");
        scanf("%i", &Feld[i]);

        if (Feld[i] == 0)  break;

        ++i;

    } while (i < 100);

    /* Sortieren der Liste */
    Quicksort(0, i-1);

    /* Ausgeben der sortierten Liste */
    for(j = 0; j < i-1; ++j)
    {
        printf("%i  ", Feld[j]);
    }

    printf("%i\n", Feld[i-1]);

    return 0;
}
 

BAGZZlash

Well-Known Member
c-b Experte
#2
Ohne jetzt genau über den Algo geschaut zu haben: Hast Du mal gecheckt, ob Essensreste vielleicht ein Problem sind?

/edit: Okay, das war's nicht. Ich hab's mir jetzt mal angesehen. Hm, ich muss zugeben, dass ich nicht bei jedem Deiner Schritte die Intention verstanden habe. Gerne hätte ich Dich auf diesen einen Fehler aufmerksam gemacht, den Du noch drin hast, dazu bin ich aber nicht gekommen. Stattdessen habe ich das Ding mehr oder weniger nach und nach neu implementiert, was vielleicht nicht gerade das ist, was Du willst. Na gut, hier trotzdem mal, was ich gebastelt habe:

C:
#include <stdio.h>

int Feld[100];

void Quicksort(int links, int rechts)
{
    int i, j, x, save;

    if (links < rechts)
    {
        i = links;
        j = rechts;
        x = links;
    
        while (i < j)
        {
            while (Feld[i] <= Feld[x] && i < rechts) i++;
            while (Feld[x] < Feld[j]) j--;       
            
            if (i < j)
            {
                save = Feld[i];
                Feld[i] = Feld[j];
                Feld[j] = save;
            }
        }
        
        save = Feld[x];
        Feld[x] = Feld[j];
        Feld[j] = save;
    
        Quicksort(links, j - 1);
        Quicksort(j + 1, rechts);
    }
}

int main()
{
    int i = 0, j = 0;

    /* Einlesen der Liste */
    /*do
    {
        printf("Bitte geben Sie eine Zahl ein oder Null zum Abbruch: ");
        scanf("%i", &Feld[i]);
        while (getchar() != '\n');

        if (Feld[i] == 0) break;

        ++i;
    } while (i < 100);*/
    Feld[0] = 9;
    Feld[1] = 1;
    Feld[2] = 8;
    Feld[3] = 2;
    Feld[4] = 7;
    Feld[5] = 3;
    Feld[6] = 6;
    Feld[7] = 4;
    Feld[8] = 5;
    i = 9;

    /* Sortieren der Liste */
    Quicksort(0, i - 1);

    /* Ausgeben der sortierten Liste */
    for(j = 0; j < i; ++j) printf("%d  ", Feld[j]);

    return(0);
}
 
Zuletzt bearbeitet:
#3
Hey,
ja ich muss sagen ich kann jetzt auch manche schritte von mir nicht mehr nachvollziehen ^^...

Wenn ich zulange an einem Code rumbastel finde ich mich oft selber nicht mehr zurecht. Ganz zu schweigen das es irgendwann alles schrecklich aussieht vom ganzen einfügen und rumprobieren... (Bin ziemlicher Anfänger im Bereich Coding)

Auf jeden Fall vielen Dank für deine Mühe!!! Das mit den Essensresten fand ich trotzdem ziemlich interessant!
 
Oben