Сортировка

Зачем вообще сортировать данные

Сортировка приводит элементы к заданному порядку: например, от меньшего к большему, по длине строки или по какому-то полю объекта. После этого данные становятся предсказуемее: соседние значения связаны порядком, одинаковые элементы группируются, а многие последующие алгоритмы становятся проще.

Но «отсортировать» можно по-разному. Одни алгоритмы просты и удобны для обучения, другие хорошо работают на больших массивах, третьи выигрывают только при специальных свойствах входных данных. Поэтому важно понимать не один конкретный способ, а несколько разных идей сортировки.

Что входит в раздел

• Основы сортировки. Разберём, что именно считается порядком, как задаётся критерий сравнения и какие свойства алгоритма важны кроме результата.
• Пузырьковая сортировка. Увидим простую идею обмена соседних элементов и постепенного «выталкивания» больших значений вправо.
• Сортировка выбором. Будем находить минимальный элемент оставшейся части и ставить его на правильную позицию.
• Сортировка вставками. Научимся поддерживать уже отсортированный префикс и вставлять в него следующий элемент.
• Сортировка слиянием. Разделим задачу на части, отсортируем их и аккуратно объединим результат.
• Быстрая сортировка. Познакомимся с разбиением массива относительно опорного элемента и рекурсивной обработкой частей.
• Сортировка подсчётом. Используем значения элементов как индексы счётчиков вместо сравнений между элементами.
• Стабильная сортировка. Разберём, почему взаимный порядок равных элементов иногда имеет значение.

В Java сортировка уже есть, но алгоритмы всё равно нужны

int[] values = {7, 2, 5, 1};
Arrays.sort(values);

System.out.println(Arrays.toString(values)); // [1, 2, 5, 7]

В прикладном коде обычно используют готовые библиотечные методы. В этом разделе мы реализуем основные алгоритмы сами, чтобы научиться видеть их механику, оценивать стоимость и выбирать подходящую идею под конкретную задачу.