Selection Sort erweitert

[rolliwitsch]

hi Fangemeinde,

die Tage habe ich den Selection Sort etwas aufgebohrt, hier der Code

// keine Rekursion, Funktion muss iterativ aufgerufen werden!

void xSort(int * p, int start, int stop){

	unsigned long min = 0xffffFFFF; // GAZ, Größte Anzunehmende Zahl unsigned int

	unsigned long max = 0;

	int posmin;

	int posmax;

	int i;

	for(i = start; i < stop; i++){

		if( p[i] < min ) { 

			min = p[i];

			posmin = i;

		}

		if( p[i] > max ) {

			max = p[i];

			posmax = i;

		}

	}


	// nun die Zahlen auf den richtigen Positionen ablegen

	// merke wert auf p[start]

	unsigned long wsta = p[start];

	p[start] = min;

	p[posmin] = wsta;


	// posmax ist posmin, wenn max auf start stand

	if(posmax == start){posmax = posmin;}


	// merke wert auf p[stop-1]

	unsigned long wsto = p[stop-1];


	p[stop-1] = max;

	p[posmax] = wsto;

}

/*************************************************************************/

// Biepiel Funktionsaufruf

int main(){

	int i;

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


	int size = sizeof(zn)/sizeof(int);

	printf("zn hat %d Zahlen\n", size);


	// iteration über xSort

	for(i = 0; i < size - i; i++) xSort(zn, i, size - i);


	// Ausgabe

	for(i = 0; i < size; i++) printf ("%d\n", zn[i]);


	return 0;

}

Dabei wird ein Zahlen-Array mit bspw. 10 Zahlen lediglich nur fünfmal durchlaufen, danach ist es sortiert. Ein Array mit 11 Zahlen wird sechsmal durchlaufen. Das macht diese Sortierfunktion sehr performant.

Funktionsweise: Bei jedem Durchlauf wird das Minimum UND das Maximum ermittelt, sowie die Positionen dieser Werte im Array. Das Minimum tauscht dann seinen Platz mit der Startposition und dem dortigen Wert. Das Maximum tauscht den Platz mit der Stopposition. Das ist der Gewinn dieses Algorithmus gegenüber einem Selection Sort, bei dem lediglich das Minimum verschoben wird.

Viele Grüße!

[Klotzkopp]

Du hast keine Frage gestellt, deswegen gebe ich einfach mal so meine Kommentare ab

die Tage habe ich den Selection Sort etwas aufgebohrt

Soso

// keine Rekursion, Funktion muss iterativ aufgerufen werden!

Normalerweise würde man den gesamten Algorithmus in eine Funktion packen. Aber das ist ja keine große Sache.

unsigned long min = 0xffffFFFF; // GAZ, Größte Anzunehmende Zahl unsigned int

Es gibt (je nach Plattform) einen Unterschied zwischen unsigned long und unsigned int. Im Hinblick auf Portierbarkeit ist es daher auch keine gute Idee, solche Konstanten fest in den Code zu schreiben.

