next up previous contents
Nächste Seite: Aufgabe 10 Aufwärts: Angaben Vorherige Seite: Aufgabe 8   Inhalt

Aufgabe 9

Man entwickle ein Unterprogramm, das zu zwei gegebenen Mengen von ganzen Zahlen (eindimensionale Arrays von Typ INTEGER) die Vereinigungsmenge liefert.
Außerdem sollen die gegebenen Mengen aufsteigend sortiert zurückgeliefert werden, wobei mehrfach auftretende Elemente nur einmal in den Ergebnisfeldern (Menge!) auftreten sollen.

Programmtyp: SUBROUTINE, nichtrekursiv.
Transiente Parameter: die gegebenen Zahlenmengen wie oben spezifiziert.
Ausgangsparameter: Die Vereinigungsmenge

Zum Sortieren verwende man (in einem eigenen Unterprogramm) den "Bubble-Sort"- Algorithmus:
Das einfachste Sortierverfahren ist das Sortieren mit paarweisem Austausch:
Der Sortieralgorithmus beginnt den Vergleich am Ende des Feldes. Bei jedem Durchlauf wird von hinten nach vorne vorgehend jedes Element mit seinem unmittelbaren Vorgänger verglichen und gegebenfalls vertauscht.
Am Ende des 1. Durchlaufs ist der kleinste Schlüssel am Anfang der neuen Schlüsselfolge (n-1 Vergleiche). Im zweiten Durchlauf wird wiederum am Folgenende begonnen, der 2. Schlüssel wird in Position gebracht (nur mehr n-2 Vergleiche), u.s.w. Sobald keine Vertauschung mehr nötig ist, ist man fertig (spätestens nach n-1 Durchläufen, d.h. n(n-1)/2 Vergleichen!


Reinfried O. Peter 2001-09-07