РусҚаз

Сортировки

Информатика · 9 класс · Алгоритмы обработки · Урок 2 из 4

Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Что это

Сортировка — это расстановка вещей по порядку: книги на полке по алфавиту, товары по цене, фотографии по дате. Ты сам сортируешь, когда выстраиваешь друзей по росту для общей фотографии. Компьютер делает то же самое, только с миллионами записей и строго по правилам.

Школьный физрук на спортивной площадке выстраивает ребят в шеренгу по росту, двое мальчишек меняются местами, остальные смеются.

Зачем это нужно

Почти каждый сервис вокруг тебя сортирует: поиск выдаёт самые подходящие страницы первыми, маркетплейс раскладывает товары по цене, лента в соцсети — по свежести и интересу. Базы данных держат записи упорядоченными, чтобы в них работал быстрый бинарный поиск, а дата-центры для ИИ каждую секунду сортируют огромные потоки данных. Сегодня код сортировки ИИ напишет за секунду, но решать, по какому признаку упорядочить, заметить, что результат перепутан, и выбрать способ, который не захлебнётся на миллиарде записей, — дело человека. Кто понимает, как устроена сортировка изнутри, тот умеет и ставить задачу, и проверять ответ машины.

Огромный светлый склад интернет-магазина, роботы-тележки развозят коробки по стеллажам, расставленным по номерам, инженер с планшетом следит за потоком.

Как это работает

Сортировка пузырьком идёт по списку и сравнивает соседей: если левый больше правого, они меняются местами. За один проход самый большой элемент, как пузырёк в воде, всплывает в самый конец. Сортировка выбором действует иначе: ищет самый маленький элемент среди ещё не разложенных и ставит его в начало. А беспорядок удобно мерить инверсиями — парами, где больший стоит левее меньшего: каждый обмен соседей, стоящих не по порядку, убирает ровно одну инверсию, поэтому пузырёк делает ровно столько обменов, сколько инверсий в массиве.

Ряд разноцветных стеклянных бутылок разной высоты на подоконнике, девочка переставляет две соседние бутылки, меняя их местами.

Немного истории

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

Конец девятнадцатого века, изобретатель в жилете и с усами стоит у деревянной машины с ящиками для перфокарт и опускает рычаг, рядом стопки картонных карточек.

Что будем делать на практике

А теперь давай попробуем выполнить практическое задание. Перед тобой список из восьми чисел — пять, два, семь, один, восемь, три, шесть, четыре — в виде столбиков, высота каждого равна его значению. Между соседними столбиками есть кнопки с двумя стрелками: нажимаешь — и соседи меняются местами. Твоя цель — выстроить столбики по возрастанию слева направо, причём без единого лишнего обмена: меняй только ту пару, где левый столбик выше правого. Сейчас в массиве тринадцать инверсий, и следи, как этот счётчик тает с каждым правильным обменом — значит, всего понадобится ровно тринадцать обменов. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай, у тебя всё получится.

Задание в опыте

Расставьте столбики по возрастанию слева направо, меняя местами только соседей. Ни одного лишнего обмена: каждый обмен должен исправлять беспорядок.
Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Уроки темы: Алгоритмы обработки

  1. Поиск: линейный и бинарный
  2. Сортировки
  3. Сложность алгоритма
  4. Рекурсия