Heapsort auch Richtigkeit überprüfen

chin842

Hallo,

ich hab ein kleines Programm geschrieben, dass einen Array mit dem Heapsort verfahren sortiert.
Wie kann ich aber überprüfen lassen, ob der Heapsort richtig war und richtig sortiert hat?
am besten auch durch eine funktion, die mir dann ausgibt richtig und falsch.
irgendwie mit ner schleife, die jedes mal überprüft ob i>i-1 ? so was in die richtung und dann durchlaufen lassen?

Hier noch der Code, aber tut ja eigentlich nix zur sache

void siftdown(int a[], int n, int i){ 
int j, h=a[i];
if(i<0) return; 
while(i<n/2){ 
j=i+i+1; 
if(j+1<n && a[j]<a[j+1]) 
j++; 
if(h>=a[j]) 
break; 
a[i]=a[j]; i=j; 
}
a[i]=h;
}

void buildheap(int a[], int n){
int i;
for(i=n/2-1; i>=0; i--){
siftdown(a,n,i);

}}

void heapsort(int a[], int n){
int i, tmp;
buildheap(a,n);
for(i=n-1; i>=0; i--){
tmp=a[0]; a[0]=a[i]; a[i]=tmp;
siftdown(a,i,0);
printf("\nheap=%d, n=%d, i=%d",a[i],n,i);
}}

int main (int argc, const char * argv[]) {
const int n = 8;
int array[] = {3,5,1,8,2,4,7,6};
heapsort (array, n);
getchar();
return 0;

}

volkard

Ganz genau.

for(;;){
   int size=rand()%1000;
   int* data=new int[size];
   fillRandom(data,size);
   sort(data,size);
   if(!isSorted(data,size))
      panic();
   delete[] data;
}

volkard schrieb:

Ganz genau.

for(;;){
   int size=rand()%1000;
   int* data=new int[size];
   fillRandom(data,size);
   sort(data,size);
   if(!isSorted(data,size))
      panic();
   delete[] data;
}

Wir befinden uns im ANSI C-Forum.

Letzendlich sollte Volkards Intention aber auch für einen C Programmierer verständlich sein.
Du lässt eben einfach zufällige Listen sortieren. Sollte dabei ein Fehler auftreten (Liste nicht vollständig sortiert), so ist dein Algorithmus falsch.

volkard

ioioioi schrieb:

Wir befinden uns im ANSI C-Forum.

Ups, war keine Absicht. In C ist es vermutlich

for(;;){ 
   int size=rand()%1000; 
   int* data=malloc(size*sizeof(int)); 
   fillRandom(data,size); 
   sort(data,size); 
   if(!isSorted(data,size)) 
      panic(); 
   free(data); 
}

Aber ich wollte ja nur die generelle Vorgehensweise zeigen, die ich da nehmen würde, egal, welche Sprache, auch bei Basic, Pascal und Java teste ich immer gegen sauviele Zufallszahlen und seit 10 Jahren flutscht kein Fehler mehr durch bei sowas. Damals hatte ich einen bösen Flutschi, als ich noch so doof war, die Arraygröße konstant zu lassen (obwohl ich gegen Milliarden von Zufallszahlen gestestet hatte). Uih, das dürfte ich gar nicht erzählen, wenn Ihr nicht alle meine Freunde wärt. Mehr als 9 Monate blieb der Fehler unentdeckt. Uih, hab ich mich danach peinlich berührt gefühlt.

namespace invader

volkard schrieb:

if(!isSorted(data,size))

Das testet aber nur, ob das Ergebnis sortiert ist, und nicht, ob es tatsächlich das sortierte Eingabearray ist; eine kaputte Sortierfunktion könnte etwa leicht Elemente verdoppeln oder verschwinden lassen.

Und bestimmte Dinge werden durch so ein Array aus Zufallszahlen auch nicht getestet, z.B. wird man mit zufälligen 64-Bit-Integern fast nie ein Array mit einer mehrfach vorkommenden Zahl, oder auch INT_MIN oder INT_MAX bekommen.

Hier ist ein lesenswerter Artikel zum Testen von Sortierfunktionen: What does it take to test a sorting routine?

(Und natürlich: Testing is not a substitute for thinking)

chin842

danke
angenommen ich hab einen array der länge n=20 und ist auch schon belegt

for(i=0;i<=n;i++){
   int size=rand()%1000;
   int* data=malloc(size*sizeof(int));
    heapsort(array,n);
   if(!isSorted(array,n))
      panic();
   free(array);
}

ist auf den code oben bezogen

isSorted und panic sind dann noch funtionen nehm ich an?

Danke für Hilfe!

chin842

int i;
     for(i=0; i<n; i++){
              if (array[i]>array[i+1]){
                 printf("\nnicht sortiert");
                 return 0;
                 }
              }
     printf("\nsortiert");

habs jetzt so gelöst

Wutz

Geht davon aus, dass array n+1 Elemente besitzt statt n.
Funktioniert nicht für array, wenn 1 Elementwert doppelt vorkommt.

chin842

das stimmt, n-1, hatte ich schon geändert auch, aber danke
der fall das 1 element doppelt vorkommt sollte ich nicht berücksichtigen da die elemte von sich verschiedene sein müssen im array.