SelectionSort2

[Janus]

Hallo,
...komm bei einer Übungsaufgabe nicht weiter....
Beim Selection Sort wird eine Liste so sortiert, daß links vom aktuellen Element
eine sortierte Teilliste aus Elementen kleiner oder gleich dem aktuellen Element
liegt. In einem Sortierschritt wird das aktuelle Element mit dem Minimum in der
unsortierten Restliste vertauscht.
Als optimierte Variante könnte man versuchen, nicht nur das kleinste, sondern
pro Durchlauf die zwei kleinsten Elemente im Rest der Liste zu finden und an
den Anfang zu stellen.
a) Schreiben Sie einen Algorithmus selSort2(bint list[n] ↓n), der dies
implementiert.
Achten Sie auf mögliche Sonderfälle, die auftreten können, z.B.:
• Ungerade/Gerade Listenlängen
• Beide Minima stehen am Anfang in verkehrter Reihenfolge (zweitkleinstes
vor dem kleinsten)

Ich meine ich kenne zwar den ursprünglichen SelectionSort aber hat wer eine Idee zu dem?

[Scavi]

..besonders optimiert klingt mir das nicht gerade.

[Jan Krüger]

Naja, es kann theoretisch die Zahl der Schleifendurchläufe halbieren (weil in jedem Durchlauf ca. zwei Elemente sortiert werden). Am asymptotischen Laufzeitverhalten ändert sich dadurch natürlich nichts.

Von der Implementation her ist das nicht weiter schwer: man sucht bei jedem Durchlauf die beiden niedrigsten Elemente (zwei temporäre Variablen; Sonderfall: es ist nur noch ein unsortiertes Element übrig) und tauscht die mit den beiden ersten unsortierten Elementen.

[Scavi]

Du halbierst zwar die Laufzeit aber verdoppelst die Vergleiche. Insofern nimmt sich das nichts. Man könnte sonst ja auch pro Durchlauf n-1 kleinere Elemente suchen und einfügen. Da wiegt sich wieder Speicher- gegen Laufzeitkomplexität auf. Also ist es keine Optimierung.

[Jan Krüger]

Nein, wenn du n-1 kleinere Elemente suchst, ändert sich nichts, weil du dann einfach nur die Schleife woandershin verschoben hast. :)

Schauen wir uns die Zahl der Vergleiche mal im Detail an... Beispiel 10 Elemente (jeweils Worst Case):

Zwei Minima
- 1. 17 Vergleiche, 2 Tauschoperationen
- 2. 13 V, 2 T
- 3. 9 V, 2 T
- 4. 5 V, 2 T
- 5. 1 V, 1 T
Summe: 45 V, 9 T

Ein Minimum
- 1. 9 V, 1 T
- 2. 8 V, 1 T
- 3. 7 V, 1 T
- 4. 6 V, 1 T
- 5. 5 V, 1 T
- 6. 4 V, 1 T
- 7. 3 V, 1 T
- 8. 2 V, 1 T
- 9. 1 V, 1 T
Summe: 45 V, 9 T

Okay, soviel dazu.

[Scavi]

Yo, das ist das was ich meinte. Gut, ich gebe zu, ich hab mich unverständlich ausgedrückt.

Deine Überschriften sind aber verdreht ;)

[Jan Krüger]

Hm, und dabei hab ich's zuerst richtig gemacht... ich muss unbedingt wacher werden. :D

[TGGC]

Sinnlose Optimierung, aber nette Fingerübung für angehende FI. 8)


Bye, TGGC

[Jan Krüger]

Wir waren uns gerade einig, dass es eben keine Optimierung ist, weil dadurch absolut gar nichts schneller wird.

[DarkTom]

In der Tat lässt sich aber die Anzahl der Vergleiche reduzieren, analog zu dem Problem, in dem man gleichzeitig Minimum und Maximum sucht.

Das kommt dann so raus:

Zwei Minima
- 1. 13 Vergleiche, 2 Tauschoperationen
- 2. 10 V, 2 T
- 3. 7 V, 2 T
- 4. 4 V, 2 T
- 5. 1 V, 1 T
Summe: 35 V, 9 T

