Что вижу - о том пою (aragont) wrote,
Что вижу - о том пою
aragont

Categories:

Алгоритмы сортировки для чайников

Когда-то я придумывал, как объяснить "чайнику" программисткое понимание компьютера. Получилось примерно так - компьютер состоит из тупого, но очень быстрого и аккуратного, слуги (процессора) и умного советника (программиста), написавшего для слуги инструкции (программы) на все случаи жизни.

Вам хочется кофе? Достаньте инструкцию с надписью "кофе" и отдайте слуге. Слуга прочитает (и выполнит) сотни элементарных действий - "повернись на север, сделай 10 шагов, повернись на восток и сделай ещё 3 шага, протяни правую руку влево и возьми банку с кофе...". Если слуга достаточно быстр, для вас это будет выглядеть, как появление в его руке чашечки с кофе вместо бумажки с надписью "кофе".

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

Вот один из вариантов сортировки:
1. Взять две верхние карты из колоды.
2. Младшую положить в новую колоду, старшую оставить на руках.
3. Взять из старой колоды следующую карту.
4. Перейти к пункту 2.
5. Когда старая колода кончится, переложить новую на место старой и вернуться к пункту 1.

Удивительное дело, но через некоторое время все карты в колоде разлягутся по порядку.

Существуют и другие способы.

Недавно узнал про Bogosort или "обезьянью сортировку":
1. Проверить лежат ли все карты по порядку.
2. Если нет - подкинуть колоду в воздух, собрать карты с пола и перейти к пункту 1.

Вчера в интернете попалась шикарная постановка с исполнительными слугами и четырьмя алгоритмами сортировки колоды - http://www.youtube.com/user/AlgoRythmics

Один ролик процитирую прямо здесь
Tags: математика
Subscribe

  • Безбумажные технологии

    Пара историй про электронные технологии в университетах. В УрФУ (по крайней мере в моём институте) появилось поколение студентов без зачёток.…

  • Театр

    Будете в Екатеринбурге, загляните в кукольный театр на "Дон Кихота" и его Дульсинею тобольскую. От "Дон Кихота" там страшно худая седая лошадь,…

  • Палки для сэлфи

    Если кто не знает, то в середине (за 700 р) выкидная дубинка, которая в СССР однозначно считалась холодным оружием.

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments