Сортировка пузырьком (Bubble Sort): Простой, но неэффективный алгоритм, который многократно проходит по списку, сравнивая и меняя соседние элементы. Временная сложность: O(n^2) в худшем и среднем случае, O(n) в лучшем случае (если массив уже отсортирован). Примечание: Это один из самых неэффективных алгоритмов сортировки для больших массивов.
Сортировка выбором (Selection Sort): Находит наименьший элемент и перемещает его в начало списка, повторяя процесс для оставшейся части. Временная сложность: O(n^2) в худшем, среднем и лучшем случаях. Примечание: Этот алгоритм также неэффективен для больших массивов и не использует дополнительную память.
Сортировка вставками (Insertion Sort): Постепенно строит отсортированный массив, вставляя элементы на свои места. Временная сложность: O(n^2) в худшем и среднем случае, O(n) в лучшем случае (если массив уже отсортирован). Примечание: Хорошо работает для небольших массивов и частично отсортированных данных.
Сортировка слиянием (Merge Sort): Разделяет массив на подмассивы, сортирует их и затем объединяет. Временная сложность: O(n log n) в худшем, среднем и лучшем случаях. Примечание: Это стабильный алгоритм сортировки, который требует дополнительной памяти для хранения временных массивов.
Быстрая сортировка (Quick Sort): Разделяет массив на две части по опорному элементу и рекурсивно сортирует каждую часть. Временная сложность: O(n log n) в среднем и лучшем случаях, O(n^2) в худшем случае (например, если массив уже отсортирован и выбирается плохой опорный элемент). Примечание: Это один из самых быстрых алгоритмов сортировки для больших массивов, но он не является стабильным.
Самые эффективные: Merge Sort и Quick Sort (в большинстве случаев). Наименее эффективные: Bubble Sort, Selection Sort и Insertion Sort (в основном для больших массивов).
Линейный поиск (Linear search): Проверяет каждый элемент массива по очереди, пока не найдет нужный. Сложность: Лучший случай: O(1) — элемент найден на первой позиции. Средний и худший случай: O(n) — когда элемент находится в конце массива или отсутствует. Примечание: Линейный поиск прост в реализации и может быть полезен для небольших массивов или когда данные не отсортированы. Однако для больших отсортированных массивов лучше использовать более эффективные алгоритмы, такие как бинарный поиск.
Бинарный поиск (Binary search): Работает на отсортированных массивах, деля массив пополам и сравнивая средний элемент с искомым значением. Сложность: Лучший случай: O(1) — элемент найден на первой проверке. Средний и худший случай: O(log n) — количество элементов уменьшается вдвое на каждой итерации. Примечание: Бинарный поиск эффективен для больших отсортированных массивов и является одним из самых быстрых способов поиска элемента в таком массиве.
Алгоритм Дейкстры: Находит кратчайший путь от одной вершины графа к всем остальным. Временная сложность: O((V + E) log V), где V — количество вершин, E — количество ребер. Это связано с тем, что каждая вершина и каждое ребро обрабатываются, а операции с приоритетной очередью занимают логарифмическое время. Пространственная сложность: O(V), так как мы храним расстояния и граф в памяти.
Алгоритм Флойда-Уоршелла: Находит кратчайшие пути между всеми парами вершин. Временная сложность: O(V^3), где V — количество вершин. Это связано с тремя вложенными циклами, каждый из которых проходит по всем вершинам. Пространственная сложность: O(V^2), так как мы храним матрицу расстояний в памяти.
Поиск в глубину (DFS): Рекурсивный алгоритм, который исследует как можно глубже по графу, прежде чем вернуться. Временная сложность: O(V + E), где V — количество вершин, E — количество ребер. Каждый узел и каждое ребро обрабатываются один раз. Пространственная сложность: O(V) для хранения множества посещенных вершин и стека (в случае рекурсивного подхода, глубина рекурсии может достигать O(V)).
Поиск в ширину (BFS): Исследует все соседние вершины перед переходом к следующему уровню. Временная сложность: O(V + E), где V — количество вершин, E — количество ребер. Каждый узел и каждое ребро обрабатываются один раз. Пространственная сложность: O(V) для хранения множества посещенных вершин и очереди.
Бинарное дерево поиска (БДП или BST) Быстрый поиск: В среднем, операции поиска, вставки и удаления имеют временную сложность O(log n), что делает БДП эффективным для работы с отсортированными данными. Недостатки: Плохая производительность в худшем случае: В худшем случае (например, когда дерево становится несбалансированным, как в случае вставки отсортированных данных) временная сложность операций может ухудшиться до O(n). Это происходит, когда дерево принимает форму линейного списка. Необходимость балансировки: Для поддержания эффективной производительности требуется балансировка дерева, что может усложнить реализацию. Существуют самобалансирующиеся деревья, такие как AVL-деревья и красно-черные деревья, которые решают эту проблему, но они добавляют дополнительную сложность
AVL-дерево Самобалансирующееся бинарное дерево поиска, в котором для каждого узла разность высот левого и правого поддеревьев (баланс) не превышает 1. Преимущества: Быстрые операции: AVL-деревья обеспечивают операции поиска, вставки и удаления с временной сложностью O(log n) в худшем случае, что делает их эффективными для работы с большими объемами данных. Самобалансировка: AVL-деревья автоматически поддерживают балансировку после каждой операции вставки или удаления, что предотвращает ухудшение производительности, связанное с несбалансированными деревьями. Высокая степень сбалансированности: AVL-деревья имеют более строгие критерии балансировки по сравнению с другими самобалансирующимися деревьями (например, красно-черными деревьями), что позволяет им оставаться более сбалансированными и, как следствие, обеспечивает более быстрые операции поиска. Предсказуемая производительность: Поскольку AVL-деревья всегда сбалансированы, производительность операций предсказуема и не зависит от порядка вставки данных. Эффективные обходы: AVL-деревья поддерживают различные способы обхода (симметричный, прямой, обратный и уровень), что позволяет извлекать данные в нужном порядке. Недостатки: Затраты на время при вставке и удалении: Хотя операции поиска выполняются быстро, операции вставки и удаления могут быть медленнее, чем в обычных бинарных деревьях поиска, из-за необходимости поддержания балансировки. В худшем случае, время выполнения может достигать O(log n) из-за дополнительных поворотов. Необходимость частых поворотов: При частых операциях вставки и удаления, AVL-дерево может потребовать много поворотов для поддержания балансировки, что может увеличить время выполнения операций. Ограниченная гибкость: AVL-деревья имеют строгие правила балансировки, что может ограничить их использование в некоторых сценариях, где требуется более гибкая структура данных.
Красно-черное дерево Преимущества: Быстрые операции: Все основные операции (поиск, вставка, удаление) имеют временную сложность O(log n), что делает красно-черные деревья эффективными для работы с большими наборами данных. Простота вставки и удаления: Вставка и удаление в красно-черных деревьях могут быть выполнены с относительно простыми алгоритмами, что делает их более удобными для реализации по сравнению с другими сбалансированными деревьями, такими как AVL-деревья. Поддержка динамических данных: Красно-черные деревья хорошо подходят для сценариев, где данные часто изменяются (вставляются и удаляются), благодаря их способности поддерживать баланс. Недостатки: Меньшая строгость балансировки по сравнению с AVL-деревьями: Красно-черные деревья менее сбалансированы, чем AVL-деревья, что может привести к более длинным путям в некоторых случаях, что в свою очередь может замедлить операции поиска. Необходимость частых поворотов: При частых операциях вставки и удаления может потребоваться множество поворотов для поддержания свойств дерева, что может увеличить время выполнения операций. Сложность анализа производительности: Из-за особенностей алгоритма балансировки может быть сложнее предсказать производительность для определенных наборов данных по сравнению с другими структурами данных.
package main
import (
"fmt"
"log"
"math"
AlgorithmsGraphs "github.com/Reactivity512/Golang-algorithms/algorithm/graphs"
AlgorithmsSearch "github.com/Reactivity512/Golang-algorithms/algorithm/search"
AlgorithmsSorting "github.com/Reactivity512/Golang-algorithms/algorithm/sorting"
AlgorithmsTree "github.com/Reactivity512/Golang-algorithms/algorithm/tree"
)
func Examples() {
// example sorting
var arrForSort = []int{38, 27, 43, 3, 9, 82, 10}
fmt.Println("QuickSort Исходный массив:", arrForSort)
var sortedArr = AlgorithmsSorting.QuickSort(arrForSort)
fmt.Println("QuickSort Отсортированный массив:", sortedArr)
// example search
var arrForSearch = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
var targetForSearch = 7
var indexSearchElement = AlgorithmsSearch.BinarySearch(arrForSearch, targetForSearch)
if indexSearchElement != -1 {
fmt.Printf("Результат BinarySearch Элемент %d найден на индексе %d\n", targetForSearch, indexSearchElement)
} else {
fmt.Printf("Результат BinarySearch Элемент %d не найден\n", targetForSearch)
}
// example dijkstra
var graphDijkstra = &AlgorithmsGraphs.GraphDijkstra{
Vertices: 5,
Edges: map[int][]AlgorithmsGraphs.EdgeDijkstra{
0: {{To: 1, Weight: 10}, {To: 2, Weight: 3}},
1: {{To: 2, Weight: 1}, {To: 3, Weight: 2}},
2: {{To: 1, Weight: 4}, {To: 3, Weight: 8}, {To: 4, Weight: 2}},
3: {{To: 4, Weight: 7}},
4: {},
},
}
var startVertexForDijkstra = 0
distancesGraphDijkstra, err := graphDijkstra.Dijkstra(startVertexForDijkstra)
if err != nil {
log.Fatalln(err)
}
fmt.Printf("Dijkstra ")
for i, distance := range distancesGraphDijkstra {
if distance == math.MaxInt32 {
fmt.Printf("Вершина %d: недоступна, ", i)
} else {
fmt.Printf("Вершина %d: %d, ", i, distance)
}
}
fmt.Println()
// example floydWarshall
var graphFloydWarshall = AlgorithmsGraphs.GraphFloydWarshall{
Graph: [][]int{
{0, 3, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0},
{0, 0, 0, 7, 0, 2},
{0, 0, 0, 0, 2, 0},
{6, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0},
},
}
var graphFloydWarshallDistances = AlgorithmsGraphs.FloydWarshall(graphFloydWarshall)
fmt.Println("FloydWarshall Матрица кратчайших расстояний:")
for i := 0; i < len(graphFloydWarshallDistances); i++ {
for j := 0; j < len(graphFloydWarshallDistances[i]); j++ {
if graphFloydWarshallDistances[i][j] == math.MaxInt32 {
fmt.Print("Infinity ")
} else {
fmt.Print(graphFloydWarshallDistances[i][j], " ")
}
}
fmt.Println()
}
fmt.Println("End FloydWarshall")
// example depth first search
graphDFS := AlgorithmsGraphs.NewGraphDFS()
graphDFS.AddEdge(0, 1)
graphDFS.AddEdge(0, 2)
graphDFS.AddEdge(1, 3)
graphDFS.AddEdge(1, 4)
graphDFS.AddEdge(2, 5)
graphDFS.AddEdge(2, 6)
// Recursive DFS
visitedGraphDFS := make(map[int]bool)
var resultGraphDFSRecursive []int
graphDFS.DFSRecursive(0, visitedGraphDFS, &resultGraphDFSRecursive)
fmt.Println("Результат DFSRecursive:", resultGraphDFSRecursive)
// Iterative DFS
resultGraphDFSIterative := graphDFS.DFSIterative(0)
fmt.Println("Результат DFSIterative:", resultGraphDFSIterative)
// example breadth_first_search
graph := AlgorithmsGraphs.NewGraphBFS()
graph.AddEdge(0, 1)
graph.AddEdge(0, 2)
graph.AddEdge(1, 3)
graph.AddEdge(1, 4)
graph.AddEdge(2, 5)
graph.AddEdge(2, 6)
resultGraphBFS := graph.BFS(0)
fmt.Println("Результат BFS:", resultGraphBFS)
// example binary_tree
bst := &AlgorithmsTree.BST{}
bst.Insert(10)
bst.Insert(5)
bst.Insert(15)
bst.Insert(3)
bst.Insert(7)
bst.Insert(12)
bst.Insert(18)
fmt.Println("binary_tree Поиск 7:", bst.Search(7))
fmt.Println("binary_tree Поиск 20:", bst.Search(20))
fmt.Println("binary_tree Симметричный обход:", bst.InOrderTraversal())
// example AVL tree
treeAVL := &AlgorithmsTree.AVLTree{}
valuesAVL := []int{30, 20, 40, 10, 25, 35, 50}
for _, v := range valuesAVL {
treeAVL.Insert(v)
}
fmt.Println("AVLTree Симметричный обход InOrder:", treeAVL.InOrderTraversal())
fmt.Println("AVLTree Поиск 25:", treeAVL.Search(25))
fmt.Println("AVLTree Поиск 100:", treeAVL.Search(100))
// example red black tree
treeRBT := &AlgorithmsTree.RedBlackTree{}
treeRBT.Insert(10)
treeRBT.Insert(20)
treeRBT.Insert(30)
treeRBT.Insert(15)
treeRBT.Insert(25)
treeRBT.Insert(5)
// Обход дерева in-order
resultRBT := treeRBT.InOrderTraversal()
fmt.Println("RedBlackTree In-order traversal:", resultRBT)
// Поиск элемента
fmt.Println("RedBlackTree Поиск 15:", treeRBT.Search(15))
fmt.Println("RedBlackTree Поиск 40:", treeRBT.Search(40))
}