Der Trick: Die jeweils nächsten beiden Kandidaten werden zuerst miteinander verglichen, dann der grössere mit dem Maximum (bzw hier mit dem zweitkleinsten Element), der kleinere mit dem Minimum.
Als Resultat braucht man für einen Durchlauf 3/2*n - 2 Vergleiche statt wie erwartet 2*n - 2
:)

[Jan Krüger]

Ohja, richtig. Die Hitze und so. ;)

[TGGC]

Naja, Einsicht ist der erste Schritt...


Bye, TGGC

[DarkTom]

In der Tat die Hitze. Meine obigen Ausführungen sind nämlich falsch, wie mir im Nachhinein eben auffiel. Aber nett, dass ihr das einfach so akzeptiert. *g*

Die Analogie zur Minimum/Maximum-Bestimmung hält leider nicht wirklich. (Kann man sich relativ einfach überlegen (z.B. wenn man den Kopf in den Kühlschrank steckt). Die Ausführung ist mir jetzt aber zu anstrengend (die Hitze und so... ;))

Wenn mir nicht noch ein Geistesblitz kommt, bleibt es also bei der gleichen Anzahl an Vergleichen. Und bei den Temperaturen wäre so ein Geistesblitz ja schön blöd, noch durch die Gegend zu rennen...

[TGGC]

Haben sie dich jetzt bestochen, oder ist das wirlich nur die Hitze... 8)


Bye, TGGC

[Jan Krüger]

Aber nett, dass ihr das einfach so akzeptiert. *g*
Auch das liegt an der Hitze. Ich hatte noch meine Zweifel, aber ich hab's einfach nicht geschafft, die Überprüfung bis zum Ende durchzuziehen. :D

[DarkTom]

Blubb!

Heute Nacht ist's zeitweilig abgekühlt. Ich kann erneut widerrufen. Ist das Leben nicht schön? Es geht denn wohl doch mit der angegebene Vergleichszahl, wenn auch anders, als ich erst dachte. Mal ganz grob:

Wir haben min und minPlus und die zwei nächsten Kandidaten k < g.

if (k < min) {
if (g < min) minPlus = g;
else minPlus = min;
min = k;
}
else {
if (k < minPlus) minPlus = k;
}
Also 3 Vergleiche für jeweils zwei weitere Elemente.

Bestochen hat mich übrigens niemand, auch wenn ich den Zusammenhang nicht verstehe, aber es ist ja auch schon wieder so warm...

[TGGC]

Es gibt mehrere Möglichkeiten, auch deine erstgenannte hätte funktioniert, entspricht nur nicht ganz der Aufgabe. Das würde nämlich die Liste nicht nur von "unten" her sondern auch von oben her aufbauen.


Bye, TGGC

[DarkTom]

Es gibt mehrere Möglichkeiten, auch deine erstgenannte hätte funktioniert, entspricht nur nicht ganz der Aufgabe. Das würde nämlich die Liste nicht nur von "unten" her sondern auch von oben her aufbauen.Meine erstgenannte ist identisch mit meiner letztgenannten Version. Ich bin nur zuletzt konkreter geworden, um die Korrektheit nachzuweisen (u.a. mir selbst). Das Maximum kam nur deshalb rein, weil ich daher diese Vorgehensweise kannte und war nicht Teil meiner vorgeschlagenen Lösung. Das war vielleicht in der Kürze der Darstellung missverständlich. Aber trotzdem sind deine Gedankengänge richtig; natürlich könnte man auch mit Min- und Maximum arbeiten. Letztlich ist das doch eh nur akademische Spielerei. Es gibt bestimmt noch zig weitere wenig sinnvolle Varianten von SelectionSort.

[TGGC]

Dann habe ich dich wohl falsch verstanden, und mir selbst was Logisches zusammengereimt.
Letztlich ist das doch eh nur akademische Spielerei.Das war es, was mein erster Post ausdrücken wollte.


Bye, TGGC