Файл: Алгоритмы сортировки данных (Что такое алгоритм).pdf

Содержание:

1. Введение

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

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

Программирование содержит некоторое количество локальных задач, которые встречаются не каждый день, а кто-то вообще с ними сталкивается лишь косвенно, но при всем этом они остаются одними из самых важных. Одной из таких задач является задача сортировки набора данных. В данной курсовой работе я найду определение понятия “алгоритм”, определю основные параметры оценки алгоритмов сортировки, рассмотрю различные реализации сортировок, найду их плюсы и минусы. Алгоритмы сортировки, рассмотренные в данной курсовой работе, были выбраны по принципу популярности (частоты использования) и потому что они являются базовыми алгоритмами для многих других, использующих их в качестве основы.

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

1. Метод пузырька
2. Шейкерная сортировка
3. Сортировка выбором
4. Сортировка вставкой
5. Метод Шелла
6. Быстрая сортировка
7. Пирамидальная сортировка
8. Сортировка слиянием

Оценивать эффективность алгоритмов будем по следующим критериям:

• Время. Основной параметр, характеризующий быстродействие алгоритма. Другое название - вычислительная сложность
• Память. Ряд алгоритмов требует выделения дополнительной памяти для временного хранения данных. При оценке не будет учитываться место, которое занимают исходный массив и сам код программы
• Естественность поведения — эффективность метода при обработке уже полностью или частично отсортированного набора данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику и работает эффективнее.

2. Что такое алгоритм

Алгоритм — это последовательность действий, которая направлена на достижение окончательного решения проблемы наиболее оптимальными и эффективными способами. Существует версия, что термин алгоритм произошел от имени древнего ученого Аль-Хорезми, который написал трактат «Книга о сложении и вычитании». Позднее один из переводчиков на латинский язык неправильно перевел имя ученого и вынес его в название книги — «Алгоритмии о счете индийском». Так этот термин проник в европейские языки и закрепился в них.

3. Пузырьковая сортировка

Пузырьковая сортировка так называется, потому что большие числа “всплывают” в правую часть массива, как пузырек воздуха всплывает в воде.

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

Данный алгоритм имеет среднюю и максимальную временные сложности O(n^2), алгоритм медленный и не эффективный. Поэтому в наше время он используется исключительно в обучающих целях. Дополнительной памяти не требуется, за исключением аллокации необходимых для итерации переменных-счетчиков.

Пример реализации алгоритма на языке Go:

func BubbleSort(array []int) {

for i := 0; i < len(array); i++ {

for j := i; j < len(array); j++ {

if array[i] > array[j] {

swap(&array, i, j)

}

}

}

}

func swap(array *[]int, i int, j int) {

var dArray = *array;

dArray[i], dArray[j] = dArray[j], dArray[i];

}

Пример сортировки массива:

4. Шейкерная сортировка

Другое название - сортировка перемешиванием. Это немного модифицированная пузырьковая сортировка. Сначала алгоритм точно такой же: смещаем максимальный элемент в самый конец массива. После этого “разворачиваемся” и идём в обратную сторону, при этом уже сдвигая в в начало минимальное значение. Отсортировав в массиве первый и последний элементы, повторяем итерацию. Процесс заканчивается, когда мы оказываемся в середине массива.

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

5. Сортировка выбором

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

Стоит отметить, что данная сортиировка является неусточивой.

Отличие устойчивых сортировок от неустойчивых в том, что если сравниваются не просто значения, а объекты по какому-то из свойств, то устойчивая сортировка оставит объекты с одинаковым ключом в том же порядке, в котором они были, а неустойчивая перемешает.

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

Пример реализации алгоритма на языке Go:

func SelectSort(ar []int) {

for i := 0; i < len(ar)-1; i++ {

min := i

for j := i + 1; j < len(ar); j++ {

if ar[min] > ar[j] {

min = j

}

}

if min != i {

swap(&ar, i, min)

}

}

}

func swap(array *[]int, i int, j int) {

var dArray = *array;

dArray[i], dArray[j] = dArray[j], dArray[i];

}

Пример сортировки массива

6. Сортировка вставкой

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

Данный алгоритм имеет среднюю и максимальную временные сложности O(n^2), алгоритм медленный и не эффективный. Поэтому в наше время он используется исключительно в обучающих целях. Дополнительной памяти не требуется, за исключением аллокации необходимых для итерации счетчиков. Однако, временная сложность лучшего случая будет O(n), в отличие от метода сортировки выбором.

Пример реализации алгоритма на языке Go:

func InsertionSort(ar []int) {

for i := 1; i < len(ar); i++ {

x := ar[i]

j := i

for ; j >= 1 && ar[j-1] > x; j-- {

ar[j] = ar[j-1]

}

ar[j] = x

}

}

Пример сортировки массива

7, Сортировка Шелла

Алгоритм предложен в 1959 г. Дональдом Л. Шеллом. Является усовершенствованным вариантом алгоритма сортировки вставками.

Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз.

Первое значение, соответствующее расстоянию d равно 10/2=5. На каждом шаге оно уменьшается вдвое. Элементы, входящие в одну группу, сравниваются и если значение какого-либо элемента, стоящего левее того с которым он сравнивается, оказывается больше (сортировка по возрастанию), тогда они меняются местами. Так, элементы путем внутригрупповых перестановок постепенно становятся на свои позиции, и на последнем шаге (d=1) сортировка сводится к проходу по одной группе, включающей в себя все N элементов массива. При этом число требуемых обменов оказывается совсем небольшим.

Данный алгоритм имеет максимальную временные сложности O(n^2), однако среднее время зависит от выбранных шагов и обычно значительно меньше.

Пример реализации алгоритма на языке Go:

func ShellSort(ar []int) {

for gap := len(ar) / 2; gap > 0; gap /= 2 {

for i := gap; i < len(ar); i++ {

x := ar[i]

j := i

for ; j >= gap && ar[j-gap] > x; j -= gap {

ar[j] = ar[j-gap]

}

ar[j] = x

}

}

}

Пример сортировки массива

8. Быстрая сортировка

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

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

Данный алгоритм имеет максимальную временные сложности O(n^2), однако среднее время - О(n log n). Поэтому алгоритм эффективне и в большинстве случаев именно он используется при вызове функция сортировки используемого языка программирования.

Пример реализации алгоритма на языке Go:

func Quicksort(ar []int) {

if len(ar) <= 1 {

return

}

split := partition(ar)

Quicksort(ar[:split])

Quicksort(ar[split:])

}

func partition(ar []int) int {

pivot := ar[len(ar)/2]

left := 0

right := len(ar) - 1

for {

for ; ar[left] < pivot; left++ {

}

for ; ar[right] > pivot; right-- {

}

if left >= right {