Всем привет!🤩

Сегодня в рубрике «Алгоритмы и легенды» расскажем вам, как один из самых известных алгоритмов в программировании придумали в Москве. ⭐️

🤩 Начнём с истории. В 1959 году англичанин Тони Хоар приехал учиться в МГУ по обмену. Русский он выучил ещё на службе во флоте, а в Москве занимался машинным переводом: делал программу, которая переводила бы с русского на английский.

Проблема была в том, что словарь хранился на магнитной ленте в алфавитном порядке. Чтобы не перематывать ленту туда-сюда ради каждого слова, слова из предложения нужно было сначала отсортировать. Тогда все переводы можно найти за один проход ленты.

Первым делом Хоар попробовал сортировку вставками, но она оказалась слишком медленной. Тогда он придумал свой способ:
выбрать один элемент, раскидать остальные на «меньше» и «больше» и повторить то же самое для каждой части. 🤩

Так появилась быстрая сортировка, она же quicksort. В 1960 году Хоар уже в Англии впервые применил её на практике, а сегодня она есть почти в каждом языке программирования.

Выходит, что алгоритм, которым пользуется весь мир, появился из попытки научить компьютер понимать русский язык. ❤️

#алгоритмыИлегенды