Сегодня мы расскажем простым языком о Bubble Sort, Insertion Sort и Selection Sort. Покажем, какие идеи лежат в основе этих сортировок и продемонстрируем их сильные и слабые стороны. Разберём алгоритмы по шагам, рассмотрим их простые версии и даже немного улучшим. Дальнейший рассказ подразумевает, что вас не смущают такие фразы, как «сложность worst-case-алгоритма по времени равна O(n^2)». Иногда Time Complexity мы будем называть «сложностью по времени», а Space Complexity — «сложностью по памяти»...

Когда мы начинаем изучать алгоритмы сортировки, одним из первых, с которым мы сталкиваемся, является сортировка пузырьком (Bubble Sort). Этот алгоритм получил свое название благодаря принципу «всплывания» наибольшего элемента в конец массива, подобно пузырьку, поднимающемуся на поверхность воды. Простота этого алгоритма делает его хорошим кандидатом для начала знакомства с базовыми принципами алгоритмических операций. Сортировка пузырьком — это простой алгоритм сортировки, который последовательно сравнивает и меняет местами соседние элементы массива, если они расположены в неправильном порядке...