Sortieralgorithmen

Hallo,
ich habe ein Programm zum testen von Sortieralgorithmen geschrieben (Quicksort und Heapsort)....

Wenn ich einen kurzen Bereich (z.b. 20 Werte) sortieren will, dann klappts mit Quicksort und Heapsort einwandfrei....

Wenn ich aber mit 65000 Werten arbeite, dann gibts bei Quicksort einen "Stack overflow" und bei Heapsort ab der 30.000ten Stelle falsche Werte...

Wer Lust hat könnte ja mal drübergucken und mir sagen, was falsch ist...

Code:

#include <stdio.h>

void anfangsarray(int abc[])
{
	abc[0]=55;
	abc[1]=2;
	abc[2]=98;
	abc[3]=64;
	abc[4]=7;
	abc[5]=500;
	abc[6]=91;
	abc[7]=74;
	abc[8]=60;
	abc[9]=88;
	abc[10]=29;
	abc[11]=3;
	abc[12]=5;
	abc[13]=67;
	abc[14]=14;
	abc[15]=324;
	abc[16]=87;
	abc[17]=32;
	abc[18]=98;
	abc[19]=1;
	abc[20]=8;
}


void buildlong(int abc[])
{
	int count=0;
	for(count=0; count<=9999; count++)
	{
		abc[count]=65000-count;
	}

	for(count=10000; count<=19999; count++)
	{
		abc[count]=20000-count;
	}

	for(count=20000; count<=29999; count++)
	{
		abc[count]=50000-count;
	}

	for(count=30000; count<=39999; count++)
	{
		abc[count]=50000-count;
	}

	for(count=40000; count<=64999; count++)
	{
		abc[count]=105000-count;
	}
}


void array2(int abc[], int abc2[], int r)
{
	int count;
	for(count=0; count<=r; count++)
	{
		abc2[count+1]=abc[count];
	}
}

void umdrehen(int abc[], int r2)
{
	int t;
	int count;
	for(count=1; count<=r2; count++, r2--)
	{
		t=abc[count];
		abc[count]=abc[r2];
		abc[r2]=t;
	}
}
	
void show_long(int abclong[])
{
	printf("\nStelle 1: %d\n",abclong[1]);
	printf("\nStelle 5000: %d\n",abclong[5000]);
	printf("\nStelle 15000: %d\n",abclong[15000]);
	printf("\nStelle 25000: %d\n",abclong[25000]);
	printf("\nStelle 35000: %d\n",abclong[35000]);
	printf("\nStelle 45000: %d\n",abclong[45000]);
	printf("\nStelle 64999: %d\n",abclong[64999]);
}

void show_all(int abc[], int r)
{
	int count;
	printf("\n%d",abc[0]);
	for(count=1; count<=r; count++)
	{
		printf(", %d",abc[count]);
	}
}


void show_all2(int abc[], int r2)
{
	int count;
	printf("\n%d",abc[1]);
	for(count=2; count<=r2; count++)
	{
		printf(", %d",abc[count]);
	}
}

void exchange(int* x, int* y)
{
	int t=0;
	t=*x;
	*x=*y;
	*y=t;
}



int partition(int abc[], int l, int r) 
{
	int i, j, k, v;
	k=r; v=abc[k];
	i=l; 
	j=r-1; 
	while(1) 
	{
		while(abc[i]<=v && i<r) i++;
		while(abc[j]>=v && j>=l) j--;
		if(i>=j)
		{
			break;
		}
		else
		{
			exchange(&abc[i],&abc[j]);
		}
	}


	
	exchange(&abc[i],&abc[k]);
	


	return i;
}

void quick_sort(int abc[],int l,int r)
{
	int k;
	if(r<=l) return;
	k=partition(abc,l,r);
	quick_sort(abc,l,k-1);
	quick_sort(abc,k+1,r);
} 


void sink(int abc2[], int k, int anzahl) /*gehört zu Heap-Sort*/
{
	int son;
	while(1)
	{
		if(2*k>anzahl)
		{
			break;
		}

		if(2*k+1<=anzahl)
		{
			if(abc2[2*k]<abc2[2*k+1]) 
			{
				son=2*k;
			}
			else 
			{
				son=2*k+1;
			}
		}

		else 
		{
			son=2*k;
		}

		if(abc2[k]>abc2[son])
		{
			exchange(&abc2[k],&abc2[son]);
			k=son;
		}

		else 
		{
			break;
		}
	}
}


