matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Schulmathe
  Status Primarstufe
  Status Mathe Klassen 5-7
  Status Mathe Klassen 8-10
  Status Oberstufenmathe
    Status Schul-Analysis
    Status Lin. Algebra/Vektor
    Status Stochastik
    Status Abivorbereitung
  Status Mathe-Wettbewerbe
    Status Bundeswettb. Mathe
    Status Deutsche MO
    Status Internationale MO
    Status MO andere Länder
    Status Känguru
  Status Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAlgorithmen und DatenstrukturenStabilisierung von Sortieralg.
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Algorithmen und Datenstrukturen" - Stabilisierung von Sortieralg.
Stabilisierung von Sortieralg. < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Stabilisierung von Sortieralg.: Tipp
Status: (Frage) beantwortet Status 
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

        
Bezug
Stabilisierung von Sortieralg.: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                
Bezug
Stabilisierung von Sortieralg.: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.schulmatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]