---
title: Алгоритмы · часть 1
seo:
title: Алгоритмы · часть 1 — C++ Developer
description: Тема «Алгоритмы · часть 1» для собеседования C++ Developer. Что такое алгоритмы сортировки и какие вы знаете? Какие алгоритмы работы со строками знаете?
---
[Все темы C++ Developer](/c-developer)
## Что такое алгоритмы сортировки и какие вы знаете? [#q-14bee738d69b810aba1adf780085bf88]
Алгоритмы сортировки — это методы организации коллекций данных в упорядоченном порядке, обычно по возрастанию или убыванию. Они являются фундаментальными инструментами в информатике, применяемыми для обработки и управления данными. Вот несколько основных типов алгоритмов сортировки:
1. Сортировка пузырьком (Bubble Sort):
Простейший алгоритм, который повторно проходит через список, сравнивает
соседние элементы и меняет их местами, если они находятся в неправильном
порядке.
1. Сортировка вставками (Insertion Sort)
: Строит итоговый отсортированный массив (или список) одним элементом за
раз, вставляя каждый новый элемент в уже отсортированную часть массива.
1. Сортировка выбором (Selection Sort)
: Находит минимальный элемент из неотсортированной части массива и
помещает его в конец отсортированной части.
1. Быстрая сортировка (Quick Sort):
Выбирает опорный элемент, и перегруппирует элементы вокруг него, так что
элементы меньше опорного оказываются перед ним, а большие — после. Процесс
повторяется рекурсивно для подмассивов до и после опорного элемента.
1. Сортировка слиянием (Merge Sort):
Разделяет массив на две части, рекурсивно сортирует их, а затем сливает в
один отсортированный массив.
1. Кучная сортировка (Heap Sort):
Преобразует массив в двоичную кучу, затем извлекает элементы из кучи один за
другим, восстанавливая свойства кучи после каждого извлечения.
1. Сортировка Шелла (Shell Sort):
Улучшенная версия сортировки вставками, использует последовательность шагов
(интервалов), сокращая количество перемещений элементов на большие
расстояния.
1. Поразрядная сортировка (Radix Sort)
: Сортирует числа путем обработки отдельных цифр. Функционирует от
младших разрядов к старшим или наоборот.
:::note[Ссылки для изучения]
1. [7 способов сортировки массива на С++](https://proglib.io/p/7-sposobov-sortirovki-massivov-na-primere-s-s-illyustraciyami-2022-04-20)
:::
---
## Какие алгоритмы работы со строками знаете? [#q-14bee738d69b81369498d0b3916abdd9]
Алгоритмы работы со строками — это методы обработки и анализа текстовых данных. Вот несколько основных алгоритмов, применяемых в обработке строк:
{/* prettier-ignore */}
1. Поиск подстроки:
- Алгоритм Кнута-Морриса-Пратта (KMP): Эффективно ищет вхождения подстроки в строке, используя префиксную функцию для минимизации количества обратных шагов.
- Алгоритм Бойера-Мура: Использует суффиксные правила и информацию о встреченных символах для ускорения поиска подстроки.
- Алгоритм Рабина-Карпа: Использует хэш-функцию для быстрого сравнения подстрок, что позволяет эффективно искать множество шаблонов одновременно.
1. Сортировка строк:
- Поразрядная сортировка (Radix Sort): Особенно эффективна для сортировки строк, так как обрабатывает символы строк начиная с младших разрядов.
- Сортировка слиянием: Хорошо подходит для сортировки больших массивов строк из-за своей стабильности и эффективности на больших данных.
1. Динамическое программирование в строках:
- Расстояние Левенштейна (редакционное расстояние): Вычисляет минимальное количество операций вставки, удаления и замены, необходимых для преобразования одной строки в другую.
- Нахождение наибольшей общей подпоследовательности (LCS): Определяет длину наибольшей последовательности символов, которая появляется в обеих строках в том же порядке.
1. Палиндромы:
- Алгоритмы для определения наибольшей палиндромической подстроки: Используют различные методы, включая динамическое программирование и расширение вокруг центра, для нахождения самых длинных палиндромов в строке.
1. Парсинг и лексический анализ:
- Регулярные выражения: Предоставляют мощные средства для поиска и извлечения данных из строк с помощью заданных паттернов.
:::note[Ссылки для изучения]
1. [Основные алгоритмы для работы со строками в C++](https://proglib.io/p/must-have-algoritmy-dlya-raboty-so-strokami-na-c-2020-03-30)
:::
---
## Какие алгоритмы на графах знаете? [#q-14bee738d69b81228769e99c68e7b458]
Алгоритмы на графах — это методы, используемые для анализа и решения задач в структурах данных, представляющих графы. Вот несколько ключевых алгоритмов, используемых для различных операций на графах:
{/* prettier-ignore */}
1. Поиск в глубину (DFS, Depth-First Search):
- Обходит граф, углубляясь как можно дальше, прежде чем отступать.
1. Поиск в ширину (BFS, Breadth-First Search):
- Обходит граф по слоям, начиная с исходной вершины и распространяясь равномерно во все стороны.
1. Поиск кратчайшего пути:
- Алгоритм Дейкстры: Находит кратчайшие пути от одной вершины до всех других в графе с неотрицательными весами рёбер.
- Алгоритм Беллмана-Форда: Решает ту же задачу, что и Дейкстра, но работает и с отрицательными весами рёбер.
- Алгоритм Флойда-Уоршелла: Находит кратчайшие пути между всеми парами вершин в графе.
1. Минимальное остовное дерево (Minimum Spanning Tree, MST):
- Алгоритм Прима: Построение MST, начиная с выбранной вершины и добавляя к ней ближайшие вершины с минимальными весами рёбер.
- Алгоритм Краскала: Построение MST, выбирая рёбра с наименьшим весом, которые не образуют циклов.
1. Топологическая сортировка:
- Упорядочивает вершины так, чтобы для каждого направленного ребра из вершины U в вершину V, U шло перед V.
1. Сильно связные компоненты:
- Алгоритм Косарайю: Находит сильно связные компоненты в направленном графе.
- Алгоритм Тарьяна: Эффективный способ нахождения сильно связных компонент с использованием одного DFS обхода.
1. Сети и потоки:
- Алгоритм Форда-Фалкерсона: Расчёт максимального потока из источника в сток в сети.
- Алгоритм Эдмондса-Карпа: Реализация Форда-Фалкерсона с использованием BFS для нахождения увеличивающих путей.
:::note[Ссылки для изучения]
1. [Базовые алгоритмы на графах на C++](https://habr.com/ru/companies/timeweb/articles/751762/)
:::