Алгоритмы сортировки для чайников
Когда-то я придумывал, как объяснить "чайнику" программисткое понимание компьютера. Получилось примерно так - компьютер состоит из тупого, но очень быстрого и аккуратного, слуги (процессора) и умного советника (программиста), написавшего для слуги инструкции (программы) на все случаи жизни.
Вам хочется кофе? Достаньте инструкцию с надписью "кофе" и отдайте слуге. Слуга прочитает (и выполнит) сотни элементарных действий - "повернись на север, сделай 10 шагов, повернись на восток и сделай ещё 3 шага, протяни правую руку влево и возьми банку с кофе...". Если слуга достаточно быстр, для вас это будет выглядеть, как появление в его руке чашечки с кофе вместо бумажки с надписью "кофе".
Программировать варку кофе довольно сложно, поэтому программисты тренируются на упорядочивании карт в колоде по старшинству (обычно раскладывают одну масть, но это не важно). Чтобы тупой слуга не запутался, придерживаются правила - из колоды брать не более двух карт за раз.
Вот один из вариантов сортировки:
1. Взять две верхние карты из колоды.
2. Младшую положить в новую колоду, старшую оставить на руках.
3. Взять из старой колоды следующую карту.
4. Перейти к пункту 2.
5. Когда старая колода кончится, переложить новую на место старой и вернуться к пункту 1.
Удивительное дело, но через некоторое время все карты в колоде разлягутся по порядку.
Существуют и другие способы.
Недавно узнал про Bogosort или "обезьянью сортировку":
1. Проверить лежат ли все карты по порядку.
2. Если нет - подкинуть колоду в воздух, собрать карты с пола и перейти к пункту 1.
Вчера в интернете попалась шикарная постановка с исполнительными слугами и четырьмя алгоритмами сортировки колоды - http://www.youtube.com/user/AlgoRythmics
Один ролик процитирую прямо здесь
Вам хочется кофе? Достаньте инструкцию с надписью "кофе" и отдайте слуге. Слуга прочитает (и выполнит) сотни элементарных действий - "повернись на север, сделай 10 шагов, повернись на восток и сделай ещё 3 шага, протяни правую руку влево и возьми банку с кофе...". Если слуга достаточно быстр, для вас это будет выглядеть, как появление в его руке чашечки с кофе вместо бумажки с надписью "кофе".
Программировать варку кофе довольно сложно, поэтому программисты тренируются на упорядочивании карт в колоде по старшинству (обычно раскладывают одну масть, но это не важно). Чтобы тупой слуга не запутался, придерживаются правила - из колоды брать не более двух карт за раз.
Вот один из вариантов сортировки:
1. Взять две верхние карты из колоды.
2. Младшую положить в новую колоду, старшую оставить на руках.
3. Взять из старой колоды следующую карту.
4. Перейти к пункту 2.
5. Когда старая колода кончится, переложить новую на место старой и вернуться к пункту 1.
Удивительное дело, но через некоторое время все карты в колоде разлягутся по порядку.
Существуют и другие способы.
Недавно узнал про Bogosort или "обезьянью сортировку":
1. Проверить лежат ли все карты по порядку.
2. Если нет - подкинуть колоду в воздух, собрать карты с пола и перейти к пункту 1.
Вчера в интернете попалась шикарная постановка с исполнительными слугами и четырьмя алгоритмами сортировки колоды - http://www.youtube.com/user/AlgoRythmics
Один ролик процитирую прямо здесь
Click to view