Посчитал репозиторий полезным? Поставь звезду
Данный репозиторий содержит мою реализацию структрур и алгоритмов обработки данных из соответствующего курса лекций МАИ, а так же мое вольное описание принципа работы Алгоритмов/структур, на достоверность не претендую.
Я буду рассматривать только алгоритмы поиска и сортировки, алгоритмы оптимизации оставлю на потом.
Глобально алгоритмы поиска элемента в массиве делятся на линейные и бинарные. Преимущество линейного поиска заклчается в том, что для его работы нет ограничения на входные данные: поиск может осуществляться как в отсортированом массиве, так и не отсортированном. Бинарный поиск работает быстрее (в худшем случае), но требует, чтобы исходный массив был отсортирован.
| Тип | Название | лучший случай | худший случай | память |
|---|---|---|---|---|
| Линейный | LinearSearch | |||
| Линейный | SentialSearch | |||
| Бинарный | BinarySearch |
Реализация тут
Классический линейный поиск. Принцип работы заключается в том, что в цикле поэлементно сравнивается текущее значение множества с искомым. Если мы перебрали весь исходный массив, а искомый элемент так и не нашелся, возвращается значение -1.
Реализация тут
Принцип работы похож на обычный линейный поиск, за тем исключением, что время одной итерации меньше за счёт отсутствия проверки выхода за границу массива.
Реализация тут
Идея заключается в том, что мы "сужаем" диапазон, в котором может находиться искомый элемент, учитывая то, что мы знаем, с какого индекса находятся элементы меньше искомого, а с какого - больше.
Алгоритм:
- Определяется значение элемента в середине массива. Полученное значение сравнивается с искомым элементом.
- Если искомый элемент меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
- Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с искомым элеменом.
- Процесс продолжается до тех пор, пока не будет найден элемент со значением искомого или не станет пустым интервал для поиска.
Алгоритмов сортировки существует множество, я рассмотрю только несколько наиболее популярных.
| Название | Средний случай | Худший случай | Память |
|---|---|---|---|
| Сортировка пузырьком | |||
| Сортировка вставками | |||
| Сортировка выбором | |||
| Сортировка слиянием | |||
| Быстрая сортировка | |||
| Параллельная сортировка слиянием |
Реализация тут
Простейшая для реализации и понимания сортирровка. Принцип работы заключается в выполнении нескольких проходов по массиву: начиная c 0 элемента, перебираются соседние пары. Если левый элемент пары больше правого, то они меняются местами (при сортировке по возрастанию).
Псевдокод:
function bubble_sort(array)
for i from 0 to length(array) - 1 do
for j from 0 to length(array) - 1 - i do
if array[j] > array[j + 1]
swap(array[j - 1], array[j])
end if
Реализация тут
Изначально массив разделяется на отсортированную часть и неотсортированную, затем берется первый элемент из неотсортированной части и вставляется в нужное место в отсортированной. Это действие продолжается до тех пор, пока в неостортированной части не закончатся элементы.
Псевдокод:
function insert_sort(array)
for i from 0 to length(array) - 1 do
insert(array, i, sorted + 1)
function insert(array, endOfSortedPartIndex, itemIndex)
// получение индекса вставки может быть реализовано разными способами, например - через бинарный поиск
insertToIndex = getInsertToIndex(endSortedPartIndex, array[itemIndex])
for i from itemIndex to insertToIndex step -1 do
swap(array[i], array[i - 1])
Реализация тут
Принцип очень прост: на каждой итерации берем текущий элемент и меняем его местами с минимальным элементам из множества, правее текущего элемента.
Псевдокод:
function selection_sort(array)
for i from 0 to length(array) - 1 do
min_index = I
for j from i + 1 to length(array) do
if array[j] < array[min_index]
min_index = j
end if
swap(array[i], array[min_index])
Реализация тут
Идея заключается в объединении отсортированных множеств, это делается очень легко: первый элемент первого множества сравнивается с первым элементом второго множества, меньший из них добавляется в буфферный массив, а указатель добавленного элемента сдвигается вперед. Эти действия повторяются до тех пор, пока не сольются оба множества или одно из них не закончится. В случае, если одно из множеств закончилось раньше, чем другое, то оставшиеся элементы из множества добавляем в конец буфферного массива.
Алгоритм работает по приципу "разделяй и властвуй": исходное множество делится на две части, каждая из которых так же делится на две части. Когда часть множества состоит всего из одного (или нуля) элемента и делить дальше уже некуда, мы получаем отсортированное множество (множество из одного элемента по умолчанию отсортированно, а пустое - тем более). Затем наступает этап слияния двух уже отсортированных подможеств в одно большей размерности.
Псевдокод:
function mergesort(m)
var list left, right, result
if length(m) ≤ 1
return m
else
middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = mergesort(left)
right = mergesort(right)
result = merge(left, right)
return result
end if
function merge(left,right)
var list result
while length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
end if
while length(left) > 0
append first(left) to result
left = rest(left)
while length(right) > 0
append first(right) to result
right = rest(right)
return result
Реализация тут
Общая идея алгоритма состоит в следующем:
- Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность. Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: элементы "меньшие" опорного, "равные" и "большие".
- Для отрезков "меньших" и "больших" значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы. На практике массив обычно делят не на три, а на две части: например, "меньшие опорного" и "равные и большие"; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения. В своей реализации я поступил именно так.
Псевдокод:
function quick_sort(array, left, right)
if left >= right
return
end if
var i, j, = left, right
var pivot = array[left]
while i <= j do
while array[i] < pivot do
i++
end while
while array[j] > pivot do
j--
end while
if i <= j
swap(array[i], array[j])
i++
j--
end if
end while
quick_sort(array, left, j)
quick_sort(array, i, right)
Реализация тут
Одно из преимуществ сортировки слиянием залкючается в том, что ее очень просто распараллелить: достаточно рекурсивные вызовы делать в новых потоках, а затем дожидаться выполнения этих вызовов и производить слияние в вызывающем потоке.
В процессе оформления
в процессе оформления
в процессе оформления
в процессе оформления
в процессе реализации
в процессе реализации