Что это
Сортировка — это расстановка вещей по порядку: книги на полке по алфавиту, товары по цене, фотографии по дате. Ты сам сортируешь, когда выстраиваешь друзей по росту для общей фотографии. Компьютер делает то же самое, только с миллионами записей и строго по правилам.
Зачем это нужно
Почти каждый сервис вокруг тебя сортирует: поиск выдаёт самые подходящие страницы первыми, маркетплейс раскладывает товары по цене, лента в соцсети — по свежести и интересу. Базы данных держат записи упорядоченными, чтобы в них работал быстрый бинарный поиск, а дата-центры для ИИ каждую секунду сортируют огромные потоки данных. Сегодня код сортировки ИИ напишет за секунду, но решать, по какому признаку упорядочить, заметить, что результат перепутан, и выбрать способ, который не захлебнётся на миллиарде записей, — дело человека. Кто понимает, как устроена сортировка изнутри, тот умеет и ставить задачу, и проверять ответ машины.
Как это работает
Сортировка пузырьком идёт по списку и сравнивает соседей: если левый больше правого, они меняются местами. За один проход самый большой элемент, как пузырёк в воде, всплывает в самый конец. Сортировка выбором действует иначе: ищет самый маленький элемент среди ещё не разложенных и ставит его в начало. А беспорядок удобно мерить инверсиями — парами, где больший стоит левее меньшего: каждый обмен соседей, стоящих не по порядку, убирает ровно одну инверсию, поэтому пузырёк делает ровно столько обменов, сколько инверсий в массиве.
Немного истории
Машины начали сортировать данные задолго до появления компьютеров. Изобретатель Герман Холлерит придумал перфокарты и электрические машины, которые считали и раскладывали их по ящикам, — с их помощью обработали перепись населения в Соединённых Штатах в 1890 году намного быстрее, чем вручную. Фирма Холлерита позже стала частью компании, которую мы знаем как Ай-би-эм.
Что будем делать на практике
А теперь давай попробуем выполнить практическое задание. Перед тобой список из восьми чисел — пять, два, семь, один, восемь, три, шесть, четыре — в виде столбиков, высота каждого равна его значению. Между соседними столбиками есть кнопки с двумя стрелками: нажимаешь — и соседи меняются местами. Твоя цель — выстроить столбики по возрастанию слева направо, причём без единого лишнего обмена: меняй только ту пару, где левый столбик выше правого. Сейчас в массиве тринадцать инверсий, и следи, как этот счётчик тает с каждым правильным обменом — значит, всего понадобится ровно тринадцать обменов. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай, у тебя всё получится.