Algorithmen und Datenstrukturen in C/ Shakersort

Aus Wikibooks

Prinzip[Bearbeiten]

Der Shakersort ist eine verbesserte Version des Bubblesort. Es wird hier nach jedem Durchlauf die Laufrichtung gewechselt. Dadurch wird zuerst das kleinste Element nach links, dann das größte Element nach rechts verschoben, usw.

Implementierung in C[Bearbeiten]

 void shakersort(int *a, int n)
{
	int li=0, re=n-1, mov;
        int j, hilf;
	do
	{
		for(j=re; j>=li+1; j--)
		{
			if(a[j-1] > a[j])
			{
				hilf = a[j-1];
				a[j-1] = a[j];
				a[j] = hilf;
				mov = j;
			}
		}

		li = mov;

		for(j=li; j<=re-1; j++)
		{
			if(a[j] > a[j+1])
			{
				hilf = a[j+1];
				a[j+1] = a[j];
				a[j] = hilf;
				mov = j;
			}
		}

		re = mov;
	} while(li<re);
}

Laufzeit-Komplexität[Bearbeiten]

Der Shakersort ist vor allem dann nützlich, wenn ein großer Teil des Feldes sortiert vorliegt. Jedoch ist die Verbesserung gegenüber dem Bubbelsort nur gering, da nur Vergleiche vermieden werden, und meist Vertauschungen aufwendiger sind. Somit ergibt sich eine ungefähre Komplexität von O(n²).

Eigenschaften[Bearbeiten]

Beim Shakersort handelt es sich wie beim Bubblesort um einen stabilen Sortieralgorithmus.