Fehler im Quicksort - Dringend!

BeatSampras

hi!

ich bräuchte dringend hilfe. ich soll einen Quicksort schreiben, der nur auf Zeigern basiert und keine Indizies verwendet. Hab ich auch gemacht. Allerdings sortiert er nicht zu Ende. Das Ergebnis sieht immer so aus, als müßte er das ganze noch ein paar mal durchgehen.
Bis zur Feldlänge von 10 sortiert er richtig, danach ist Schluß.

Eine Antwort wäre super!!! Danke schon mal im voraus!

Thomas

Hier ist der Quelltext.

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

void randomize(void);
int quicksort(int*, int*);
void ausgabe(int [],int);

void main (void) {
   int c;
   int temp=0;
   int laenge;
   int *a;

   cout<<"Bitte geben sie die Feldgroesse ein!"<<endl;
   do {
   	cin>>laenge;
   } while(laenge<=0);

   a = (int *)malloc(laenge*sizeof(int));

   if(a==NULL) {
   	cout<<"Auf dem Datentraeger ist nicht genuegend Speicherplatz vorhanden!"<<endl;
      exit(-1);
   }

     	for(int i=0;i<laenge;i++)
  		*(a+i) = random(101);

   cout<<"Das Feld vor der Sortierung"<<endl;
   ausgabe(a,laenge);

   c = quicksort(&a[laenge-laenge],&a[laenge-1]);

   cout<<endl<<"Das Feld NACH der Sortierung"<<endl;
   cout<<"Durchlaeufe : "<<c<<endl;
   ausgabe(a,laenge);
  	getch();
}

int quicksort (int *plo, int *phi)
  	{
      int *pi=plo;
      int *pj=phi;
      int temp;
      int c=0;
      int anzahl=0;

      for(int i=0;(plo+i)<phi;i++)
      	anzahl++;

      char *x = plo+((anzahl)/2);

      //  Aufteilung
      while (pi<=pj)
      {
        while (*pi<*x) pi++;
        while (*pj>*x) pj--;

        if (pi<=pj)
        {
            temp=*pi;
            *pi=*pj;
            *pj=temp;
            pi++; pj--;
            c++;
         }
      }

      // Rekursion
      if (plo<pj) quicksort(plo, pj);
      if (pi<phi) quicksort(pi, phi);

      return c;
}

void ausgabe(int a[],int laenge) {
	for(int i=0;i<laenge;i++) {
   	cout.width(2);
   	cout<<i;
   	cout.width(5);
   	cout<<a[i]<<endl;
   }
}

AJ

Nach langem Grüblen denke ich, dass ich weiß woran es liegt.

Geh mal von dem Fall aus, dass pi und pj genau auf die gleiche Adresse wie x stehen und dann geh mal deine Schleife im quicksort durch. Schreib dir am besten irgendwelche Werte für die drei Variablen auf und verändere sie so, wie sie dein Programm verändert, dann solltest du drauf kommen

Aja nochwas:

1. &a[laenge-laenge] => auch Umwege führen zum Ziel, oder wie??
Da kann man auch einfach a schreiben. Ist 1. kürzer und 2. besser lesbar und verständlicher.

2. for(int i=0;(plo+i)<phi;i++)
anzahl++;
=> Eine Zählschleife, die gleich zwei Zähler hochzählt und nur dazu dient die Anzahl zu ermitteln
Wie wärs mit anzahl = phi - plo; ? Ist 1. kürzer (ich scheine mich zu wiederholen) und 2. bremst du dadurch auch nicht den Quicksort aus

BeatSampras

hi!

danke, daß du geantwortet hast. ich habe heute den fehler gefunden. ich weiß nicht, ob du das gemeint hast, was ich jetzt geändert hab.

x ist jetzt kein zeiger mehr, sondern ein zahlenwert und sieht jetzt so aus:

int x = *(plo+(anzahl/2));

schlimm, was so ein kleines sternchen alles anrichten kann....

thomas

AJ

Stimmt das ist auch ein Problem. Der Wert von x verändert sich ja, wenn x auf eine Adresse in dem Array zeigt.