Сортування файлів розміром більшим, ніж оперативна пам’ять

Abstract

Сортування – це впорядкування за певною характеристикою ланки об’єктів, що мають конкретні взаємозв’язки, або ж просто мають спільне поле характеристики. Вивчаючи курс АІСД, ми вже ознайомилися із основними методами сортування: бульбашка, вибором, вставками, пірамідальним, швидким, злиттям. Усі ці алгоритми можна класифікувати як алгоритми внутрішнього сортування, тобто ті, у яких дані зберігаються у оперативній пам’яті комп’ютера, і якісь маніпуляції ми проводимо тільки з ними. На противагу алгоритмам внутрішнього сортування, існують алгоритми зовнішнього сортування – це спосіб сортування даних, які не вміщаються в оперативну пам’ять та є розташованими на периферійних пристроях. Важливою характеристикою є факт того, що внутрішнє сортування значно ефективніше зовнішнього, оскільки на звернення до оперативної пам’яті комп’ютера витрачається набагато менше часу, ніж до периферійних пристроїв. Тобто, до прикладу, відсортувати масив із певною кількістю елементів, що знаходиться в оперативній пам’яті в рази простіше, ніж аналогічний масив, що записаний на Ufile. Простими словами, зовнішнім сортуванням ми будемо впорядковувати файли, що мають розмір значно більший за середньостатистичний розмір сучасних оперативок – файли розміром в Гігабайти.