Внутренняя сортировка - Internal sort
An внутренняя сортировка любой процесс сортировки данных, который происходит полностью в пределах основная память компьютера. Это возможно, когда данные для сортировки достаточно малы, чтобы все они могли храниться в основной памяти. Для сортировки больших наборов данных может потребоваться хранить в памяти только фрагмент данных, поскольку он не умещается полностью. Остальные данные обычно хранятся на более крупном, но более медленном носителе, например на жестком диске. Любое чтение или запись данных на этот более медленный носитель и с него может значительно замедлить процесс сортировки. Эта проблема имеет значение для разных алгоритмы сортировки.
Некоторые распространенные алгоритмы внутренней сортировки включают:
- Пузырьковая сортировка
- Сортировка вставкой
- Быстрая сортировка
- Сортировка кучи
- Радиксная сортировка
- Выборочная сортировка
Рассмотрим Bubblesort, где соседние записи меняются местами, чтобы привести их в правильном порядке, так что записи кажутся «пузырящимися» вверх и вниз по пространству данных. Если это нужно делать по частям, то, когда мы отсортировали все записи в чанке 1, мы переходим к чанку 2, но мы обнаруживаем, что некоторые записи в чанке 1 должны «пролистать» чанк 2, и наоборот. наоборот (т. е. в блоке 2 есть записи, которые принадлежат блоку 1, и записи в блоке 1, которые принадлежат блоку 2 или более поздним блокам). Это приведет к тому, что блоки будут многократно считываться и записываться на диск, поскольку записи пересекают границы между ними, что приводит к значительному снижению производительности. Если все данные могут храниться в памяти как один большой блок, этого снижения производительности можно избежать.
С другой стороны, некоторые алгоритмы обрабатывают внешняя сортировка скорее лучше. А Сортировка слиянием разбивает данные на части, сортирует их по другому алгоритму (может быть, пузырьковая сортировка или Быстрая сортировка ), а затем повторно объединяет куски два на два, чтобы каждый рекомбинированный кусок был в порядке. Такой подход сводит к минимуму количество операций чтения и записи блоков данных с диска и является популярным методом внешней сортировки.