Quicksort Code in C

[dulfried (Gast)]

hallo miteinander,

hat mit jemand den C-code für einen quicksort?

Alternativ: könntet ihr mir verraten, was an meinem falsch ist?

---------------------------------------------------------------------

int* quicksort  (int *feld, int index)
{

  int buffer = 0;
  int pivot = 0;
  int *pointer_kl;
  int *pointer_gr;
  int versatz = 0;

  if (index > 0)
  {
    pivot = feld[index/2];
    pointer_kl = feld + index;
    pointer_gr = feld;

    do
    {
      while (*pointer_gr<=pivot && pointer_gr != pointer_kl)
      {
        pointer_gr++;
      }

      while (*pointer_kl>=pivot && pointer_kl != pointer_gr)
      {
        pointer_kl--;
      }

      buffer = *pointer_gr;
      *pointer_gr = *pointer_kl;
      *pointer_kl = buffer;

    } while (pointer_gr<pointer_kl);

    versatz = pointer_gr - feld;

    if (versatz > (index/2) && feld[versatz] > pivot)
    {
      versatz = versatz-1;
    }

    feld[index/2] = feld[versatz];
    feld[versatz] = pivot;

    quicksort(feld, (versatz - 1));              //Rekursion
    quicksort(feld + (versatz + 1), index - (versatz + 1));
  }

  else
  {
    return feld;
  }


}

---------------------------------------------------------------------

[dulfried (Gast)]

Anmerkung: index=anzahl-1;

[alesi (Gast)]

dulfried schrieb:
> hat mit jemand den C-code für einen quicksort?

Suchmaschine: "quicksort in c"

http://de.wikibooks.org/wiki/Algorithmen_und_Datenstrukturen_in_C/_Quicksort

http://rosettacode.org/wiki/Sorting_algorithms/Quicksort

[Purzel H. (hacky)]

Und dann gaeb's noch den Debugger im Single Step Mode ....

[Klaus W. (mfgkw)]

... oder eine vernünftige Beschreibung, was nicht funktioniert?

[hp-freund (Gast)]

Klaus Wachtler schrieb:
> ... oder eine vernünftige Beschreibung, was nicht funktioniert?

Gute Frage. Habs zum Spass in ein Prog gepackt und es funktioniert.
Ich habe aber nicht getestet ob es wirklich max. "quick" ist.

[Klaus W. (mfgkw)]

Vielleicht ist es irgendwo aus dem Internet kopiert.
Aber danke fürs Testen :-)

[Torsten R. (Firma: Torrox.de) (torstenrobitzki)]

Es gibt doch die Funktion qsort() in der C Library. 
http://en.wikipedia.org/wiki/Qsort

[dulfried (Gast)]

stimmt habe den quicksort seperat ausprobiert und der funktioniert, dann 
muss der fehler an meiner main oder an der übergabe liegen.
Hier ist mal der komplette code, hoffe ihr erkennt den Fehler.

Wenn ich mir die zahlen ausgeben lassen kommen immer extrem hohe werte 
raus(werden wohl die adressen sein):

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


int* quicksort(int *feld, int index)
{
  int buffer = 0;
  int pivot = 0;
  int *pointer_kl;
  int *pointer_gr;
  int versatz = 0;

  if (index > 0)
  {
    pivot = feld[index / 2];
    pointer_kl = feld + index;
    pointer_gr = feld;

    do
    {
      while (*pointer_gr <= pivot && pointer_gr != pointer_kl)
      {
        pointer_gr++;
      }

      while (*pointer_kl >= pivot && pointer_kl != pointer_gr)
      {
        pointer_kl--;
      }

      buffer = *pointer_gr;
      *pointer_gr = *pointer_kl;
      *pointer_kl = buffer;

    } while (pointer_gr<pointer_kl);

    versatz = pointer_gr - feld;

    if (versatz >(index / 2) && feld[versatz] > pivot)
    {
      versatz = versatz - 1;
    }

    feld[index / 2] = feld[versatz];
    feld[versatz] = pivot;

    quicksort(feld, (versatz - 1));              //Rekursion
    quicksort(feld + (versatz + 1), index - (versatz + 1));


  }

  else
  {

    return feld;
  }
}

void ausgabe(int *zahlen, int anzahl){
  for (int z = 0; z < anzahl; z++){
    printf("%d\n", zahlen[z]);
  }
}

int main()
{
  int anzahl, auswahl, min, max, index;
  int *zahlen, *fertig;

                  // Bedingungen festlegen
                  printf("Mit diesem Programm können Sie verschiedene 
Sortieralgorithmen verwenden\n\n");
                  printf("Geben Sie die Gr\x94sse des Feldes an:\n");
                  scanf("%d", &anzahl);

                  printf("Geben Sie den Zahlenbereich an:\n");
                  printf("Untere Grenze: ");
  ^dieser teil stimmt^      scanf("%d", &min);
                  printf("Obere Grenze: ");
                  scanf("%d", &max);


                  // Zahlen per Zufall aussuchen
                  zahlen = (int*)malloc((anzahl)* sizeof(int));

                  for (int i = 0; i < anzahl; i++){
                    zahlen[i] = rand() % ((max + 1) - min) + min;
                  }

  //sortieren
    index = anzahl - 1;
    fertig = quicksort(zahlen, index);
    ausgabe(fertig, anzahl);



  system("pause");
  return 0;
}

-------------------------------------------------------------------

[dulfried (Gast)]

Habe den Fehler gefunden !!!!!!!!!!!!!!!!!!!


Dies funktioniert nicht:

fertig = quicksort(zahlen, index);
for (int i = 0; i<anzahl; i++)printf("index:%3d\t\twert:%d\n", i, 
fertig[i]);

 Lösung:

quicksort(zahlen, index);
for (int i = 0; i<anzahl; i++)printf("index:%3d\t\twert:%d\n", i, 
zahlen[i]);


Wäre aber nett, wenn mir jemand erklären könnte, warum nur die untere 
Variante funktioniert

Mfg dulli

[Narfie (Gast)]

Kein return im if-Teil deines Quicksort...

[DirkB (Gast)]

Sollte aber der Compiler als Warnung anmeckern.

[Narfie (Gast)]

Deshalb ist die Option -Wall nicht schlecht zum Entwickeln.

[Mark B. (markbrandis)]

Narfie schrieb:
> Deshalb ist die Option -Wall nicht schlecht zum Entwickeln.

Die ist nie schlecht. :)