Welchen Sortieralgorithmus für schnelle Vergleiche und langsames Verschieben?
-
Wenn man sich Tabellen von Sortieralgorithmen anguckt wird die Komplexität immer in der Anzahl der Vergleiche angegeben. Aber was ist, wenn ein Vergleich vergleichsweise trivial ist, aber jeder Tausch von Elementen kostet? Dann würde man ja nach Möglichkeit gleich jedes Element an seinem richtigen Platz haben wollen.
Ein Beispiel wäre ein Mensch, der ein Bücherregal alphabetisch sortiert. Es ist trivial zwei Bücher zu vergleichen, man kann sogar ziemlich gut abschätzen wo das Buch hinterher landen wird. Daher wird ein Mensch mit einem einfachen Selection Sort schneller sein als ein Mensch der ein fortschrittliches MixSort benutzt, dafür aber alle Bücher aus dem Regal holen muss und zigmal vertauschen muss.
Was würdet ihr nehmen?
P.S.: Bei meinem Problem ist auch ganz gut abschätzbar, wo die Elemente später ungefähr landen werden, wie beim Bücherregal.
P.P.S.: Und keine Pointerindirektion. Ja, das wäre eine sehr gute Lösung und ich werde es vermutlich auch so machen. Ich bin aber eher an der akademischen Fragestellung interessiert, wie man die Anzahl der Vertauschungen minimiert, weil ich beim Nachdenken über das Problem neugierig geworden bin.
-
Hi,
ich könnte mir vorstellen, daß vielleicht ein lineares Sortieren, bei dem man am Anfang anfängt und jedes nicht passend stehende Element durch das passende ersetzt gut gehen könnte. Eventuell auch von beiden Seiten zugleich aufbauen.
Ein anderer Gedanke wäre, daß man nicht nur passen oder nicht betrachtet, sondern sich am Anfang auf die Elemente konzentriert, die am weitesten falsch stehen.Gruß Mümmel
-
Bei Büchern würde sich Radixsort möglicherweise eignen(allerdings brauchste dann referenzen wennste nix kopieren willst)
Ansonsten gehe davon aus, dass du jedes buch (mindestens) einmal verschieben musst(die Wahrscheinlichkeit, dass ein buch passend steht ist doch sehr gering). ALso kannst du InsertSort(wenn dus genau weißt) oder selectionsort nehmen.EDIT: Radix nicht Bucket, natürlich
-
DerBaer schrieb:
Bei Büchern würde sich Radixsort möglicherweise eignen(allerdings brauchste dann referenzen wennste nix kopieren willst)
Och, Kopieren ist schon ok. Der Bibliothekar kann nämlich auf Tischen schnell operieren, während das Rumhantieren auf Regalen lange dauert.
Einmal raus aus allen Regalen auf 26 Tische. Dann die Tische einzeln Sortieren. Und dann in die Regale zurücktun. Gegebenenfalls Tische weiter teilen.Und Mergesort bietet sich an, weil reale Bücher sehr gute Stacks und Queues bilden können, aber mit Arrays doch ihre Probleme haben.
Für Rechner und Arrays bietet sich wohl an, ein Indexfeld anzulegen und zu sortieren und dann anhand des Indexfeldes mit nur n Vertauschungen das Hauptfeld aufräumen.
-
volkard schrieb:
Und Mergesort bietet sich an, weil reale Bücher sehr gute Stacks und Queues bilden können, aber mit Arrays doch ihre Probleme haben.
wobei Queues nur bei dicken büchern. Bei dünne fallenb die um oder du brauchste starke hände xD
-
Ich kenne mich zwar mit Algorithmen nicht aus, aber meine Idee:
Anzahl der Bücher eines bestimmten Buchstaben ermitteln, Datenfeld mit der Gesamtgröße anlegen, aus den Mengen die Offsets ermitteln und dann die Bücher an die entsprechenden Plätze stellen. Dann müsste man aber wohl rekursieren…
Naja, ich schicke es als Anregung trotzdem einmal ab.
-
P.P.S.: Und keine Pointerindirektion. Ja, das wäre eine sehr gute Lösung und ich werde es vermutlich auch so machen. Ich bin aber eher an der akademischen Fragestellung interessiert, wie man die Anzahl der Vertauschungen minimiert ..
Also die offensichtliche Loesung zu verbieten, ist sowohl paraktisch als auch akademisch wenig foerderlich. Ein Problem in der Praxis sowie in der Theorie begegnet man meist mit allen zur Verfuegung stehen Mitteln. Auch fallen grundlegende Datenstrukturen wie Listen weg, da sie beim Sortiren die Objekte an sich nicht kopieren. Es wird ja nicht ohne Grund die Komplexitaet abhaengig von der Anzahl der Vergleiche angegeben. Was waere der 100m-Laeufer wenn er auf sein rechtes Bein verzichtet oder rueckwaerts rennt?
-
Also wir haben an der Universität für solche Fälle Selection Sort gelernt. Hat zwar im schlimmsten Fall n² Vergleiche, aber das stört nicht weil es selbst im allerschlimmsten Fall nur zu n Moves kommt.
Bucket/Radix ist da ebenfalls gut, aber auf die Wirklichkeit projiziert wird das mit den Buckets für die Bücher etwas umständlich
MfG SideWinder
-
knivil schrieb:
Also die offensichtliche Loesung zu verbieten, ist sowohl paraktisch als auch akademisch wenig foerderlich. Ein Problem in der Praxis sowie in der Theorie begegnet man meist mit allen zur Verfuegung stehen Mitteln. Auch fallen grundlegende Datenstrukturen wie Listen weg, da sie beim Sortiren die Objekte an sich nicht kopieren. Es wird ja nicht ohne Grund die Komplexitaet abhaengig von der Anzahl der Vergleiche angegeben. Was waere der 100m-Laeufer wenn er auf sein rechtes Bein verzichtet oder rueckwaerts rennt?
Ok, dann sagen wir, dass es kein Computerproblem ist, sondern ein Realweltproblem, also tatsächlich Büchersortieren. Da gibt es keine Pointer. Und ich habe ein ganz fieses Bücherregal, wo Pixiebücher mit dicken Wälzern gemischt sind, da kann volkards Bibliothekar keine schönen Stapel schichten
.SideWinder schrieb:
Also wir haben an der Universität für solche Fälle Selection Sort gelernt. Hat zwar im schlimmsten Fall n² Vergleiche, aber das stört nicht weil es selbst im allerschlimmsten Fall nur zu n Moves kommt.
Interessant, das heißt ja dass die Sortierstrategie die die meisten Menschen intuitiv einsetzen würden (auch wenn sie es nicht Selection Sort nennen, ist es das doch), schon ziemlich optimal ist.
Bucket- und Radixsort muss ich mir erstmal angucken, die habe ich bisher immer als Exoten angesehen und nie richtig ernst genommen.
-
SeppJ schrieb:
Und ich habe ein ganz fieses Bücherregal, wo Pixiebücher mit dicken Wälzern gemischt sind, da kann volkards Bibliothekar keine schönen Stapel schichten
.Ich dachte nie an Stapel mit Buch-Auf-Buch, sondern an Buch-Neben-Buch, gerne mit Buchstützen gefaßt. Um genau zu sein, sogar mit schägen Büchern, http://www.google.de/images?q=buchstütze+falling&um=1&hl=de&tbs=isch%3A1&sa=2
[/quote]Interessant, das heißt ja dass die Sortierstrategie die die meisten Menschen intuitiv einsetzen würden (auch wenn sie es nicht Selection Sort nennen, ist es das doch), schon ziemlich optimal ist.[/quote]
Muttu aber viel genauer beobachten.Selection Sort ist nicht die Strategie, die die meisten Menschen intuitiv einsetzen.
Bei Spielkarten machen sie einen Radix-Schritt nach den vier Farben und als Endstufe insertion sort.Wenn Du mir jemanden zeigst, der den ganzen Stapel nach der kleinsten Karte untersucht, sie rauslegt, dann wieder nach der kleinsten sucht, sie rauslegt..., dann glaube ich einfach mal nicht, daß der noch gesund ist.
-
SeppJ schrieb:
[...]Ein Beispiel wäre ein Mensch, der ein Bücherregal alphabetisch sortiert. Es ist trivial zwei Bücher zu vergleichen, man kann sogar ziemlich gut abschätzen wo das Buch hinterher landen wird. Daher wird ein Mensch mit einem einfachen Selection Sort schneller sein als ein Mensch der ein fortschrittliches MixSort benutzt, dafür aber alle Bücher aus dem Regal holen muss und zigmal vertauschen muss.[...]P.P.S.: Und keine Pointerindirektion. Ja, das wäre eine sehr gute Lösung und ich werde es vermutlich auch so machen. Ich bin aber eher an der akademischen Fragestellung interessiert, wie man die Anzahl der Vertauschungen minimiert, weil ich beim Nachdenken über das Problem neugierig geworden bin.
Akademisch würde man auch die originalen Bücher nehmen und tauschen. Man würde wohl kaum Abschriften von den Büchern anfertigen, diese dann tauschen, und die Originale verbrennen. Außerdem hat man dann noch das Problem, dass man einen neuen Typen braucht, der die Asche aufnehmen kann. Und wenn man oft sortiert, und die ganze Asche in einen Vektor packt, bekommt man irgendwann ein Speicherproblem.
-> Pointer. Auch akademisch.