if( p < min ) {

Du vergleichst vorzeichenlose mit vorzeichenbehafteten Werten. Das ist generell keine gute Idee. Dein Algorithmus funktioniert darum auch nicht, wenn negative Werte auftreten.

Dabei wird ein Zahlen-Array mit bspw. 10 Zahlen lediglich nur fünfmal durchlaufen, danach ist es sortiert. Ein Array mit 11 Zahlen wird sechsmal durchlaufen. Das macht diese Sortierfunktion sehr performant.

Hast du das nachgemessen, oder wie kommst du darauf? Ein Algorithmus wird nicht zwangsläufig dadurch performanter, dass man die Anzahl der äußeren Schleifendurchläufe reduziert.

Funktionsweise: Bei jedem Durchlauf wird das Minimum UND das Maximum ermittelt, sowie die Positionen dieser Werte im Array. Das Minimum tauscht dann seinen Platz mit der Startposition und dem dortigen Wert. Das Maximum tauscht den Platz mit der Stopposition. Das ist der Gewinn dieses Algorithmus gegenüber einem Selection Sort, bei dem lediglich das Minimum verschoben wird.

Inwiefern ist das ein Gewinn?

Dein Algorithmus braucht genauso viele Vergleiche und Tauschoperationen wie Selection Sort.Du hast vielleicht nur halb so viele Schleifendurchläufe, allerdings machst du bei jedem Durchlauf doppelt so viel.

Dein Algorithmus hat dieselbe Laufzeitkomplexität wie Selection Sort (O(n^2)) und auch dieselben Nachteile (nicht stabil, nicht natürlich).

[TDM]

Ich bleib da lieber bei Quicksort, der ist performanter.:hells:

[Klotzkopp]

Ich bleib da lieber bei Quicksort, der ist performanter.:hells:

So allgemein kann man das auch nicht sagen. Die Laufzeitkomplexität sagt ja nichts über die tatsächliche Dauer aus. Bei kleinen Arrays können die O(n^2)-Algorithmen durchaus schneller als die mit O(n log n) sein.

Es kommt auch darauf an, ob die Daten vorsortiert sind, und wie teuer Vergleiche in Relation zu Vertauschungen sind.

Es gibt nicht "den" besten Sortieralgorithmus für jede Situation.

[qat]

hi Fangemeinde,

...

Hallo!

Ob sich Klotzkopp dazuzählt?

Btw:

Wenn du eigene (nützliche) Routinen entwickelst und diese einer breiteren Öffentlichkeit präsentieren möchtest, empfehle ich dir codeproject.

Aber ich finds auch ok das hier zu tun, schließlich kann man aus den Reaktionen die man bekommt nur lernen.

[rolliwitsch]

hi danke Euch!!!

nun habe ich wirklich einmal eine Frage. Das Selection-Sort schnappt sich nur das Minimum. Ich habe Selection-Sort schon umgeschrieben, dass es sich nur das Maximum schnappt und an die richtige Position schiebt.

Das geht natürlich auch.

Meine Frage ist die: Wenn ich ein Array durchlaufe, was um Gottes Namen spricht dagegen, außer dem Minimum, oder dem Maximum, nicht gleich BEIDES zu ermitteln und zum Sortieren an die richtige Position zu schieben!?

Oder, die Frage mal etwas heretischer gestellt: Haben die Publisher von Selection-Sort das nicht hinbekommen?

Viele Grüße!

Btw.: Was wirklich Ressourcen spart, vermeidet Rekursionen, ruft dazu bestimmte Funktionen iterativ auf. Bei Rekursionen legt das OS einen zusätzlichen Stack im Speicher an. Desterwegen postete ich obenstehende Sortierfunktion als NICHT rekursiv.

[Klotzkopp]

Meine Frage ist die: Wenn ich ein Array durchlaufe, was um Gottes Namen spricht dagegen, außer dem Minimum, oder dem Maximum, nicht gleich BEIDES zu ermitteln und zum Sortieren an die richtige Position zu schieben!?

Gar nichts. Es spricht aber auch nichts dafür. Wie ich bereits sagte, bringt das keinen nennenswerten Perfomancegewinn. Du brauchst genauso viele Vergleiche und genauso viele Vertauschungen.

Oder, die Frage mal etwas heretischer gestellt: Haben die Publisher von Selection-Sort das nicht hinbekommen?

Mal abgesehen davon, dass es keine "Publisher" gibt: Es gibt da nichts hinzubekommen.

Du scheinst immer noch zu glauben, dass dein Algorithmus besser ist als ein normaler Selection Sort. Das ist aber nicht der Fall. Hast du meine Kommentare nicht gelesen?

Desterwegen postete ich obenstehende Sortierfunktion als NICHT rekursiv.

Was nichts Besonders ist, weil Selection Sort sowieso iterativ implementiert wird, denn die Rekursionstiefe wäre gleich der Anzahl der zu sortierenden Elemente, und so etwas versucht man zu vermeiden.

[rolliwitsch]

Vielen Dank!

immerhin kann ich selbst festlegen, ob ich meine Funktion rekursiv oder iterativ aufrufe,

für welchen Zahlenbereich meine Funktion gültig ist (unsigned int || signed int)

und ob ich einen Selection-Sort auf das Minimum, das Maximum oder Beides beziehe. Praktisch läuft ein Selection-Sort schneller, wenn ich nicht nur das Minimum, sondern auch das Maximum einbeziehe, dies zeigt mir ein Versuch.

Viele Grüße ;-)

