Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Способы записи алгоритмов).pdf

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

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

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

В результате алгоритмы сортировки на больших объемах данных оказываются непрактичными.

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

Первый этап: прочитать S записей и отсортировать их с помощью подходящей внутренней сортировки. Отсортированный набор записей перепишем в файл A. Далее S записей прочитывается еще раз и сортируется с дальнейшем переписывание в файл B. При этом отсортированные блоки пишутся попеременно в файл A и файл B. Снизу показан алгоритм, который реализует первый этап:

CreateRuns(S)

S размер создаваемых отрезков

CurrentFile=A

while конец входного файла не достигнут do

read S записей из входного файла

sort S записей

if CurrentFile=A then

CurrentFile=B else

CurrrentFile=A

end if

end while

Теперь данный файл разбит на отсортированные отрезки.

Второй этап (слияние данных отрезков): процесс слияния аналогичен функции MergeLists, только вместо того, чтобы записи переписывать в новый массив они будут записаны в новый файл. Для начала начнем читать половинки первых отрезков из фалов A и B. Чтение производится строго по половине отрезков, так как в памяти может находится только одновременно S записей, а требуются файлы из обоих файлов. Далее половинки отрезков сливаются в один отрезок файла C. После того, как одна половинка закончится, то следует прочесть вторую половинку из этого же файла. По окончанию обработки одного из отрезков, конец второго отрезка будет переписан в файл C.

После завершения слияния двух отрезков из файла A и B, следующие два отрезка сливаются в файл D. Процесс слияния отрезков продолжается с попеременной записью слитых отрезков в файлы C и D.

По завершению сортировки мы получаем два файла, которые разбиты на отсортированные отрезки длины 2S. После чего процесс повторяется, при этом отрезки читаются из файлов C и D, а слитые отрезки 4S запишутся в файл A и B. В конце отрезки сольются в один отсортированный список в одном из файлов. Снизу показан алгоритм показан алгоритм, который реализует второй этап:

PolyPhaseMerge(S)

S размер исходных отрезков

Size=S

Input1=A

Input2=B

Current Output=C

while not done do

while отрезки не кончились do

слить отрезок длины Size из файла Input1

с отрезком длины Size из файла Input2

записав результат в CurrentOutput

if (CurrentOutput=A) then

CurrentOutput=B

elsif (CurrentOutput=B) then

CurrrentOutput=A

elsif (CurrentOutput=C) then

Currrent Output=D

elsif (CurrentOutput=D) then

CurrrentOutput=C

end if

end while

Size=Size*2

if (Input1=A) then

Input1=C

Input2=D

Current Output=A

else

Input1=A

Input2=B

CurrentOutput=C

end if

end while /6, с.112-115/.

Исходя из вышеизложенного стоит отметить, что алгоритмы сортировки делятся на разные виды. Каждый из которых занимает свое определенное место в программировании.

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

Заключение

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

Как правило, алгоритм служит не для решения какой-то конкретной задачи, а для решения определенного класса задач.

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

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

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