nicht rekursiv (iterativ)

Wie schon bewiesen wurde oder noch zu beweisen ist, hat jedes rekursive Programm ein nicht-rekursives Analogon, das äquivalent dazu ist. Dies heisst jedoch nicht, daß die Reihenfolge der Abarbeitung bei beiden Implementierungen gleich bleibt.

Im folgenden sei die einfachste nicht-rekursive Lösung des MergeSorts aufgezeigt. Tatsächlich führt diese Implementierung die Abarbeitung in etwas anderer Weise durch als die rekursive Variante. Wie ersichtitlich in der nachstehenden Tabelle, ist die Arbeitsweise der hier vorgestellten iterativen Implementierung eine andere. Es werden von links nach rechts kleine Mengen, zuerst bestehend aus einem Element, zu Zweiermengen mit Hilfe der merge-Funktion gebildet. Dananch werden diese Zweiermenge zu Vierergruppen gemischt. Dann diese zu Achtermengen ... usw.


18 35 22 10 12 25 13 31 1 8 0 16 4
18 35                      
    10 22                  
        12 25              
            13 31          
                         
                1 8      
                    0 16  
                        4
10 18 22 35                  
        12 13 25 31          
                0 1 8 16  
                        4
10 12 13 18 22 25 31 35          
                0 1 4 8 16
0 1 4 8 10 12 13 16 18 22 25 31 35


In der folgenden Implementierung gibt die Variable step die Größe der zu mischenden Mengen an. left und right dagegen begrenzen begrenzen die Menge. In der äußeren Schleife wird das Ablaufen der Iterationen kontrolliert. Die innere Schleife dagegen sorgt für die jeweilige Aufteilung in Mengen und ruft die merge-Funktion auf, um die entstehenden Mengen zu sortieren. Die beiden Parameter definieren die zu sortierende Menge. data ist die Adresse des Arrays, N die Anzahl Elemente im Array.


\begin{listing}{1} void iterative_merge_sort( int * data, int N ) { int step;... ...or( i = left; i < right; i++ ) data[i] = buffer[j-left]; } } } \end{listing}

Nächste Seite  Aufwärts  Vorherige Seite  Inhalt 


Nächste Seite: ``in-place'' Aufwärts: Implementierung Vorherige Seite: rekursiv   Inhalt

2002-05-09