Внутренняя сортировка

— Внутренняя сортировка это любой процесс сортировки данных, который полностью происходит в основной памяти компьютера. Это возможно, когда данные, подлежащие сортировке, достаточно малы и могут храниться в основной памяти. как жесткий диск. Любое чтение или запись данных на этот медленный носитель и обратно может значительно замедлить процесс сортировки. Эта проблема имеет последствия для различных алгоритмов сортировки .

Некоторые распространенные алгоритмы внутренней сортировки включают в себя:

Рассмотрим сортировку пузырьком , при которой соседние записи меняются местами, чтобы расположить их в правильном порядке, так что создается впечатление, что записи «пузырятся» вверх и вниз по пространству данных. Если это нужно делать порциями, то, отсортировав все записи в чашке 1, мы переходим к чашке 2, но обнаруживаем, что некоторым записям в чашке 1 нужно «пропустить» чашку 2, и наоборот. и наоборот (т. е. в блоке 2 есть записи, принадлежащие блоку 1, и записи в блоке 1, которые принадлежат блоку 2 или более поздним блокам). Это приведет к тому, что фрагменты будут считываться и записываться обратно на диск много раз, когда записи пересекают границы между ними, что приведет к значительному снижению производительности. Если все данные можно хранить в памяти как один большой фрагмент, такого снижения производительности можно избежать.

С другой стороны, некоторые алгоритмы справляются с внешней сортировкой гораздо лучше . Сортировка слиянием разбивает данные на фрагменты, сортирует фрагменты с помощью какого-либо другого алгоритма (возможно, пузырьковой сортировки или быстрой сортировки ), а затем повторно объединяет фрагменты два на два, чтобы каждый повторно объединенный фрагмент находился в порядке. Этот подход сводит к минимуму количество операций чтения и записи фрагментов данных с диска и является популярным методом внешней сортировки.