www.mikrocontroller.net

Forum: PC-Programmierung großer Sortierer aus kleinen Sortierern aufbauen


Autor: Max (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Uhu Uhuhu (uhu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Guck die mal quicksort an...

Autor: Max (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sehr witzig.
Quicksort hat ja wohl mal gar nichts mit der Aufgabenstellung zu tun.

Max

Autor: Muraer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn man es rekursiv macht...ja

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Uhu Uhuhu (uhu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
http://www.iti.fh-flensburg.de/lang/algorithmen/so...

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

Autor: Unbekannter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> sogar als Animation...

Ja und? Ist trotzdem kein Sortiernetzwerk!

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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? ^^

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Hans-jürgen Herbert (hjherbert) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)

Autor: daniel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Um so etwas geht es dem Fragesteller wohl:

  http://www-i1.informatik.rwth-aachen.de/~algorithm...

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

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.