[rolliwitsch]

Hallo!

Ob sich Klotzkopp dazuzählt?

Btw:

Wenn du eigene (nützliche) Routinen entwickelst und diese einer breiteren Öffentlichkeit präsentieren möchtest, empfehle ich dir codeproject.

Aber ich finds auch ok das hier zu tun, schließlich kann man aus den Reaktionen die man bekommt nur lernen.

Naja, und dazu gäbe es ja auch noch meine eigene Site

Berechnungen von IP-Adressen und Subnetzen mit c

--roro

[Klotzkopp]

für welchen Zahlenbereich meine Funktion gültig ist (unsigned int || signed int)

Nur so als Hinweis: Man kann Selection Sort so implementieren, dass man ohne solche Min/Max-Konstanten auskommt. Man kann das sogar in C++ als Template formulieren, dann kann man damit alles sortieren, was eine Ordnungsrelation hat, nicht nur Zahlen.

Praktisch läuft ein Selection-Sort schneller, wenn ich nicht nur das Minimum, sondern auch das Maximum einbeziehe, dies zeigt mir ein Versuch.

Hast du ein Protokoll dazu? Das würde mich interessieren.

[Bubble]

Praktisch läuft ein Selection-Sort schneller, wenn ich nicht nur das Minimum, sondern auch das Maximum einbeziehe, dies zeigt mir ein Versuch.

Das liegt an der gewählten Implementierung, nicht am Aufwand des Sortierverfahrens.

Du könntest sämtliche Rekursionen und/oder Schleifen "entrollen", dann ist vielleicht leichter erkennbar, das beide Varianten im Grunde gleich sind.

Selbst wenn Du durch eine clevere Implementierung auf geeigneter Hardware z.B. 50% der erforderlichen Taktzyklen im Vergleich zu einer anderen Implementierung einsparst, ist das nur eine Konstante vor dem Zeitfaktor. Das ist natürlich eine für zeitintensive oder zeitkritische Anwendungen sinnvolle Optimierung, aber wirklich interessant ist der Anstieg des Aufwandes bei steigender Anzahl zu sortierender Elemente. Bei selection sort steigt der Aufwand mit zunehmender Zahl zu sortierdender Elemente quadratisch, egal wie die Umsetzung aussieht.

[Klotzkopp]

Ich habe mal ein paar Tests gemacht. rolliwitschs Algorithmus (die Variante wird übrigens auch bei Wikipedia erwähnt) ist in der Tat schneller als ein "normaler" Selection Sort. Bei meinen Tests sind es etwa 30 bis 40% für die Sortierung von int-Feldern.

Der Grund ist die reduzierte Anzahl an Schleifenoperationen (Inkrementierungen und Vergleiche). Der Effekt ist umso schwächer, je schneller diese Operationen im Vergleich zu Vergleichen und Vertauschungen der zu sortierenden Objekte selbst sind.

Das ändert allerdings nichts an der Komplexitätsklasse des Algorithmus. Richtig spürbar wird der Effekt nur bei großen Arrays, für die man sowieso einen Algorithmus mit O(n log n) verwenden würde.

[Bubble]

Der Grund ist die reduzierte Anzahl an Schleifenoperationen (Inkrementierungen und Vergleiche).

Eben. Wenn man zusätzlich die Schleife weiter entrollt, sprich noch weniger Schleifendurchläufe verwendet, wird es erstmal noch günstiger - bis irgendwann so viel Code produziert wurde, dass aufgrund der Speicherperformance ein Schleifendurchlauf wieder günstiger wäre, als weiteres Entrollen. Dies ist aber nur ein Implementierungsdetail und verändert die Laufzeit vom Algorithmus (in O) nicht.