|
Anzeige
|
großer Sortierer aus kleinen Sortierern aufbauen
Gast
#1085521
Hallo, es ist ja möglich einen Sortierer, der z.B. 100 Zahlen sortieren kann aus vielen kleineren, die z.B. jeweils nur 2 Zahlen sortieren können, aufzubauen. Weiß jemand wie die Theorie heißt, die sich damit beschäftigt? Wo gibt es Internetseiten zu diesem Thema? Maximilian Guck die mal quicksort an...
Gast
#1085536
Sehr witzig. Quicksort hat ja wohl mal gar nichts mit der Aufgabenstellung zu tun. Max
Gast
#1085537
Wenn man es rekursiv macht...ja
Gast
#1085567
Meinst Du Sortiernetzwerke? In der Knuth-Bibel ist dazu einiges drinn. Es gibt eine Liste mit optimalen Sortiernetzwerken verschiedener Größe. Aber die Liste ist relativ klein, und es gibt einen Haufen ungelöster Fragen zu Sortiernetzwerken. Da kannst Du noch richtig berühmt werden, wenn Du das eine oder andere Rätsel dazu löst... Max wrote: > Sehr witzig. > Quicksort hat ja wohl mal gar nichts mit der Aufgabenstellung zu tun. http://de.wikipedia.org/wiki/Quicksort - sogar als Animation... http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/sortier.htm Aus "zwei elemente sortierer" werden größere...
Gast
#1085665
> sogar als Animation...
Ja und? Ist trotzdem kein Sortiernetzwerk!
Gast
#1085694
Lass mich raten: Du machst bei einem ganz bestimmen Wettbewerb mit, bei dem du in die 2. Runde gekommen bist und nun die Lösung für die 1. Aufgabe suchst? ^^
Gast
#1085731
Dieses Problem tritt z.B. beim Sortieren sehr grosser Datenmengenauf (Daten passen z.B.nicht komplett in den Arbeitsspeicher etc.). Im Prinzip liefert Bubblesort (und Derivate) schon einen Lösungsansatz, es ist ja jedes Element für sich sortiert. Nimmst du nicht ein Element als Teilliste, sondern mehrere Elemente, dann musst du alle Teillisten in einer Liste anordnen und zwischen benachbarten Teillisten nach einem Teillistensortierschritt immer wieder Elemente austauschen. Der Algo terminiert, wenn kein Austausch zwischen den Teilmengen erfolgen muss. Der Austausch zwischen den Teilmengen kann z.B. per Merge erfolgen (siehe Merge-Sort). Gruss Jörg Also schreibst Du ein Sortierprogramm, das aus Deiner Tabelle t, die n
Elemente hat, die Elemente k bis l sortieren kann:
ssort(t,k,l)
{
if l-k = 0 return ;
if l-k = 1 return ;
if l-k = 2
{
if t[k] > t[l] then vertausche t[k] mit t[l]
return ;
}
j = (k+l)/2 ; Die Tabelle halbieren
ssort(t, k,j) ; Die erste Hälfte sortieren
ssort(t,j,l) ; Die zweite Hälfte sortieren
rem Die beiden Teilsortiereergebnisse miteinander mischen (merge)
repeat until k >= j or j>= l
if t[k] <= t[j] then ++k ; continue
else
verschiebe t[j] vor t[k]
++k
++j
endif
endrepeat
Mit "verschiebe" ist etwa folgendes gemeint:
x = t[k]
for i = k to j-2
t[i] = t[i+1]
t[j-1] = x
Um die ganze Tabelle zu sortieren muss das Hauptprogramm erst die
Tabelle t füllen und dann aufrufen ssort(t,0,n-1) (oder vielleicht
sort(t,1,n)
Viel Spaß beim Umsetzen.
Poste dann dein Programm, wenn es fertig ist.
(ich hatte mein Programm mal sortmerg genannt, sollte unter DOS nur 8
Buchstaben haben, andere, die gerne Worthälften vertauschen, nennen den
Algorithmus "mergesort", danach mal recherchieren)
Gast
#1086091
wie schon genannt bubblesort ist die idee, die du beschreibst dabei läuft man drüber (sequenziell) und tauscht sich nur mit dem nachbarstelle aus, dabei propagandieren die kleinen werte nach links. unter der annahme, dass kleinste zahl ganz rechts war, sind n-1 durchläufe notwendig. interessant wird bubblesort für hardwareimplementierung. da könnte man paarweise in der zeit parallel tauschen. davon abgesehen, lässt sich rekursive quicksort schlecht auf einem fpga implementieren. noch ein vorteil ist, dass alles in-place in einem buffer abläuft.
Gast
#1086509
Um so etwas geht es dem Fragesteller wohl: http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo12.php Gast schrieb: > Du machst bei einem ganz bestimmen Wettbewerb mit, bei dem du in die > 2. Runde gekommen bist und nun die Lösung für die 1. Aufgabe suchst? > ^^ Die Aufgabe dieses Wettbewerbs hat zwar solche Sortiernetzwerke zum Thema, jedoch sind die Fragen so beschaffen, dass man zur Lösung nicht die Theorie verstanden haben muss. Es geht dort mehr um die programm- technische Implementierung, die Algorithmen an sich sind relativ leicht zu finden. Und um den Teilnehmern nicht den Spaß zu verderben, werden wir hier zur Wettbewerbsaufgabe natürlich keine Lösungsansätze posten :) Antwort schreiben |
Anzeige
|
