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

Содержание:

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];

}

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

Начальное состояние	5 1 4 2 8
Первая итерация
	1 5 4 2 8
	1 4 5 2 8
	1 4 2 5 8
	1 4 2 5 8
Вторая итерация
	1 4 2 5 8
	1 2 4 5 8
	1 2 4 5 8
	1 2 4 5 8
Третй проход	Проходим и убеждаемся что массив отсортирован

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

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

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

Начальное состояние	5 1 4 2 8
Первая итерация
	1 5 4 2 8
	1 4 5 2 8
	1 4 2 5 8
	1 4 2 5 8
	1 4 2 5 8
	1 4 2 5 8
	1 2 4 5 8
	1 2 4 5 8
Третй проход	Проходим и убеждаемся что массив отсортирован

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];

}

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

Начальное состояние	7 | 3 6 1 4 2 9
	1 3 | 6 7 4 2 9
	1 2 6 | 7 4 3 9
	1 2 3 7 | 4 6 9
	1 2 3 4 7 | 6 9
	1 2 3 4 6 7 | 9

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 3 6 1 4 2 9
	3 7 | 6 1 4 2 9
	3 6 7 | 1 4 2 9
	1 3 6 7 | 4 2 9
	1 3 4 6 7 | 2 9
	1 2 3 4 6 7 9

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

}

}

}

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

Начальное состояние	5 3 8 0 7 4 9 1 6 2
d = 5	4 3 1 0 2 5 9 8 6 7
d = 2	1 0 2 3 4 5 6 7 9 8
d = 1	0 1 2 3 4 5 6 7 8 9

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 {

return right

}

swap(ar, left, right)

}

}

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

var dArray = *array;

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

}

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

Начальное состояние	5 3 8 0 7 4 9 1 6 2
	4 3 1 0 2 5 9 8 6 7
	1 0 2 3 4 5 6 7 9 8
	0 1 2 3 4 5 6 7 8 9

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

Двоичным (бинарным) деревом называют структуру данных, где каждому элементу поставлены в соответствие до трех других элементов: левый и правый “потомки” и “родитель”. Левый потомок должен быть меньше, а правый – больше или равен родителю. Единственный элемент, не имеющий родителя, называется корнем дерева.

Делим массив на две части - не отсортированная и отсортированная. На не отсортированной части строим бинарное дерево. Строим по правилу, что потомки не больше предка, корень располагаем по индексу 0, а индексы листьев вычисляем по формуле 2i+1, 2i+2. В итоге, в корне оказывается наибольшее значение. Дальше мы меняем местами значения в начале и в конце неупорядоченной зоны. Получается, что отсортированная часть выросла на 1 элемент, неотсортированная уменьшилась на 1. Опять перестраиваем дерево, и повторяем все шаги пока полностью не отсортируем.

Сложность алгоритма в лучшем и худшем случае одинакова, О(n log n), те данная скорость является гарантированной. Данный алгоритм активно применяется в ядре операционной системы Linux.

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

func HeapSort(ar []int) {

if len(ar) < 2 {

return

}

heapIt(ar)

ar[0], ar[len(ar)-1] = ar[len(ar)-1], ar[0]

HeapSort(ar[:len(ar)-1])

}

func heapIt(ar []int) {

if len(ar) < 2 {

return

}

if len(ar) == 2 {

if ar[0] < ar[1] {

ar[0], ar[1] = ar[1], ar[0]

}

return

}

if len(ar) > 3 {

heapIt(ar[1:])

heapIt(ar[2:])

}

if ar[1] > ar[2] {

if ar[0] < ar[1] {

ar[0], ar[1] = ar[1], ar[0]

}

} else {

if ar[0] < ar[2] {

ar[0], ar[2] = ar[2], ar[0]

}

}

}

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

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

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

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

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

func mergeSort(items []int) []int {

var num = len(items)

if num == 1 {

return items

}

middle := int(num / 2)

var (

left = make([]int, middle)

right = make([]int, num-middle)

)

for i := 0; i < num; i++ {

if i < middle {

left[i] = items[i]

} else {

right[i-middle] = items[i]

}

}

return merge(mergeSort(left), mergeSort(right))

}

func merge(left, right []int) (result []int) {

result = make([]int, len(left) + len(right))

i := 0

for len(left) > 0 && len(right) > 0 {

if left[0] < right[0] {

result[i] = left[0]

left = left[1:]

} else {

result[i] = right[0]

right = right[1:]

}

i++

}

for j := 0; j < len(left); j++ {

result[i] = left[j]

i++

}

for j := 0; j < len(right); j++ {

result[i] = right[j]

i++

}

return

}

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

Начальное состояние	37824615
	3 | 7 | 8 | 2 | 4 | 6 | 1 | 5
	37 | 28 | 46 | 15
	2378 | 1456
	12345678

11. Заключение

Сортировка применяется во всех без исключения областях программирования, математические программы, игры, офисные приложения и так далее. Алгоритмы сортировки представляют собой пошаговое упорядочение элементов в определенном массиве данных, вне зависимости от размером массива. Практически каждый алгоритм сортировки можно разбить на три части: сравнение, определяющее порядок пары элементов; перестановку, меняющую пару элементов местами; сортирующий алгоритм, осуществляющий сравнение и перестановку элементов, пока все элементы не будут в правильном порядке. Выбор метода сортировки в значительной мере зависит от объема и характеристики исходных данных. Но, в целом, основными параметрами, которыми руководствуется пользователь при выборе метода сортировки, являются время действия алгоритма, память, устойчивость сортировки и эффективность поведения алгоритма.

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

В качестве практической части - были реализованы описанные в данной работе алгоритмы с использованием современного языка программирования общего назначения - Go.

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

1. Effective Go - https://golang.org/doc/effective_go.html

2. Ткачук В. А. Алгоритмы сортировки

3. Бинарные деревья - https://habr.com/ru/post/267855/

4. Описание алгоритмов сортировки и их сравнения - https://habr.com/ru/post/335920/

5. Алгоритмы сортировки - http://algolist.ru/sort/

6. Алгоритмы сортировки в Go - https://github.com/TheAlgorithms/Go]

7. Алгоритмы сортировки - https://ru.wikipedia.org/wiki/Алгоритм_сортировки