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

Видео: Java - алгоритмы: Быстрая сортировка!

При разработке различных программ практически всегда программистам приходится прибегать к использованию сортировки, чтобы оптимизировать алгоритмы работы, улучшить производительность операции поиска и т. п. Сегодня существует множество различных методик расположения элементов в необходимом порядке: сортировка слиянием, с помощью ключа и т. д. Сортировка представляет собой комплекс операций, результат выполнения которых приводит к упорядочиванию однотипных объектов в порядке убывания или возрастания – в зависимости от требований конкретной задачи.

Видео: Использование функции ВПР в MS Excel 2007

Все многообразие алгоритмов сортировки можно разделить на две категории: упорядочивание массивов и расположение в определенном порядке файлов. Первый тип объектов может располагаться не только в оперативной памяти, но и на некотором носителе при условии, что доступ к нему открыт напрямую. Вторая категория объектов должна находиться на материальном носителе: диске или магнитной ленте.

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

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

Основное отличие последовательных файлов от файлов с предоставлением прямого доступа заключается в том, что они могут размещаться на носителях, к которым сложно организовать постоянный прямой доступ. Кроме того, такие файлы обычно не используют фиксированную длину для хранимых записей. Из-за этих особенностей последовательные файлы применяются только в двух ситуациях:

– при необходимости использования носителя информации, ориентированного на последовательный доступ-

– когда удобно использовать переменную длину записей.

Сортировка слиянием достаточно часто используется в современных программных средствах. Связано это с широким распространением последовательных файлов. Например, практически все текстовые файлы носят последовательный характер. Несмотря на удобство рассмотрения последовательно организованного файла как массива данных, такой подход невозможен, т. к. ко всем элементам файла обратиться невозможно аппаратно, физически.

Сортировка слиянием стала, по сути, единственным способом для сортировки последовательных файлов. Несмотря на то, что сегодня существуют иные методы упорядочивания последовательных файлов, этот метод остается одним из самых популярных. Сортировка естественным слиянием подразумевает разделение файла на две части, равные по объему информации. Далее из каждого файла происходит постепенное считывание каждого элемента из тех, которые доступны в настоящий момент. Упорядоченные элементы располагаются в необходимом порядке в третьем файле, который в дальнейшем разделяется на два сходных по размеру. Таким образом и производится сортировка слиянием. Паскаль, Си, Basic – большинство известных языков программирования поддерживают реализацию данного типа упорядочивания последовательных файлов.