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

Предыдущая часть Ранее рассмотренные методы давали нам оценку сложности не лучше чем O(N²), так что, конечно, возникает вопрос – а можно ли её вообще улучшить? Да, но только это всегда будет приводить к некоторым ограничениям. Сортировка подсчётом Весьма оригинальный и супер-простой метод сортировки. Если на входе нам дан массив целых чисел, где каждое число находится в диапазоне от 0 до R, то после сортировки мы должны получить ряд возрастающих чисел: 0, 1, 2, 3, 4, 5, 6, ... R Но не все числа могут в нём присутствовать, а некоторые числа могут повторяться несколько раз...