Алгоритм - структура обрабатываемых данных. Индексированные элементы массива. Сортировка как процесс перегруппировки множества объектов в некотором определенном порядке. Цель – облегчить последующий поиск элементов в таком отсортированном множестве.
Аннотация к работе
Сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Мы встречаемся с отсортированными объектами в телефонных книгах, в списках подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах - почти везде, где нужно искать хранимые объекты. Практически каждый алгоритм сортировки можно разбить на три части: - сравнение, определяющее упорядоченность пары элементов; собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, сока все элементы множества не будут упорядочены. алгоритм индексированный сортировка порядокНазвание метода отражает его сущность: на каждом шаге самый «легкий» элемент поднимается до своего места («всплывает»). Для этого мы просматриваем все элементы снизу вверх, берем пару соседних элементов и, в случае, если они стоят неправильно, меняем их местами. Так как за каждый шаг на свое место встает ровно 1 элемент (самый «легкий» из оставшихся), то нам потребуется выполнить N шагов. Текст процедуры сортировки можно записать так: procedure bubble_sort(var a:list; n : integer); Для передачи массивов в процедуры и функции, необходимо определить новый тип: type list = array[0..10000] of integer;Рассмотрим еще один квадратичный алгоритм, который, однако, является оптимальным по количеству присваиваний и может быть использован, когда по условию задачи необходимо явно минимизировать количество присваиваний. Суть метода заключается в следующем: мы будем выбирать минимальный элемент в оставшейся части массива и приписывать его к уже отсортированной части. Повторив эти действия N раз, мы получим отсортированный массив. procedure select_sort(var a : list; n : integer);Куча - это структура данных, которая может выдавать минимальный (или максимальный) элемент за О(1), добавление нового элемента или добавление минимального элемента происходит О(LOGN) (где N - количество элементов в куче). Другие операции над кучей не определены (хотя при необходимости могут быть введены, однако эффективность их будет невысокой, и они обязаны поддерживать свойства кучи). Мы будем выбирать из кучи самый большой элемент, и записывать его в начало уже отсортированной части массива (сортировка выбором в обратном порядке). Т.е. отсортированный массив будет строиться от конца к началу. Такие ухищрения необходимы, чтобы не было необходимости в дополнительной памяти и для ускорения работы алгоритма - куча будет располагаться в начале массива, а отсортированная часть будет находиться после кучи. Для остальных элементов вызовем процедуру «проталкивания» по куче, начиная с n/2 до 0. procedure down_heap(var a : list; k : integer; n : integer);Хоар назвал этот метод быстрой сортировкой (Quicksort). Выбирается некий опорный элемент и все числа, меньшие его перемещаются в левую часть массива, а все числа большие его - в правую часть. Таким образом, процедура сортировки должна принимать указатель на массив и две переменные, обозначающие левую и правую границу сортируемой области. Однако в некоторых задачах, где сутью является исключительно сортировка, хитрое жюри специально подбирает тесты так, чтобы «завалить» стандартную быструю сортировку с выбором опорного элемента из середины. Приведем текст процедуры быстрой сортировки с выбором среднего элемента в качестве опорного: procedure quick_sort(var a : list; left, right : integer);Сортировка слияниями также основывается на идее, которая уже была нами затронута при рассмотрении алгоритма поиска двух максимальных элементов. Затем из двух пар создадим упорядоченные четверки и т.д. Интерес представляет сам процесс слияния: для каждой из половинок мы устанавливаем указатели на начало, смотрим, в какой из частей элемент по указателю меньше, записываем этот элемент в новый массив и перемещаем соответствующий указатель. Опишем процедуру слияния следующим образом: procedure merge(var a, b : list; c, d, e : integer); Далее опишем нерекурсивную процедуру сортировки слиянием. procedure merge_sort(var a : list; n : integer);Сортировка означает перестановку этих элементов в новом порядке Ак1 , Ак2, …, Akn. Хорошей по критерию памяти считается такая сортировка, при которой данные сортируются в том же самом массиве, где находились исходные данные. При оценке времени сортировки используют два показателя: число сравнений ключей (С), число пересылок данных (М). Хорошими по времени считаются сортировки, в которых число сравнений С=N*Ln(N). К простым, то есть не очень хорошим, относятся такие сортировки, в которых число сравнений пропорционально квадрату размерности N исходного массива С?N2.Название регулярный тип (или ряды) массивы получили за то, что в них объединены однотипные (логически однородные) элементы, упорядоченные (урегулированные) по индексам, определяющим положение каждого элемента в массиве.