Aufgabe 1

Schreiben Sie eine rekursive Funktion ravel(l:list):list, die eine Liste erzeugt, in der alle Atome aus l "linear" aufgelistet sind.

Beispiel: ravel([[1,2],[[3],4,5],6]) = [1,2,3,4,5,6]


Aufgabe 2

a) Bestimmen Sie den Aufwand O(f(n)) beim Sortieren einer bereits sortierten Zahlenfolge von n Elemente mit

  • Sortieren durch direktes Einfügen (insertionsort),
  • Sortieren durch direktes Auswählen (selectionsort),
  • Sortieren durch direktes Austauschen (bubblesort),
  • Quicksort und
  • natürlichem Mischsortieren (naturalmergesort).

b) Bestimmen Sie die Aufwände wie in a) für eine absteigend sortierte Folge.


Abzugeben bis Dienstag, 29.6.2004, 24h