Frage bei BubbleSort

[freakC++]

Hallo,
kann mir jemand sagen, warum dieser Algorithmus bei mir nicht funktioniert. Ich finde einfach den Fehler nicht:

int arr[8]={5,4,3,65,34,51,2,1};
int size=8;

void BubbleSort()
{
 for(int i=0; i<size;i++)
 {
	 for(int j=0; j<size-i;j++)
	 {
		 if (arr[j+1]<arr[j])
		 {
			int swp = arr[j];
			arr[j]=arr[j+1];
			arr[j+1]=swp;
		 }
	 }
 }
}

int main()
{
	BubbleSort();
	for (int i=0;i<8;i++)
		cout << arr[i] << "  ";
	return 0;
}

Vielen Dank
lg,freakC++

[unskilled]

was funktioniert denn nicht?

[Julian__]

kann sein dass du da eine optimierung von bubblesort hast oder so etwas, aber ich kenne bubblesort nach diesem schema:

void BubbleSort()
{
	bool swapped = true;
	while( swapped )
	{
		swapped = false;
		for( int i = 0; i < size - 1; i++ )
			if( arr[ i ] > arr[ i + 1 ] )
			{
				int tmp = arr[ i ];
				arr[ i ] = arr[ i + 1 ];
				arr[ i + 1 ] = tmp;
				swapped = true;
			}
	}
}

und das sollte so funktionieren hoffe ich, wenn du die funktion in deinen code einsetzt.

mfg,
julian

[Ad aCTa]

Ach, das geht doch viel einfacher.

template <typename T>
void bubblesort(T *array, size_t n) {
	while(--n)
		for(size_t i = 0; i < n; ++i)
			if(array[i] > array[i + 1])
				std::swap(array[i], array[i + 1]);
}

[freakC++]

naja, es wird nicht korrekt sortiert. Wenn ich jedoch folgendes Array neheme, dann funktioniert alles perfekt! Ich habe aber nichts am Code geändert. Deshalb verstehe ich nicht, warum mal richtig und mal falsch sortiert wird:

int arr[5]={5,4,3,2,1};
int size=5;

Vielen Dank
lg, feakC++

[freakC++]

komisch, jetzt funktioniert es, obwohl ich nur kurz mal andere Zahlen probiert habe und anschließend die oben geposteten Zahlen wieder eingesetzt habe! Das ist sehr merkwürdig!

Vielen Dank
lg, freaKC++

[SeppJ]

j+1 kann im Falle i=0 gleich size sein. In diesem Fall greifst du auf Objekte jenseits der Arraygrenzen zu. Also ist irgendwas an deinem Algorithmus gewaltig faul.

[freakC++]

Bin ich zu blöd oder sehe ich einfach deinen Punkt nicht. Wenn i=0 ist, hat das erstmal keine Auswirkungen und es wird auch auf kein undefiniertes Arrayelement zugegriffen ?! Da j nämlich immer kleiner als size ist, wird doch auf kein Element zugegriffen, dass es nicht gibt, oder?

Viele Dank euch allen
lg, freakC++

edit: Jetzt weiß ich was du meisnt. Ich schau mir das nochmal an!

[Tanren]

Es muss heissen "size - 1" anstelle von "size - i", dann funktionierts.