Бисерная сортировка (Bead sort)

Может быть. Мне тоже изначально не нравится O(n²), просто решил не перечить оклендским математикам, а предоставить опровержение хабраюзерам прочитавшим эту статью.

Бисерная сортировка (Bead sort)

Чаще всего сортировку наглядно представляют как бисер нанизанный на спицы. Или как шарики, скатывающиеся по узким желобкам. Второй вариант мне был проще для создания анимации.

O(1) — это результат некоего теоретизированного рассуждения, мысленный эксперимент с участием идеального физического устройства в идеальных условиях, реализующего эту сортировку. Если абсолютно исключить трение, поместить устройство вблизи сверхмассивного тела, мгновенно и одномоментно предоставить шарикам возможность упасть вниз по спицам — то временная сложность будет стремиться как раз к такому значению. Как-то так.

Бисерная сортировка (Bead sort)

O(n²) — это худший случай по памяти. Максимальное количество возможных значений n сортируемых натуральных чисел как раз равно n. В худшем случае m = n.

Почему при оценке памяти именно умножение, а не сложение? Потому что изначально входной массив из n элементов, а дополнительно приходится обрабатывать матрицу n x n (в худшем случае).

Насчёт counting sort. Да, бисерная сортировка — это сортировка подсчётом, но только через «одно место», ухудшенный вариант. Вместо того чтобы обрабатывать сами сортируемые числа, мы обрабатываем каждую единичку каждого числа. Всего единиц в массиве натуральных чисел равно сумме всех чисел S, отсюда и временная сложность O(S).

Сортировать бусинками невыгодно с какой стороны ни посмотри, но для пятничного поста алгоритм вполне годится :)

Бисерная сортировка (Bead sort)

Это статья о страшной сортировке в честь надвигающегося Хеллоуина :)

Бисерная сортировка (Bead sort)

Пожалуй, да )

История одного собеседования, или как в компании X кандидата «вешали»

Фильм зачётный, как и всё творчество Акиры Куросавы.

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

История одного собеседования, или как в компании X кандидата «вешали»

По содержанию фейсбуковской заметки А и его дальнейшим действиям (стирание записи с разоблачающими комментариями и последующее стыдливое помалкивание) можно сделать однозначный вывод что А:

1)Высокомерен.
2)Труслив.
3)Некомпетентен.
4)Нетактичен.

Оборони Б-г от таких начальников.

Офис компании Null Team

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

P.S. В общем, пора спать.

Офис компании Null Team

Забавно, Марьян и Иоана — разработчики, а Моника и Даниэла — разработчицы. :)

В целом, симпатичный отчёт. Приелись уже эти офисы будущего.

Как я победил в олимпиаде по программированию, не умея программировать

Как бывший школьный учитель обожаю такие истории :)

Расскажите ещё про какую-нибудь успешно пройденную олимпиаду :)

Как я победил в олимпиаде по программированию, не умея программировать

Вадимка… Какое красивое женское имя…

Как я победил в олимпиаде по программированию, не умея программировать

Да, большое спасибо, после третьего объяснения для меня всё встало на свои места. )

Как я победил в олимпиаде по программированию, не умея программировать

В принципе, я не обратил внимание на последний абзац. Олимпиада проводилась в Советском районе города Самары, городская олимпиада, значит, уже проводилась среди победителей районов города. Теперь всё ясно.

Как я победил в олимпиаде по программированию, не умея программировать

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

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

Как я победил в олимпиаде по программированию, не умея программировать

Уровень проверяющих, видать, был не ахти. Если Вы только поменяли имена переменных и + специально сделали одну ошибку — всё равно подлог очевиден. Скорее всего, сыграл фактор того что олимпиада проводилась на территории Вашей школы, и комиссия решила прикрыть на это глаза, тем более что на следующий этап ехал победитель, а не занявший 2-е место. Сам бывший учитель информатики и хорошо представляю как на уровне школ проводят олимпиады :)

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

В целом, зачётный рассказ. Он скорее не об обмане, а про то как человек искал и нашёл выход в безвыходном положении.

Непрактичные сортировки – бессмысленные и беспощадные

Для заинтересовавшихся оформлю в более наглядном виде:

function BogoSort2(array) {

    array.sort(function() {

        return Math.random() > 0.5; 

    });

    if (!isSorted(array)) return BogoSort2(array);

    return array;

}

function isSorted(array) {

    for(var i = 1, l = array.length; i < l; i++) {

        if(array[i] < array[i-1]) return false;

    }

    return true; 

}

Непрактичные сортировки – бессмысленные и беспощадные

Спасибо за наводку. Как дойдут руки через пару недель сделать продолжение этой темы, то метод сортировки «Разумного замысла» туда обязательно войдёт.

Непрактичные сортировки – бессмысленные и беспощадные

Ну, «изобрести» в детстве то что уже давно придумано — это святое. Если в юном возрасте есть желание и попытки «вносить свой вклад в науку» то можно только поприветствовать. Лишь бы в дальнейшем это не приобретало клинических форм как у некоторых.

Кроме того, приведённый способ не является «самой что ни на есть каноничной «сортировкой выбором». Об этом свидетельствует и честно признаваемая автором применимость только к массивам с неповторяющимися элементами. А также использование дополнительного массива (в классической selection sort расходов на дополнительную память нет).

Непрактичные сортировки – бессмысленные и беспощадные

Вы абсолютно правы. В соответсвующем месте текста добавил примечание по этому поводу.

Непрактичные сортировки – бессмысленные и беспощадные

«Иммунитет» хорошо проявляет себя в паре с другим антивирусом. (Бабушкин)

Сортировка Бабушкина особенно эффективна в симбиозе с другой сортировкой.