prev up next

Previous: Radix Sort Up: Sortieren Next: Objektorientierte Programmierung

Externes Sortieren

Problem: Sortieren auf Medien mit sequentiellem Lese- und Schreibzugriff.
Lösung: Wiederholtes Mischen von bereits sortierten Teilfolgen.

Ein Lauf ist eine monoton nicht fallende Teilfolge.

$\underbrace{3~~~~~~ 7~~~~~~ 8}$ $\underbrace{2~~~~~~ 9}$ $\underbrace{4}$ $\underbrace{1~~~~~~ 5~~~~~~ 6}$
Lauf Lauf Lauf Lauf
Gegeben 3 Magnetbänder, mit initial $0$, $ n $, $0$ Läufen. Je 2 Bänder mischen ihre Läufe zusammen auf das dritte:

Band A: 0 0 8 3 0 2 1 0
Band B: 21 13 5 0 3 1 0 1
Band C: 0 8 0 5 2 0 1 0
                sortiert

(In jeder Spalte ist die momentane Anzahl der Läufe vermerkt.)

Allgemeine Regel:

     Sei $fib(i)$ die $i$-te Fibonacci-Zahl.

    
Es habe Band A $fib(i)$ Läufe
  B $fib(i-1)$ Läufe
  C 0 Läufe

     dann mische $fib(i-1)$ Läufe von A und B zusammen auf Band C.


prev up next
Previous: Radix Sort Up: Sortieren Next: Objektorientierte Programmierung