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:
Tipps: Nicht jedes Verfahren ist gleich gut geeignet.