geloest Shakersort

Roofie

Habe hier mein Shakersort Algorithmus. Normalerweise soll er ja schneller sein als Bubblesort, ist er aber nicht. Hat jemand von euch evtl ein Idee woran das liegen kann? Ich finde des Fehler einfach nicht.

void shakersort(int n, float v[]) 
{
	int i;
	int swp;
	int lower = 1;
	int higher = n - 1;
	int lastswap = n - 1;

	while (lower <= higher)
	{
		for (i = higher; i >= lower; i--) 
		{
			if (v[i-1] > v[i]) 
			{
				swp = v[i-1];
				v[i-1] = v[i];
				v[i] = swp;
				lastswap = i;
			}
		}
		lower = lastswap + 1;

		for (i = lower; i <= higher; i++) 
		{
			if (v[i-1] > v[i]) 
			{
				swp = v[i-1];
				v[i-1] = v[i];
				v[i] = swp;
				lastswap = i;
			}
		}
		higher = lastswap - 1;
	}
}

Roofie

void shakersort(int n, float a[]) 
{
	int i, j, done;
	float swp;
	int lower, higher;
	int lflag, rflag;
	lower = 0;
	higher = n-1;
	lflag  = lower;
	rflag = higher;

	done = FALSE;

	while (!done)
	{
		for (i = lower; i <= higher-1; i++) 
			if (a[i+1] < a[i]) 
			{
				swp = a[i];
				a[i] = a[i+1];
				a[i+1] = swp;
				rflag = i;
			}
		if(rflag != i)
			higher = rflag;

		for (j = higher; j >= lower+1; j--) 
			if (a[j-1] > a[j]) 
			{
				swp = a[j];
				a[j] = a[j-1];
				a[j-1] = swp;
				lflag = j;
			}
		if(lflag != j)
			lower = lflag ;

        if(rflag == i && lflag == j)
            done = TRUE;
	}
}

Du könntest Dein Programm nochmal um 30% verbessern, indem Du die Elemente verschiebst, nicht vertauscht. Vergleich immer zwei Nachbarelemente (wie bei bubblesort). Sobald Das Folgeelement a[i+1] kleiner ist als Dein aktuelles a[i], speicherst Du dies in einer Variable save = a[i] und verschiebst solange alle Folgeelemente in das Vorherige, bis save kleiner ist als ein Folgeelement. Dann wird in der aktuellen Position save gespeichert. Zum Schluss hast Du genau wie bei bubblesort, nach einem Durchlauf, definitiv im letzten Element a[right] den größten Wert Deines Arrays.
Du kannst jetzt auch diesen Index wieder in lastswap speichern, um die Grenzwerte optimal anzupassen. Das gleiche nur umgekehrt gilt natürlich für den Vorgang Rückwärts (right bis left).

Viel Spaß beim umsetzen...

volkard

Roofie schrieb:

Habe hier mein Shakersort Algorithmus. Normalerweise soll er ja schneller sein als Bubblesort, ist er aber nicht. Hat jemand von euch evtl ein Idee woran das liegen kann? Ich finde des Fehler einfach nicht.

kein wunder.
shakersort ist asymptotisch nicht schneller als bubblesort und in der praxis nicht erwähnenswert (falls überhaupt) schneller.

hehejo

Ist auch kein Wunder.
In der Uni hatten wir das mal kurz in einer Ringvorstellung (in der sich alle Lehrstühle vorstellen und für's Hauptsemester werben).

Bei einer Zweierpotenz von Spalte oder Reihe (je nach dem) geht's relativ schnell.
Sind es aber keinen Zweierpotenzen, dann bilden sich immer "Türme".

volkard

hehejo schrieb:

Bei einer Zweierpotenz von Spalte oder Reihe (je nach dem) geht's relativ schnell.
Sind es aber keinen Zweierpotenzen, dann bilden sich immer "Türme".

ich behaupte mal, daß du da was verwechselt hast.

hehejo

Oh, jetzt wo du es sagst..
Also es war ein Sortieralgo der "Geschoben" hatte.
Aber egal