Stabilisierung von Sortieralg. < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:17 Sa 19.06.2010 | | Autor: | DerGraf |
| Aufgabe | | In der letzten Übungsserie haben Sie die Instabilität für die Sortierverfahren Heapsort und Quicksort gezeigt. Überlegen Sie sich, durch welche Modifikationen die Stabilität in diesen Algorithmen gesichert werden kann. |
Hallo,
sowohl bei der Wiederherstellung der Heapeigenschaft bei Heapsort als auch in Quicksort werden in der Regel kaum Nachbarelemente miteinander verglichen. Dabei kann es also vorkommen, dass 2 gleichwertige Elemente ihre Reihenfolge tauschen, weil das vorhergehende Element über das nachfolgende hinweggetauscht werden kann.
Am einfachsten würde ich dies umgehen, in dem ich gleichwertige Elemente in einer Queue zusammenfasse, und dann die Queues sortiere, könnte ich die Stabilität natürlich ohne weiteres beibehalten. Nur könnte ich dann auch gleich Bucketsort verwenden, welches danach arbeitet.
Hat jemand vielleicht noch eine bessere Idee?
Ich würde mich sehr darüber freuen.
Gruß
DerGraf
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:04 Mo 21.06.2010 | | Autor: | felixf |
Moin.
> In der letzten Übungsserie haben Sie die Instabilität
> für die Sortierverfahren Heapsort und Quicksort gezeigt.
> Überlegen Sie sich, durch welche Modifikationen die
> Stabilität in diesen Algorithmen gesichert werden kann.
>
> sowohl bei der Wiederherstellung der Heapeigenschaft bei
> Heapsort als auch in Quicksort werden in der Regel kaum
> Nachbarelemente miteinander verglichen. Dabei kann es also
> vorkommen, dass 2 gleichwertige Elemente ihre Reihenfolge
> tauschen, weil das vorhergehende Element über das
> nachfolgende hinweggetauscht werden kann.
>
> Am einfachsten würde ich dies umgehen, in dem ich
> gleichwertige Elemente in einer Queue zusammenfasse, und
> dann die Queues sortiere, könnte ich die Stabilität
> natürlich ohne weiteres beibehalten.
Genau.
> Nur könnte ich dann auch gleich Bucketsort verwenden,
> welches danach arbeitet.
Wieso das? Das geht doch i.A. gar nicht! Wie willst du Bucket Sort machen, wenn du fuer die Eingabedaten nur zwei Routinen hast, die dir $a < b$ und $a = b$ testen? Dann kannst du Bucket Sort vergessen, deine oben skizzierte Methode und Quicksort/Heapsort funktionieren dagegen.
> Hat jemand vielleicht noch eine bessere Idee?
> Ich würde mich sehr darüber freuen.
Such doch mal im Netz nach "stable quicksort" und "stabe heapsort".
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:37 Do 24.06.2010 | | Autor: | DerGraf |
Hallo Felix,
vielen Dank für deine Antwort. Bei Heapsort stand in meinen bisherigen Quellen, dass es nicht stabilisiert werden kann.
Da mein Verfahren funktioniert, habe ich es auch abgegeben, da es die Aufgabe erfüllt, auch wenn es programmtechnisch nicht so schön ist.
Mit freundlichen Grüßen
DerGraf
|
|
|
|
