großer Sortierer aus kleinen Sortierern aufbauen

[Max (Gast)]

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

[Uhu U. (uhu)]

Guck die mal quicksort an...

[Max (Gast)]

Sehr witzig.
Quicksort hat ja wohl mal gar nichts mit der Aufgabenstellung zu tun.

Max

[Muraer (Gast)]

Wenn man es rekursiv macht...ja

[Unbekannter (Gast)]

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...

[Uhu U. (uhu)]

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...

[Läubi .. (laeubi)]

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/sortier.htm

Aus "zwei elemente sortierer" werden größere...

[Unbekannter (Gast)]

> sogar als Animation...

Ja und? Ist trotzdem kein Sortiernetzwerk!

[Gast (Gast)]

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? ^^

[Jörg (Gast)]

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

[Hans-jürgen H. (hjherbert)]

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)

[daniel (Gast)]

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.

[yalu (Gast)]

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 :)