Wir betrachten in dieser Aufgabe eine Variante des Sortierproblems: Es müssen nicht mehr alle n Zahlen sortiert werden, sondern es sollen nur die k kleinsten Zahlen des Arrays (sortiert) zurückgegeben werden. Hierbei sei k deutlich kleiner als n.

Beschreiben Sie, ob/wie die folgenden Algorithmen aus der Vorlesung angepasst werden könnten, um dieses Problem möglichst effizient zu lösen. Geben Sie jeweils die Worst-Case-Komplexität in Abhängigkeit von n und k an:

• Insertionsort
• Quicksort
• Heapsort

Tipps: Nicht  jedes Verfahren ist gleich gut geeignet.