void heap_sort(int abc2[], int anzahl)
{
	int i;
	for(i=anzahl/2; i>0; i--)
	{
		sink(abc2,i,anzahl);
	}
	for(i=anzahl; i>1; i--)
	{
		exchange(&abc2[1],&abc2[i]);
		sink(abc2,1,i-1);
	}
}

void main()
{
	int anzahl=21;
	int anzahl2=65000;
	int l=0;
	int r=20;
	int r2=64999;
	int abc[65000];
	int abc2[65001];

	printf("PROGRAMM ZUM TESTEN VERSCHIEDENER SORTIERALGORITHMEN");
	printf("\n\nFolgender Array wird sortiert:\n");
	
	anfangsarray(abc);						/* Array 21 Werte zuweisen */

	show_all(abc, r);

	
	printf("\n\nQUICKSORT:");
	quick_sort(abc, l, r);					/* mit Quicksort sortieren */
	
	show_all(abc, r); 

	anfangsarray(abc);						/* Array mit urspruenglichen Werten wiederherstellen */
	array2(abc,abc2,r);						/* zweiter Array, bei dem jeder Wert "eins weiter gerückt" ist */

	printf("\n\nHEAPSORT:");
	heap_sort(abc2, anzahl);				/* mit Heapsort sortieren */
	umdrehen(abc2,anzahl);					/* umdrehen */
	show_all2(abc2,anzahl);


	printf("\n\nFolgender Array wird sortiert:\n");

	buildlong(abc);							/* Array 65.000 Werte zuweisen */
	show_long(abc);

	printf("\n\nQUICKSORT:");
	quick_sort(abc, l, r2);					/* mit Quicksort sortieren */
	show_long(abc);

	buildlong(abc);							/* urspruengliche Werte */
	array2(abc,abc2,r2);					/* zweiter Array, bei dem jeder Wert "eins weiter gerückt" ist */
	umdrehen(abc2,anzahl2);					/* umdrehen, damit's für Heapsort nicht zu vorsortiert ist... */


	printf("\n\nHEAPSORT:");
	heap_sort(abc2, anzahl2);				/* mit Heapsort sortieren */
	umdrehen(abc2,anzahl2);					/* umdrehen */
	show_long(abc2);

	




	getch();
	

}

 

Hi,

Nimm aus der quick_sort-Methode das Array abc[] raus.
Du erhältst sonst riesige Datenmengen, die möglicherweise zum stackoverflow geführt haben.
Stell das Array abc[] auf private um, so dass es nur einmal im
Programm existiert. (Bzw. mit einfachen Kopien arbeiten, wenn nötig)

Ich hoff, es hilft dir auf den richtigen Weg.

Grüße

 

@Johnny: Wie kommst Du darauf?

 

@daboom:
Das übliche Problem bei übermäßigen Rekursionen: Da stapelt sich eine zu große Datenmenge auf.
Davon kann ich dir ein Lied singen.

(Es sei denn, ich habe in diesem Fall etwas übersehen (?) )

Greetz

 

@ottifant

Es ist allgemein zu bevorzugen keine Rekusionen zu verwenden. Wie hier ja schon geschrieben wurde neigen diese dazu unter Umständen doch extrem den Stack zu belasten was zu einem Overflow führen kann.

Du solltest in Deinem vorliegenden Fall anstatt einer Rekursion eher mit Schleifen arbeiten.

 

@Johnny: OK, ich hatte Dich so verstanden, dass Du meintest, dass Array würde immer wieder kopiert werden. Ja, die Array-Pointer stapeln sich, allerdings genauso wie die beiden ints l und r. Von daher macht da ein globaler Array-Pointer wohl nicht so viel aus, würde ich sagen.

@Fettbemme: Eigentlich sollte man auf herkömmlichen Rechner-Architekturen imo sogar Rekursionen vermeiden, da die einfach nicht dafür optimiert sind. Schleifen schaffen das gleiche of schneller.
Das Problem ist, dass Rekursionen oft viel übersichtlicher und einfacher zu programmieren sind...