Algorytmy i struktury danych · Senior · Pytanie 19 z 75
Jak posortować plik 200 GB na maszynie z 8 GB RAM?
- 1Podzielić według pierwszego znaku i sortować każdy plik osobno
- ✓Poprawna odpowiedź: Posortować kawałki mieszczące się w pamięci, potem scalanie k-drożne z kopcem
- 3Wczytać go przez memory-mapped I/O i wywołać zwykłe sortowanie
Wyjaśnienie
Zewnętrzne sortowanie przez scalanie zapisuje posortowane serie na dysk, a potem je scala, czytając każdą serię sekwencyjnie. Kopiec wybiera najmniejszą głowę spośród k serii w O(log k). Podział według pierwszego znaku nie wyrównuje rozmiarów części.