alizar 31 мая 2013 в 22:16

Архив интересного кода

1 мин

54K

C++ * Алгоритмы * Программирование *

+80

Комментарии 33

Frink 31 мая 2013 в 22:32

Достаточно амбициозно… но если Кейту действительно нравится всё это делать (анализировать и очень тщательно комментировать), то получится шикарная коллекция. Я думаю многие будут о-очень благодарны ему.
Однозначно в избранное.

primepix 31 мая 2013 в 23:40

Алгоритм Дейкстры-то уж без сомнения очень серьезная вещь :)

Ну, а в целом конечно крайне импонирует видеть такие ресурсы

guyfawkes 1 июн 2013 в 07:50

Зато исходники прокомментированы, хорошо отформатированы, так что подход к делу основательный)

turboNOMAD 1 июн 2013 в 06:19

Keith правильно читается как «Кит». Кейт (Kate) — это женское имя.

НЛО прилетело и опубликовало эту надпись здесь

newdya 1 июн 2013 в 09:30

В качестве личного имени Keith встречается у британцев и американцев, так что следует читать по-английски.

НЛО прилетело и опубликовало эту надпись здесь

mwizard 1 июн 2013 в 06:47

Надеюсь, в коллекцию попадет референсная реализация bubblesort ;)

freopen 1 июн 2013 в 07:09

Что такое референсная реализация 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);

Deshene 1 июн 2013 в 10:33

Это Вы так шутить изволили? :)

freopen 1 июн 2013 в 15:51

Ни капли. Сколько я не гуглил референсную реализацию пузырька на русском и английском — ничего не нашел. Вот и интересуюсь, что такое?

Deshene 1 июн 2013 в 17:44

Как насчет этого?

Или, если брать Ваш пример кода, то нужно сделать следующие небольшие изменения:

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.

freopen 1 июн 2013 в 19:01

Разумеется я знаю эту и некоторые другие реализации пузырька. Меня интересует одна конкретная реализация пузырька — «референсная», которая настолько интересна, что инициатор ветки предлагает добавить ее в список выше.

un_def 1 июн 2013 в 21:10

Если оптимизировать количество итераций, то стоит тогда добавить во внутренний цикл флаг обмена и проверять его во внешнем.

Deshene 1 июн 2013 в 23:34

Ой-вей, только j < n-i, опечаточка вышла.

winger 1 июн 2013 в 06:56

e-maxx.ru/algo/

sdevalex 1 июн 2013 в 07:03

Очень красиво написано (методы сгруппированы, оставлены пустые строки для разделения разных секций, пробелы все на месте, одно удовольствие читать). В России\Украине преподаватели так не пишут, у всех все как попало…

lair 1 июн 2013 в 07:19

Примеры на сайте преимущественно закодированы в 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 предоставляет прекрасную базу для выражения алгоритмов, работающих с различными типами данных».

freopen 1 июн 2013 в 07:22

Ну если открыть ссылку, можно узнать, что алгоритмы преимущественно закодированы в C++ из-за библиотеки шаблонов, а структуры данных — на Java из-за Collections и сборщика мусора.
UPD. уже не актуально :(

lair 1 июн 2013 в 07:24

Ссылку-то я открыл. Просто Ализар традиционно переврал оригинал.

(ну и да, описывать структуры данных на языке со сборщиком мусора — это, конечно, современно, но не всегда поучительно)

chersanya 1 июн 2013 в 07:42

Удобно, что сразу в одном месте описание алгоритма, строгое доказательство корректности, и реализация. Хотелось бы конечно ещё группировку по темам (как на e-maxx например), может быть автор добавит.

Rational_Yurij 1 июн 2013 в 09:57

А где строгие доказательства?

chersanya 1 июн 2013 в 11:24

Вообще я сначала наугад открыл www.keithschwarz.com/interesting/code/?dir=egyptian-fraction — там полное доказательство. Сейчас на другие алгоритмы посмотрел, действительно — во многих этого нет.