Algorithmen und Datenstrukturen · Senior · Frage 19 von 75
Wie sortiert man eine 200-GB-Datei auf einer Maschine mit 8 GB RAM?
- 1Sie nach dem ersten Zeichen aufteilen und jede Datei einzeln sortieren
- 2Teile sortieren, die in den Speicher passen, und dann per Heap k-fach zusammenführen
- 3Sie per Memory-Mapped I/O laden und normal sortieren
Antwort zeigen
Richtige Antwort: Teile sortieren, die in den Speicher passen, und dann per Heap k-fach zusammenführen
Erklärung
Externes Merge Sort schreibt sortierte Abschnitte auf die Platte und führt sie dann zusammen, wobei jeder Abschnitt sequenziell gelesen wird. Der Heap wählt in O(log k) den kleinsten Kopf unter k Abschnitten. Aufteilen nach dem ersten Zeichen gleicht die Teile nicht aus.