• Библиотечная сортировка
    0
    Спасибо, я погляжу. И даже посмотрю, можно ли этот метод использовать для сортировки. Если да, то отлично: после сортировок вставками будут сортировки выбором, и этот алгоритм органично впишется в этот класс.
  • Библиотечная сортировка
    +3
    Лично я алгоритмы разбираю just for fun. Реализация модифицированного бинарного поиска и полной перебалансировки массива доставили мне некоторое удовольствие.

    Что касается мотивов, которыми руководствовались авторы сортировки — спросите у них. Я привёл персональные странички профессоров на сайтах их университетов, там есть электронные адреса.
  • Библиотечная сортировка
    +2
    И она будет :)
  • Сортировки вставками
    0
    А вот тут большое Вам спасибо. На досуге протестирую и даже, скорее всего, возьму эти реализации себе как основные для данных сортировок.

    А то в комментариях мода такая — пишут: «у вас реализации неэффективные», но хоть бы кто привёл «правильные» варианты алгоритмов.
  • Сортировки вставками
    0
    Что касается вот этого:
    У неё нет рекурсии и поэтому в отличие от своих коллег она успешно обработывает массивы, состоящие из миллионов элементов
    У меня при тестировании действительно различные варианты быстрой сортировки не могут осилить массивы, состоящие из миллионов элементов. А вот расчёска сортирует быстро и без проблем.
  • Сортировки вставками
    0
    Есть подозрение, что я двусмысленно выразился в статье и мы вообще говорим о разных вещах.
    Сортировка расчёской по похожему принципу улучшает пузырьковую сортировку, благодаря чему временна́я сложность алгоритма с O(n2) подскакивает аж до O(n log n). Увы, но Шеллу этот подвиг повторить не удаётся — лучшая временна́я сложность достигает O(n log2 n).
    Я имел ввиду, что если модифицировать сортировку пузырьком (имеющую сложность O(n2)) в сортировку расчёской, то получаем алгоритм со сложностью O(n log n).
    А вот если похожей модификацией сортировку вставками (имеющую сложность O(n2)) преобразовать в сортировку Шелла, то получаем алгоритм со сложностью O(n log2 n).
    То есть и сортировка Шелла и сортировка расчёской — это аналогичные модификации из более простых алгоритмов со сложностью O(n2). И хоть это и похожие модификации, сортировка расчёской всё-таки в общем случае достигает лучших результатов, чем Шелл.

    Когда я упомянул сложность O(n2) то речь шла о сортировке пузырьком и сортировке вставками. А не о худшей сложности расчёски и Шелла, о чём мы и ведём эту странную дискуссию.
  • Сортировки вставками
    0
    Сложности в худшем случае (по данным той же Википедии) у этих алгоритмов одинаковы — O(n2). Причём, подозреваю, что вырожденные случаи у Comb sort и Shell sort совершенно разные. На каких-то наборах данных один алгоритм будет зависать, а второй щёлкать как орешки. А универсальных вырожденных случаев (чтобы были одновременно вырожденными для обоих алгоритмов) может запросто и не оказаться. А если так, то какой смысл сравнения по худшему случаю?

    В целом Вы подняли интересную тему. К сожалению, у меня сейчас банально нет времени проводить обстоятельное научное исследование, по отлавливанию и нейтрализации худших случаев для Shell sort / Comb sort. Если Вас так волнует эта тема, то почему бы Вам этим и не заняться за счёт своего, а не моего времени? Я сейчас пишу серию из около 30-ти обзорных (подчёркиваю — обзорных, а не уровня Arxiv.org) статей по 80+ алгоритмам, принадлежащим к 6 основным классам сортировок. Я не буду бросать эту работу только для того, чтобы Вам что-то доказывать по поводу Шелла и расчёски. Так что прошу меня извинить.
  • Сортировки вставками
    0
    Давайте снова внимательно почитаем Википедию.

    Сортировка расчёской

    Лучшее время — O(n log n)
    Сравнение алгоритма с quick sort (цитата) — "… конкурирует с алгоритмами, подобными быстрой сортировке ..."

    Сортировка Шелла

    Лучшее время — O(n log2 n) — ввиду квадратичности это худший, показатель чем у Comb sort.
    Сравнение алгоритма с quick sort (цитата) — "… Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка ...".

    То есть, сама Википедия указывает, что у Comb sort более скоростные показатели чем у Shell sort.

    Что касается «покажите тот случай», то я готов Вам всё показать, просто дайте мне наилучшую по Вашему мнению реализацию Shell sort на том языке программирования, который сочтёте нужным. Я проведу тесты и пришлю Вам все итоговые материалы.
  • Сортировки вставками
    0
    Я просто в этой статье галопом по Европам прошёлся по общеизвестным вставочным сортировкам, не хотел перегружать и так большой материал вырожденными случаями.

    Через несколько статей будет рассказ про сортировку с помощью splay tree, которая как раз преодолевает вырожденные случаи, возникающие у простого binary tree. Там как раз всё и покажу.
  • Сортировки вставками
    0
    Вызываю Вас на дуэль.

    Вы выставляете лучшую реализацию Shell sort (желательно на Python, но можем обсудить язык). Я со своей стороны подберу реализацию Comb sort. Проверим, кто окажется быстрее.
  • Сравнение сортировок обменами
    0
    Я поразмышляю над Вашими замечаниями и постараюсь в будущих статьях, где будут сравниваться другие классы сортировок, учесть критику.

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

    Возможно, раз тестирование у меня такое корявое, я вообще откажусь от этого формата и статьи все будут сугубо теоретическими. В общем, чуть позже определюсь с этим.
  • Сравнение сортировок обменами
    0
    А вот это уже ближе к моим реалиям. Статьи про сортировки вставками также через несколько недель будут завершаться финальным всеобщим тестированием, надо будет действительно это сделать на PyPy. Спасибо, что дали наводку.
  • Сравнение сортировок обменами
    0
    Отличная идея.

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

    Скажем так — данная серия статей ориентирована на тех, кто интересуется теорией алгоритмов.
  • Сравнение сортировок обменами
    0
    Сортировка Шелла принадлежит к классу сортировок вставками, к изучению которого приступаем в следующей статье.
  • Сравнение сортировок обменами
    –1
    Скорее всего, Вы правы и вариант далёк от совершенства с практической точки зрения.

    Честно говоря, я избегаю писать свои версии всех этих многочисленных сортировок, предпочитаю на просторах Интернета находить работающие версии, написанные, по всей видимости, куда большими специалистами чем я. Конечный выбор той или иной реализации обуславливается синтаксисом, наиболее иллюстрирующим основную суть алгоритма. Остальное, ИМХО, вторично в данной ситуации.

    А вообще мне очень нравится вот эта версия:

    def quick_haskell(data):
        return (quick_haskell([y for y in data[1:] if y <  data[0]]) + 
                data[:1] + 
                quick_haskell([y for y in data[1:] if y >= data[0]])) if len(data) > 1 else data

    Но она не вписывается в стиль статьи в духе «о сортировках максимально доступными словами».
  • Сортировки обменами
    0
    Я решил сортировки, в которых случайно перемешивается массив выделить в отдельную группу и рассказать про неё когда-нибудь отдельно.

    Стрелки на КДПВ означают преемственность алгоритмов. Если видоизменить Stupid sort одним образом, то получается Gnome sort. Если другим — то получается Bubble sort. Bubble sort в свою очередь имеет свои модификации — Odd-Even sort, Shaker sort и Comb sort.
  • Сортировки обменами
    0
    Shell sort относится к классу сортировок вставками, про них чуть позже.
  • Сортировки всех времён и народов
    0
    Кстати, сама gif-анимация на последнем этапе формируется с помощью скрипта на PHP. Excel только сохраняет картинки для каждого шага.

    За метод сохранения картинок особая благодарность гуру Excel Николаю Павлову, эту процедуру я содрал из его надстройки PLEX.
  • Сортировки всех времён и народов
    0
    Не знаю, писать именно про макросы VBA не хочется.
  • Сортировки всех времён и народов
    +1
    Именно он. Какую сортировку он символизирует предлагаю угадать самостоятельно.

    А все картинки (заготовки для кругляшков) у меня из гугл-поиска. Саму КДПВ сгенерировал сам, написал пару скриптов для этого.
  • Сортировки всех времён и народов
    +2
    На VBA программирую лет 15. Начиналось всё, когда я работал на одной околобухгалтерской должности в одной крупной компании. Чтобы не утонуть в адской рутине учёта, купил учебник Уокенбаха и автоматизировал в Excel, всё что только получилось автоматизировать для своей деятельности. Ручное формирование отчётов занимало время от пары часов до пары дней. После овладения макросами — от пары секунд до пары минут.

    Сейчас VBA для меня сугубо как хобби.
  • Классические алгоритмы и структуры данных на JavaScript
    0
    Всё мечтаю продолжить эту работу, да времени катастрофически нет… Уже накопилось некоторое количество новых сортировок, которые ещё не заливал на этот сайт и есть планы по выкладыванию в общественный доступ самого excel-приложения с макросами, с помощью которого делаю gif-анимацию алгоритмов.

  • «Амедиа ТВ» хочет привлечь к уголовной ответственности сотрудников студии «Кубик в кубе» за сериалы HBO
    0
    В данном случае, пожалуй, имеет значение, что сериал «Рим» уже несвежий и не ожидается новых сезонов. Денег на нём уже не подымешь.

    Ну и Гоблин сотрудничает с Amedia, им гнобить его причин нет.
  • «Амедиа ТВ» хочет привлечь к уголовной ответственности сотрудников студии «Кубик в кубе» за сериалы HBO
    0
    Есть мнение, что Амедиа решили заняться копирастией и монополизацией рынка, в связи с чем упражняются в преследовании небольших независимых студий.

    Им удобно начать с Кубиков, поскольку когда-то сотрудничали с ними и знают их контакты. На Кубики подать в суд было проще всего. Потом и другими займутся.
  • «Амедиа ТВ» хочет привлечь к уголовной ответственности сотрудников студии «Кубик в кубе» за сериалы HBO
    +1
    Теперь ясно, почему 2-я серия «Кремниевой долины» в озвучке Кубиков на прошлой неделе вышла с таким опозданием :( Этот сериал в других переводах смотреть не могу.

    >>> Но когда узнала, что в студии работает только два человека, отказалась от сотрудничества, объяснив, что им необходима премиум-озвучка на 12 голосов.

    Хоть бы Amedia не позорилась с такими заявлениями, учитывая, что транслируют «Эш против зловещих мертвецов» в одноголосом переводе Гоблина.
  • Изучаем ферзя (часть 3)
    0
    Как часто встречаются (и встречаются ли вообще) дети, способные самостоятельно додуматься до обратного анализа? К примеру, задания №3 «Лабиринт» и №4 «Перехитри часовых» проще решать, если двигаться от конца. То есть, искать не начальные ходы ферзём, а сначала рассмотреть конечные, отсекая сразу много ответвлений, по которым нельзя добраться до конечного пункта. Встречались ли такие «одарённые» ученики, способные столь нестандартно подойти к решению проблемы?
  • Изучаем слона (часть 2)
    0
    А рано ли на этом этапе давать детям уже играть друг с другом?

    Например: 8 слонов против 8 слонов. Выигрывает тот кто уничтожил все фигуры противника. Если остались только разнопольные слоны --> ничья (причём, к выводу что в этой ситуации невозможен чей-либо выигрыш должны дети придти самостоятельно).
  • Изучаем слона (часть 2)
    +1
    Мне уже хочется разучиться играть в шахматы и научиться заново по этой методике :)
  • Изучаем ладью (Часть 1)
    +1
    Ну, пожалуй, тут дело в количестве учеников. Если это целый класс чужих детей, то, наверное, в педагогическом процессе эффективнее задачи с единственным решением.

    Если же обучать по этой методике пару собственных спиногрызов, то, думаю, лучше тогда задачи с несколькими решениями. Потому что я заинтересован в том, чтобы мой ребёнок был творческим и гибким в принятии решений и готов тратить дополнительное время на анализ его стиля мышления и стремлюсь научить чадо искать и находить альтернативы.
  • Изучаем ладью (Часть 1)
    0
    Спасибо, очень интересный цикл статей. Настолько отличается от того, как меня учили шахматам в детстве, что как будто бы открываешь для себя шахматы заново.

    >>> но следует учесть один момент – путь для правильного решения должен быть единственным верным. Этот же совет относится и ко всем другим заданиям, которые будут приведены дальше.

    А почему такая необходимость, чтобы путь был единственно верным? Я считаю что наоборот, если решений несколько, то так даже лучше, даёт дополнительные дидактические возможности:

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

    2)Анализировать те способы, которыми ребёнок решает задачу. Это позволит получить дополнительную информацию о мышлении ученика: умеет ли он выбирать самый эффективный способ, видит ли он вообще более эффективные способы, имеет ли «вредные» предпочтения (например, упорно старается передвигать ладью в правую сторону, хотя в каких то ситуациях намного лучше если сделать ход влево), выбирает ли он самую короткую траекторию для фигуры или самую замысловатую и т.п.
  • Освещал ли СССР высадку на Луну? Взгляд с обратной стороны Земли
    0
    Википедия сообщает что враги (3-я эскадрилья ВВС Австралии) похоронили погибшего в воздушном бою Красного Барона с военными почестями. То есть благородное отношение к противнику (даже если он уничтожил десятки твоих самолётов) имело место быть на той войне. По крайней мере среди лётчиков, считающимися «аристократами» в любой армии.
  • Поехали! Falcon Heavy отправила Tesla на Марс
    +1
    Я так и понял. Поставил Вам плюсики за комменты.

    Просто мне захотелось вставить эту картинку в обсуждение, а тут Ваш ироническая ремарка как раз оказалась кстати.
  • Поехали! Falcon Heavy отправила Tesla на Марс
    0
    Вот тогда и поговорим!
  • Пузырьковая сортировка и все-все-все
    +1
    С начала марта будет мега-серия статей, посвящённая алгоритмам сортировок. Наконец-то в общий доступ выложу программу, с помощью которой подготавливаю эту гиф-анимацию

    Следите за эфиром :)

  • Физические итоги года
    +1
    Теперь понятно, на каких принципах функционируют некоторые из Камней Бесконечности.
  • В защиту Австралии или взгляд изнутри
    0
    Жаль, я желал для НЗ первый вариант.
  • В защиту Австралии или взгляд изнутри
    +1
    Что Вы имеете ввиду? Новая Зеландия становится похожей на ЮАР времён апартеида или на ЮАР в её нынешнем состоянии?
  • Физик Брайан Кокс о космических колониях и будущем человеческой расы
    0
    Впервые Вас плюсану в этом посте, ибо Вы меня очень рассмешили :)
  • Физик Брайан Кокс о космических колониях и будущем человеческой расы
    0
    К большинству минусов и плюсов, кстати я причастен в этом посте (я таким образом отмечаю комментарии, которые видел, так как с интересом слежу за ходом обсуждения). Так что если видите -1 за свой комментарий, то претензии к Valerij56 можете не предъявлять — он к этому не имеет отношения. А если -2, -3, ну значит кроме меня Вас минуснул кто-то ещё.