Subato

Resource Files

Selectionsort und Insertionsort

Beurteilen Sie die Sortierverfahren Insertionsort und Selectionsort und begründen Sie jeweils:

  • Geben Sie die Best Case und Worst Case Komplexität für die Anzahl der Schreiboperationen und die Anzahl der Vergleiche von Array-Elementen an.
  • Alice hat ein sehr großes Eingabearray gegeben (z.B. $n {>} 10.000.000$). Sie benötigt aber nur die hundert größten Zahlen (z.B. $k{=}100$) in sortierter Reihenfolge. Welches der beiden Verfahren lässt sich leicht für diesen Anwendungsfall modifizieren? Geben Sie entsprechenden Pseudo-Code an, sowie die Komplexität (Anzahl der Vergleiche) in Abhängigkeit von $n$ und $k$.


You are not logged in and therefore you cannot submit a solution.