Сортировка пузырьком
Это один из простейших алгоритмов сортировки. Он не самый эффективный, но является фундаментальным шагом для погружения в мир алгоритмов.
Идея: проходим по сортируемому массиву, сравнивая соседние элементы и меняя их местами, если предыдущее оказывается больше последующего. Процесс повторяется до тех пор, пока все элементы не будут отсортированы.
Ключевые моменты:
- Пузырьковая сортировка проста для понимания, но неэффективна для больших списков.
- Его временная сложность в наихудшем случае равна
- Это хорошая отправная точка для понимания концепции сравнения и замены элементов для сортировки.
Это один из простейших алгоритмов сортировки. Он не самый эффективный, но является фундаментальным шагом для погружения в мир алгоритмов.
Идея: проходим по сортируемому массиву, сравнивая соседние элементы и меняя их местами, если предыдущее оказывается больше последующего. Процесс повторяется до тех пор, пока все элементы не будут отсортированы.
Ключевые моменты:
- Пузырьковая сортировка проста для понимания, но неэффективна для больших списков.
- Его временная сложность в наихудшем случае равна
O(n^2), что делает его менее практичным для реальных сценариев.- Это хорошая отправная точка для понимания концепции сравнения и замены элементов для сортировки.
Сортировка выбором
Это простой и интуитивно понятный алгоритм сортировки.
Он неоднократно находит самый маленький (или самый большой) элемент из неотсортированной части массива и заменяет его первым неотсортированным элементом.
Алгоритм:
1. Начинаем с того, что весь входной массив считается неотсортированным.
2. Перебираем неотсортированную часть массива, чтобы найти минимальный (или максимальный) элемент.
3. Как только минимальный (или максимальный) элемент определен, он заменяется первым элементом в несортированной части.
4. Продолжаем этот процесс, уменьшая размер неотсортированной части на один элемент на каждой итерации, пока весь массив не будет отсортирован.
Сложность алгоритма:
В лучшем случаи:
Это простой и интуитивно понятный алгоритм сортировки.
Он неоднократно находит самый маленький (или самый большой) элемент из неотсортированной части массива и заменяет его первым неотсортированным элементом.
Алгоритм:
1. Начинаем с того, что весь входной массив считается неотсортированным.
2. Перебираем неотсортированную часть массива, чтобы найти минимальный (или максимальный) элемент.
3. Как только минимальный (или максимальный) элемент определен, он заменяется первым элементом в несортированной части.
4. Продолжаем этот процесс, уменьшая размер неотсортированной части на один элемент на каждой итерации, пока весь массив не будет отсортирован.
Сложность алгоритма:
В лучшем случаи:
O(n^2)
В cреднем: O(n^2)
В худшем: O(n^2)Сортировка вставками
Это простой алгоритм сортировки, который неоднократно берет один элемент из неотсортированной части массива и вставляет его в правильную позицию в отсортированной части.
Алгоритм:
1. Начинаем с первого элемента, который считается отсортированным.
2. Перебираем неотсортированную часть массива, беря по одному элементу за раз и сравниваем его с элементами в отсортированной части массива.
3. Сдвигаем элементы в отсортированной части массива вправо, пока не найдем правильную позицию для текущего элемента.
4. Как только правильная позиция найдена, вставляем текущий элемент в отсортированную часть массива.
5. Продолжаем этот процесс, пока не будет отсортирован весь массив.
Сложность алгоритма:
В лучшем случаи:
Это простой алгоритм сортировки, который неоднократно берет один элемент из неотсортированной части массива и вставляет его в правильную позицию в отсортированной части.
Алгоритм:
1. Начинаем с первого элемента, который считается отсортированным.
2. Перебираем неотсортированную часть массива, беря по одному элементу за раз и сравниваем его с элементами в отсортированной части массива.
3. Сдвигаем элементы в отсортированной части массива вправо, пока не найдем правильную позицию для текущего элемента.
4. Как только правильная позиция найдена, вставляем текущий элемент в отсортированную часть массива.
5. Продолжаем этот процесс, пока не будет отсортирован весь массив.
Сложность алгоритма:
В лучшем случаи:
O(n)
В cреднем: O(n^2)
В худшем: O(n^2)