Сортировки одномерного массива - Курсовая работа

Сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Мы встречаемся с отсортированными объектами в телефонных книгах, в списках подоходных налогов, в оглавлениях книг, в библиотеках, в словарях, на складах - почти везде, где нужно искать хранимые объекты. Практически каждый алгоритм сортировки можно разбить на три части: - сравнение, определяющее упорядоченность пары элементов; собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, сока все элементы множества не будут упорядочены. алгоритм индексированный сортировка порядокНазвание метода отражает его сущность: на каждом шаге самый «легкий» элемент поднимается до своего места («всплывает»). Для этого мы просматриваем все элементы снизу вверх, берем пару соседних элементов и, в случае, если они стоят неправильно, меняем их местами. Так как за каждый шаг на свое место встает ровно 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.Название регулярный тип (или ряды) массивы получили за то, что в них объединены однотипные (логически однородные) элементы, упорядоченные (урегулированные) по индексам, определяющим положение каждого элемента в массиве.

Содержание

Введение

1. Основная часть

1.1 Сортировка пузырьком

1.2 Сортировка прямым выбором

1.3 Пирамидальная сортировка

1.4 Быстрая сортировка

1.5 Сортировка слиянием

2. Сравнение производительности сортировок

3. Массивы

3.1 Описание типа "массив"

Заключение

Список использованной литературы