Heapsort
-
Hallo,
habe ein Problem beim "Anhalten" des Programms, das Programm läuft auch, aber trotz des getch(); schließt sich das Konsolenfenster gleich wieder. Auch mit System("PAUSE"); bekomme ich kein anderes Ergebnis... Wahrscheinlich nur eine Kleinigkeit... Fehler liegt sicher ganz unten im Main Programm. Ich hoffe ihr könnt mir helfen! Danke schonmal!
/* Christian Günther, Matr.-Nr. 121099 */ #include <stdio.h> #include <stdlib.h> void siftdown(int a[], int n, int i){ //i ist Index des zu siebenden Elementes int j, h=a[i]; if(i<0) return; // wenn i ungueltig, dann abbrechen while(i<n/2){ // solange noch Soehne vorhanden sind j=i+i+1; // setze Vergleichselement j auf linken Sohn von i if(j+1<n && a[j]<a[j+1]) // wenn rechter Sohn groesser linkem,... j++; // ... dann dieser als j setzen if(h>=a[j]) // wenn Heap-Ordnung hergestellt, break; // ...dann abbrechen a[i]=a[j]; i=j; // Element im Heap nach unten sieben } a[i]=h; // Element an Endposition einordnen } void buildheap(int a[], int n){ // In einer Schleife siftdown aufrufen int i; for(i=0; i<=7; i++) siftdown(a,n,i); printf("\n Heap=%d, n=%d, i=%d",a[i],n,i); } void heapsort(int a[], int n){ // // buildheap aufrufen buildheap(a,n); // In einer Schleife Elemente vertauschen und siftdown aufrufen } int main (int argc, const char * argv[]) { int i; const int n = 20; int array[] = {11,92,23,84,35,76,47,68,59,17,39,55,29,3,7,77,98,1,88,61}; // Array sortieren heapsort (array, n); for(i=0; i<n; i++){ // Array-Sortierung Ueberpruefen if (array[i]>array[i+1]){ printf("\nFAIL"); // Wenn Reihenfolge verletzt FAIL ausgeben return 0; } } printf("\nPASS"); // andernfalls PASS ausgeben getch(); }
-
(Geraten, nicht getestet)
for(i=0; i<n; i++){ // Array-Sortierung Ueberpruefen if (array[i]>array[i+1]){ printf("\nFAIL"); // Wenn Reihenfolge verletzt FAIL ausgeben getch(); return 0; } }
-
Sorry, hatte noch ein paar Fehler im Programm habe ich gesehen
@yahendrik: Hast mir schonmal weitergeholfen. Ich bekomme die sortierten Werte nun angezeigt, allerdings gibt er am Ende sowohl FAIL als auch PASS aus. Ist sicher nur eine Kleinigkeit. Weiß aber nicht woran es hängt.
Hier nochmal mein aktualisiertes Programm:
/* Christian Günther, Matr.-Nr. 121099 */ #include <stdio.h> #include <stdlib.h> void siftdown(int a[], int n, int i){ //i ist Index des zu siebenden Elementes int j, h=a[i]; if(i<0) return; // wenn i ungueltig, dann abbrechen while(i<n/2){ // solange noch Soehne vorhanden sind j=i+i+1; // setze Vergleichselement j auf linken Sohn von i if(j+1<n && a[j]<a[j+1]) // wenn rechter Sohn groesser linkem,... j++; // ... dann dieser als j setzen if(h>=a[j]) // wenn Heap-Ordnung hergestellt, break; // ...dann abbrechen a[i]=a[j]; i=j; // Element im Heap nach unten sieben } a[i]=h; // Element an Endposition einordnen } void buildheap(int a[], int n){ // In einer Schleife siftdown aufrufen int i; for(i=0; i<=7; i++) siftdown(a,n,i); printf("\n Heap=%d, n=%d, i=%d",a[i],n,i); } void heapsort(int a[], int n){ // // buildheap aufrufen int i, tmp; buildheap(a,n); for(i=n-1; i>=0; i--){ // In einer Schleife Elemente vertauschen und siftdown aufrufen 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[]) { int i; const int n = 20; int array[] = {11,92,23,84,35,76,47,68,59,17,39,55,29,3,7,77,98,1,88,61}; // Array sortieren heapsort (array, n); for(i=0; i<n; i++){ // Array-Sortierung Ueberpruefen if (array[i]>array[i+1]){ printf("\nFAIL"); // Wenn Reihenfolge verletzt FAIL ausgeben } } printf("\nPASS"); // andernfalls PASS ausgeben getch(); return 0; }
-
Verwende Strg+F5 in VisualStudio oder F9 in Codeblocks und verzichte auf den ganzen getch/Pause Anfängerschrott.
-
for(i=0; i<n-1; i++){ // Array-Sortierung Ueberpruefen if (array[i]>array[i+1]){
-
volkard schrieb:
for(i=0; i<n-1; i++){ // Array-Sortierung Ueberpruefen if (array[i]>array[i+1]){Hm... Ändert leider auch nichts an der Ausgabe.
Komischerweiße gibt er auch alle Werte richtig aus, jedoch setzt er die Ziffer mit dem Index i=8 (59) gleich an den Anfang der Ausgabe!? Versteh ich jetzt mal gar nicht wieso das am Anfang stimmt. Außer das Am Ende FAIL und PASS gleichzeitig ausgibt und die 59 am Anfang passt alles...
-
Wo kommt eigentlich die 7 her in
for(i=0; i<=7; i++) siftdown(a,n,i);?
-
volkard schrieb:
Wo kommt eigentlich die 7 her in
for(i=0; i<=7; i++) siftdown(a,n,i);?
Stimmt, da ist irgendein fehler... Hatte am Anfang statt 20 Werten nur 8 Werte drin... Wahrscheinlich daher. In der Funktion ist auch sicher irgendwo der Fehler. Nur wo...
-
Einen Fehler gefunden. Er lag in der buildheap Funktion. Hier die korrekte:
void buildheap(int a[], int n){ // In einer Schleife siftdown aufrufen int i; for(i=0; i<=20; i++) siftdown(a,n,i); }Allerdings gibt er am Ende aus:
FAIL
FAIL
PASSAusgeben sollte er ja entweder nur einmal FAIL oder PASS...
Weiß da jemand weiter?
-
Cantona schrieb:
Ausgeben sollte er ja entweder nur einmal FAIL oder PASS...
Weiß da jemand weiter?"PASS" wird auf jeden Fall einmal ausgegeben, weil es außerhalb der for-Schleife steht (geschweifte Klammern falsch gesetzt). Trotzdem ist da noch etwas Code notwendig, um zu erreichen, dass "PASS" oder "FAIL" wirklich nur ein einziges Mal erscheinen. So, wie es jetzt ist, wird an jeder Stelle, an der die Sortierung nicht stimmt, "FAIL" ausgegeben.
Lösen ließe sich das Ganze zum Beispiel über eine Hilfsvariable:
int failed = 0; for (i = 0; i < n - 1 && !failed; i++) { if (array[i] > array[i + 1]) failed = 1; } if (failed) printf("\nFAIL"); else printf("\nPASS");Statt in der Schleifenbedingung zu testen, ob bereits ein Fehler vorliegt, ließe sich die Schleife auch direkt nach dem Setzen von failed auf 1 mit break verlassen. Das ist Geschmackssache.
