Комментарии 33
Достаточно амбициозно… но если Кейту действительно нравится всё это делать (анализировать и очень тщательно комментировать), то получится шикарная коллекция. Я думаю многие будут о-очень благодарны ему.
Однозначно в избранное.
Однозначно в избранное.
Алгоритм Дейкстры-то уж без сомнения очень серьезная вещь :)
Ну, а в целом конечно крайне импонирует видеть такие ресурсы
Ну, а в целом конечно крайне импонирует видеть такие ресурсы
Keith правильно читается как «Кит». Кейт (Kate) — это женское имя.
Надеюсь, в коллекцию попадет референсная реализация bubblesort ;)
Что такое референсная реализация bubblesort? Уж не это ли?
for (int i=0;i<n;i++) ref[i]=i;
for (int i=0;i<n;i++)
for (int j=0;j<n-1;j++)
if (to_sort[ref[j]] > to_sort[ref[j+1]])
swap(ref[j],ref[j+1);
Это Вы так шутить изволили? :)
Ни капли. Сколько я не гуглил референсную реализацию пузырька на русском и английском — ничего не нашел. Вот и интересуюсь, что такое?
Как насчет этого?
Или, если брать Ваш пример кода, то нужно сделать следующие небольшие изменения:
В чем суть: это небольшое изменение снизит количество сравнений с n*(n-1) до n*(n-1)/2, при этом оставив сортировку корректной. Насколько я знаю, это лучшая возможная реализация сортировки пузырьком.
О корректности:
К концу первой итерации внешнего цикла максимальный элемент будет находится в конце массива. Потому, на второй итерации, когда мы будем гнать «второй сверху» элемент на предпоследнее место в массиве, нам нет смысла сравнивать его с последним, потому что тот, заведомо больше. Отсюда и условие
Или, если брать Ваш пример кода, то нужно сделать следующие небольшие изменения:
for (int i=1;i<n;i++)
for (int j=0;j<i;j++)
if (to_sort[ref[j]] > to_sort[ref[j+1]])
swap(ref[j],ref[j+1);
В чем суть: это небольшое изменение снизит количество сравнений с n*(n-1) до n*(n-1)/2, при этом оставив сортировку корректной. Насколько я знаю, это лучшая возможная реализация сортировки пузырьком.
О корректности:
К концу первой итерации внешнего цикла максимальный элемент будет находится в конце массива. Потому, на второй итерации, когда мы будем гнать «второй сверху» элемент на предпоследнее место в массиве, нам нет смысла сравнивать его с последним, потому что тот, заведомо больше. Отсюда и условие
j < i.Разумеется я знаю эту и некоторые другие реализации пузырька. Меня интересует одна конкретная реализация пузырька — «референсная», которая настолько интересна, что инициатор ветки предлагает добавить ее в список выше.
Если оптимизировать количество итераций, то стоит тогда добавить во внутренний цикл флаг обмена и проверять его во внешнем.
Ой-вей, только
j < n-i, опечаточка вышла.
Очень красиво написано (методы сгруппированы, оставлены пустые строки для разделения разных секций, пробелы все на месте, одно удовольствие читать). В России\Украине преподаватели так не пишут, у всех все как попало…
Примеры на сайте преимущественно закодированы в C++, поскольку этот язык лучше всего подходит для описания алгоритмов.
Ась?
На всякий случай, цитата из самого автора:
I generally prefer to use C++ for algorithms, since the STL provides a great framework for expressing algorithms that work on a variety of data types.
«Я предпочитаю использовать для алгоритмов C++, поскольку STL предоставляет прекрасную базу для выражения алгоритмов, работающих с различными типами данных».
Удобно, что сразу в одном месте описание алгоритма, строгое доказательство корректности, и реализация. Хотелось бы конечно ещё группировку по темам (как на e-maxx например), может быть автор добавит.
А где строгие доказательства?
Вообще я сначала наугад открыл www.keithschwarz.com/interesting/code/?dir=egyptian-fraction — там полное доказательство. Сейчас на другие алгоритмы посмотрел, действительно — во многих этого нет.
Здесь явно не хватает целочисленного алгоритма вычисления инверсного обратного корня.
А можно было и на github все это класть :)
Тесты есть?:)
Я вот, когда на JS искал Levenshtein distance, нашел некий rosettacode.org
Например, rosettacode.org/wiki/Levenshtein_distance
Например, rosettacode.org/wiki/Levenshtein_distance
Вот это?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Архив интересного кода