Методы и алгоритмы сортировки массивов

Содержание:

Введение…………………………………………………………………………..3

1. Алгоритмы методов сортировки………………………………….4

1.1 Массив………………………………………………………………………...4

1.2 Сортировка массива………………………………………………………….7

2. Програмная реализация методов сортировки……………..12

2.1 Сортировка пузырьком……………………………………………………..12

2.2 Сортировка вставками……………………………………………………....13

2.3 Быстрая сортировка. ………………………………………………………..15

3. ПРИМЕНЕНИЕ СОРТИРОВКИ……………………………………………..18

Заключение………………………………………………………………………19

Список литературы……………………………………………………………...20

 

 

Введение

 

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

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

В данной курсовой работе рассматривается один из способов обработки массивов - сортировка массива.

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

Научная значимость данной работы состоит в описании и исследовании наиболее популярных методов сортировки. Практическая значимость темы «Сортировка массивов» состоит в анализе проблем реализации и использовании различных видов сортировок.

 

 

 

 

 

 

 

1. Алгоритмы методов сортировки

1.1 Массив

 

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

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

Название регулярный тип (или ряды) массивы получили за то, что в них объединены однотипные (логически однородные) элементы, упорядоченные (урегулированные) по индексам, определяющим положение каждого элемента в массиве.

Элементами массива могут быть данные любого типа, включая структурированные. Тип элементов массива называется базовым. Особенностью языка Паскаль является то, "что число элементов массива фиксируется при описании и в процессе выполнения программы не меняется.

Элементы, образующие массив, упорядочены таким образом, что каждому элементу соответствует совокупность номеров (индексов), определяющих его местоположение в общей последовательности. Доступ к каждому отдельному элементу осуществляется путем индексирования элементов массива. Индексы представляют собой выражения любого скалярного типа, кроме вещественного. Тип индекса определяет границы изменения значений индекса. Для описания массива предназначено словосочетание array of (массив из).

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

Если в такой форме описания массива задан один индекс, массив называется одномерным, если два индекса — двумерным, если n индексов — n-мерным. Одномерный массив соответствует понятию линейной таблицы (вектора), двумерный — понятию прямоугольной таблицы (матрицы, набору векторов). Размерность ограничена только объемом памяти конкретного компьютера. Одномерные массивы обычно используются для представления векторов, а двумерные — для представления матриц.

Элементы массива располагаются в памяти последовательно. Элементы с меньшими значениями индекса хранятся в более низких адресах памяти. Многомерные массивы располагаются таким образом, что самый правый индекс возрастает самым первым.

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

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

 

Операции с элементами массива.

Практически все операции с массивом следует проводить поэлементно в цикле. Для обработки элементов массива  удобно использовать цикл  for ...do, а верхний индекс массивов определять как предварительно описанную константу. В этом случае все циклы по обработке массива будут заканчиваться значением этой константы.  При изменении числа элементов массива,  в программе достаточно изменить значение константы (т.к. все циклы зависят от константы).

Стандартные функции Low() и High() действуют для идентификаторов типа массива. Они возвращают нижние и верхние границы массива. Стандартная функция Length() возвращает количество элементов первого измерения массива (для матрицы возвращается число строк)

Ввод-вывод элементов одномерного массива.

Паскаль не имеет средств ввода-вывода всего массива, поэтому ввод-вывод следует организовывать поэлементно (см. рис.1, 2). Блок-схема, изображённая на рис.1 и 2 может быть реализована циклами while, for.

Рис. 1 Ввод элементов массива.

Рис.2 Ввод элементов массива

 

 

 

 

2. Сортировка массива

В большинстве случаев, массивы применяются для хранения большого количества однотипной информации, создания и организации баз данных и банков данных и т.д. Во многих случаях номер (индекс) элемента в массиве не играет большой роли. Важно именно его значение, т.е. сама информация. Базы и банки данных, в свою очередь, необходимы не только для того, чтобы «складывать» в них информацию, но и для того, чтобы в любой момент была возможность удобного и быстрого доступа к ней. В обычном «неотсортированном» массиве информацию найти можно, но только уже известными способами последовательного перебора - просмотра всех  его элементов, до тех пор, пока нужный элемент не будет обнаружен. Этот самый простой метод обладает только одним, но очень существенным недостатком — на поиск одного элемента уходит много времени. Все остальные методы поиска информации намного эффективнее, быстрее, но применяются только в упорядоченных, отсортированных массивах. Поэтому часто возникает задача об упорядочивании массива.

Сортировка пузырьком (Bubble sort).

Один из самых популярных методов сортировки — "пузырьковый" метод основан на том, что в процессе исполнения алгоритма более "легкие" элементы массива постепенно "всплывают". Особенностью данного метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов. Алгоритм пузырьковой сортировки по убыванию состоит в последовательных просмотрах снизу вверх (от начала к концу) массива. Если соседние элементы таковы, что выполняется условие, согласно которому элемент справа больше элемента слева, то выполняется обмен значениями этих элементов.

"Пузырьковая" сортировка имеет очень плохие  временные характеристики. Она имеет  только учебно-исторический интерес  и не может быть рекомендована  для практического использования.

Сортировка вставками (Insertion sort).

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

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

Быстрая сортировка (Quicksort).

QuickSort является  существенно улучшенным вариантом  алгоритма сортировки с помощью  прямого обмена (его варианты  известны как «Пузырьковая сортировка»  и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит  в том, что в первую очередь  производятся перестановки на  наибольшем возможном расстоянии  и после каждого прохода элементы  делятся на две независимые  группы. Любопытный факт: улучшение  самого неэффективного прямого  метода сортировки дало в результате  один из наиболее эффективных  улучшенных методов.

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

1) Выбираем  в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом;

2) Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:

Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.

Вычисляется индекс опорного элемента m.

Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.

Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.

Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.

Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение;

3) Рекурсивно  упорядочиваем подмассивы, лежащие  слева и справа от опорного  элемента.

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

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

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

Сортировка выбором (Selection sort).

Упорядочиваем постепенно массив, заполняя первую позицию неупорядоченной части минимальным элементом из неупорядоченной части.

Шаги алгоритма:

1)     Находим номер минимального значения в текущем списке;

2) Производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции);

3) Сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы. Для реализации устойчивости алгоритма необходимо в пункте 2 минимальный элемент непосредственно вставлять в первую неотсортированную позицию, не меняя порядок остальных элементов;

Метод оказывается эффективным только на маленьких массивах (не более 10), на массивах больших размеров алгоритм оказывается крайне не эффективным.