4. Habe ein Problem!!!

Habe ein Problem!!!

  • M

    Hallo!
    Ich habe ein Problem mit folgendem Programm. Es stellt einen Quick-Sort Algorithmus dar.
    Ich rufe meine Funktion quick mit (zahl, 0, 19) auf. Durch Zwischenausgaben habe ich herausgefunden, dass mir anstelle der 19 eine 3 an o übergeben wird? Ich habe aber keine Ahnung wieso?
    Im Debug Mode bekomme ich nach Eingabe der 20 Zahlen folgende Fehlermeldung:
    Nicht abgefangene Ausnahme in Quick_Sort.exe: 0x0C00000DF: Stack Overflow.
    Ich hoffe mir kann jemand weiterhelfen.

    #include <stdio.h>
#include <time.h>

void quick (int *F, int u, int o) 
{
int i = u, j = o;
int h = 0; 
int p = 0;
int m = 0;
//übergibt für o = 2!!!
m = ((o+1)/2);

if (((u > o) && (u < m)) || ((u < o) && (u > m)))
	{
	p = u;		//untere Grenze als Pivotelement festlegen
	}
else if (((o > u) && (o < m)) || ((o < u) && (o > m)))
{
	p = o;		//obere Grenze als Pivotelement festlegen
}
else
{
	p = m;	//mittleres Element als Pivotelement festlegen
}

//printf("%d", p);	//zum Test Pivotelement ausgeben lassen

do 
	{    
	while (F[i] < p) 
		i++; 
	while (F[j] > p) 
		j--;
	if (i <= j)
		{
		h = F[i];
		F[i]=F[j];
		F[j]=h;
		i++;
		j--;
		}
	} 
while (i <= j);

if (u < j) quick(F, u, j);
if (i < o) quick(F, i, o);

printf("\n\nSortierte Folge:\n\n");
for (int x = 0; x < 20; x++)
	{
	printf("%d\n", F[x]);
	}
}

int main ()
{
int zahl[20];
int x = 0;

printf("Geben Sie 20 Werte zum Sortieren ein:\n");
for(x = 0; x < 20; x++)
	{
	scanf("%d", &zahl[x]);
	}

quick(zahl, 0, 19);

return 0;
}
    0
  • T

    ⚠ Dieser Post enthielt Blödsinn. ⚠

    0
  • M

    Wieso Blödsinn?
    Und übrigens kann ich mit solchen Antworten nicht gerade viel anfangen!

    0
  • T

    Sorry, ich bezog mich auf den Text, der ursprünglich mal in meinem Post stand. Die Aussage war falsch, und ich habe es daher weg editiert. Das war nicht auf Deinen Post bezogen. Sorry, wenn das nicht klar war.

    0
  • D

    Also ich habs verstanden ^^. Stack Overflow könnte darauf hinweisen, dass du eine Endlosschleife hast ... überprüf' also, ob die Schleifen abbrechen.

    0
  • M

    Also die Schleifen müssten eigentlich schon richtig abbrechen.
    Ich glaube eher, dass es irgendwie an meinem Array oder an der Übergabe liegen muss... Weiß allerdings nicht woran...

    0
  • _

    melle_87 schrieb:

    Also die Schleifen müssten eigentlich schon richtig abbrechen.
    Ich glaube eher, dass es irgendwie an meinem Array oder an der Übergabe liegen muss... Weiß allerdings nicht woran...

    Ob Schleifen sich richtig beenden, kannst du mit schrittweiser Programmausführung (F10/F11) überprüfen. So kannst du auch die Werte aller Variablen überwachen.

    0
  • T

    So, jetzt nochmal richtig:

    Irgendwie kommen mir die Schleifen, in denen die die Elemente aus den Halblisten tauschen willst komisch vor:

    while (F[i] < p) /* sollte wohl -> while (F[i] < F[p]) <- heissen */
        i++;
    while (F[j] > p) /* sollte wohl -> while (F[j] > F[p]) <- heissen */
        j--;

    Müsstest Du da nicht die Elemente aus den Array vergleichen? So vergleichst Du Elemente und Indizes. Irgendwie passt das nicht...

    0
  • M

    Ok. Ich bin das jetzt mal mit F10 durchgegangen. Die erste Schleife macht er einwandfrei. Die eingegebenen Zahlen stimmen und auch die Anzahl der Schleifendurchläufe. Wenn ich dann noch einen Schritt weiter gehe und die Funktion quick aufrufen will. Kommt die Fehlermeldung mit dem Stack-Overflow. Danach stehen in u = 2 und in o = 3. Aber es sollte ja in u = 0 und in o = 19 stehen.

    0
  • S

    um ehrlich zu sein find ich es allg. bisschen komisch ...
    z.B.

    if (((u > o) && (u < m)) || ((u < o) && (u > m)))
    {
    p = u; //untere Grenze als Pivotelement festlegen
    }
    else if (((o > u) && (o < m)) || ((o < u) && (o > m)))
    {
    p = o; //obere Grenze als Pivotelement festlegen
    }
    else
    {
    p = m; //mittleres Element als Pivotelement festlegen
    }

    so hab ich es geschrieben (Nebenbei, ich glaube es ist c99. Es ist schon älter das Programm...):

    #include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>

int partition(int* array, int begin, int end){

    int x = array[begin]; /*Pivot*/
    int i=begin-1;
    int j=end+1;
    int tmp;

   while(1){

      while(array[++i]<x && i<=end);

      while(array[--j]>x && j>=0);

      if(i>=j) break;

       if(array[i]>array[j]){
           tmp = array[i];
           array[i] = array[j];
           array[j] = tmp;
       }    
   }

   return j;
}

void quicksort(int* array, int begin, int end){

    int q;
    if(begin<end){
        q = partition(array, begin, end);
        quicksort(array, begin, q);
        quicksort(array, q+1, end);
    }

}

int main(void){

	srand((unsigned) time(NULL));
        int i, inserts;
	int* pInserts;

	printf("\nWieviele Werte erstellen und anschliesend sortieren?:\t");
	scanf(" %d", &inserts);

	pInserts = (int*) malloc(inserts*sizeof(int));

	for(i=0;i<inserts;i++){
		pInserts[i]= 1+rand()%inserts; //Zufall
		printf("%4d", pInserts[i]);
	}
        printf("\nBeliebige Taste druecken zum sortieren!\n");

	while(getchar()!='\n');

	quicksort(pInserts,0,inserts-1);
	free(pInserts);
	getchar();
    return 0;
}
    0
  • M

    Ja, des war wirklich komisch. In den If-Abfragen lag auch das Problem. Denn anstatt F[m], usw. hab ich die Abfragen nur mit m, usw. durchgeführt. Was natürlich total falsch war.
    Mittlerweile läuft mein Programm.
    Aber danke für die Antworten.

    0
Anmelden zum Antworten