Что вижу - о том пою (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

  • 9.1.1

    Пару дней назад было двадцатилетие террористической атаки на башни близнецы. Как сейчас помню тот вечер. Мы вернулись из гостей слегка выпивши и я…

  • Тетрадь за 28 копеек

    В передаче на телеканале "Ностальгия" Надежда Чепрага произнесла примерно такую фразу: "Новых песен у нас на селе все ждали. Если появлялась новая…

  • Тайные архивы КСП

    Когда говорят о политической оппозиции перед распадом СССР, то вспоминают диссидентов разного толка (я не был с ними знаком) и рокеров, которых в…

  • 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