Auch noch ShakerSort

freakC++

Hallo zusammen,
der ein oder andere bemerkt vielleicht, dass ich mich momentan mit Sortieralgorithmen befasse. Nun versuche ich den ShakerSort zu implementieren, doch irgendwas stimmt da nicht. Könntet ihr mal drüber schauen? Es wird nicht korrekt sortiert.

void ShakerSort(int* arr, int n)
{
	int middle = n/2;
	int temp=0;
	for (int i=0; i<=middle; ++i)
	{
		for(int j=0; j<n-i; ++j)
		{
			if(arr[j] > arr[j+1])
			{
				temp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=temp;
			}
		}
		for (int j=n-1; j>=i; j--)
		{
			if(arr[j-1] > arr[j])
			{
				temp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=temp;
			}
		}
	}  
}

Vielen Dank und bis bald
lg, freakC++

SeppJ

Das gleiche wie immer: Du greifst auf nicht existierende Elemente zu. Problem ist j+1 im Falle i=0.

edit: Außerdem kann ich da überhaupt kein Shakersort drin erkennen, darum nehme ich auch mal an, dass zusätzlich noch der Algorithmus falsch ist. Was soll denn der Kram mit dem middle?

freakC++

Hallo,
och man, dieser Fehler passiert mir immer, wenn ich aus anderen Sprache etwas übersetzte. Naja, ich habe jetzt in Zeile 16 das >= durch ein > ersetzt. Dennoch funktioniert der Algorithmus noch nicht, doch finde ich ich keine weitere Stelle, wo es ein Problem gibt, wenn i=0 ist. Was übersehe ich denn da noch...

void ShakerSort(int* arr, int n)
{
	int middle = n/2;
	for (int i=0; i<=middle; ++i)
	{
		for(int j=0; j<n-i; ++j)
		{
			if(arr[j] > arr[j+1])
				std::swap(arr[j],arr[j+1]); 	
		}
		for (int j=n-1; j>i; j--) //nicht mehr >= !!! 
		{             //das Problem ist dennoch nicht behoben
			if(arr[j-1] > arr[j])
				std::swap(arr[j],arr[j+1]); 
		}
	}  
}

Vielen Dank
lg, freakC++

SeppJ

Ich habe inzwischen bei mir noch was reineditiert. Erklär mal, wie du dir Shakersort vorstellst.

freakC++

Hallo,
also mein lehrer gab und diesen Algorithmus in Delphi. Ich übersetze den jetzt gerade. Naja, der Shakersort macht ja einen BubbleSort von beiden Seiten, also von rechts und von links. Daher wird wie beim MergeSort die Mitte benötigt. Ich habe mir den Algorithmus bei wikipedia noch nicht angeschaut, da ich auf die korrektheit meines lehrers vertraue.

Kannst Du mir weiter helfen? Danke bis jetzt...bist echt super

Vielen Dank
lg, freakC++

edit: Ich habe noch einen Fehler gefunde. Der zweite Tausch muss natürlich so heißen:

std::swap(arr[j],arr[j+1]);

Jetzt ist noch irgendein element uninitialisert, also greife ich wohl darauf noch irgendwo drauf zu. das suche ich jetzt mal

SeppJ

In der ersten Hälfte wird immer noch auf nicht vorhandene Elemente zugegriffen.

freakC++

ah, damit müsste dann eigentlich das problem gelöst sein. ich melde mich bei erfolg oder auch bei keinem erfolg.

Vielen Dank
lg, freakC++

freakC++

Ok, ich hatte ERfolg. Es funktioniert jetzt.

Vielen Dank, SeppJ

lg, freakC++