Добавлен: 29.02.2024
Просмотров: 44
Скачиваний: 0
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/Алгоритм_сортировки