Обсуждение:Сортировка вставками

Бинарный поиск

можно усовершенствовать алгоритм используя бинарный поиск в упорядоченной части массива — Эта реплика добавлена участником Fa-sol (о • в) 21:03, 12 марта 2007 (UTC)

   int insertSort(float a[], int first, int last) {
       for ( int pre = first, cur = first + 1; pre < last; pre++, cur++ ) {
           float curVal = a[cur];
           
           if ( a[pre] > curVal ) {
               int fi = first;
               int la = pre;
               
               for ( int mid = ( la + fi ) / 2; la > fi; ) {
                   if ( curVal < a[mid] ) {
                       la = mid;
                   } else {
                       fi = mid + 1;
                   }
                   mid = ( la + fi ) / 2;
               }
               
               for ( int i = pre, j = cur; j > la; i--, j-- ) {
                   a[j] = a[i];
               }
               a[la] = curVal;
           }
       }
       
       return 0; 
   }

213.238.8.13 18:42, 11 января 2011 (UTC)Forzi

Усовершенствовать можно. Но только не так, как вы написали - это никакое не усовершенствование, временная сложность же не уменьшается. Вот как надо: Bender, M., et al. (2004). Insertion Sort is O(n log n). -- X7q 18:58, 11 января 2011 (UTC)

Реализация на Паскале

В примере реализации на Паскале:3 x[j] при первом проходе (для j=0) не вызовет ошибку? Массив ведь определен как [1..N].
Vers2 22:01, 1 июля 2008 (UTC)

Реализация на C++

Я, конечно, понимаю, что это мелочи, но может стоит использовать всё-таки префиксную форму инкремента/декрмента для переменной цикла (i,j)
(Buran 01:40, 22 декабря 2008 (UTC))

Ссылки на авторитетные источники

У меня вопрос в связи с проставлением этого шаблона. Какого рода источники в интернете могут считаться для этой статьи авторитетными? Например, ссылка на сайт Algolist может быть таковой? ivannesl 08:29, 9 марта 2009 (UTC)

Реализации реализациями, а анализ самого алгоритма в худшем, среднем и лучшем случаях желателен

Иначе получается страница учебника по программированию.

Также неплохо добавить историю: кто впервые описал этот алгоритм, какие бывают усовершенствования....

Реализации можно и в Wikibooks отправить... (IMHO: Wikiwide 08:58, 4 июня 2009 (UTC))

Преимущества

почему убрано «прост в реализации»? Он же действительно прост =) DziedMaroz^talk 21:37, 29 января 2011 (UTC)

простота реализации - не объективная оценка, к тому же относительная) По сравнению с пузырьком например данный метод сложнее в реализации --Insolor 14:28, 4 августа 2011 (UTC)

Примеры псевдокода - что за белиберда?

• Первый и второй примеры псевдокода - совершенно идентичные реализации, отличающейся только сдвинутым на +-1 индексом во внутреннем цикле. То есть это совершенно одно и то же. Зачем было приводить два варианта?

• Третий пример предназначен для того, чтобы проиллюстрировать идею с "guard element", как это сделано в книге Ахо-Ульмана-Хопкрофта: A[0] = очень-маленькое-значение. Весь смысл, вся суть этой идеи заключается в том, что при наличии такого guard element нам не нужно проверять условие `j > 0` во внутреннем цикле. Именно и только ради исключения этой проверки мы и заводили "guard element" `A[0]`. Здесь же какой-то "гений" и guard element завел, и проверку оставил! Зачем было заводить этот guard element (да еще и заострять внимание в тексте статьи, что его значение должно быть маленьким), а потом просто не использовать его вообще? Это просто дичь какая-то...

Calligrapher (обс.) 02:09, 14 августа 2020 (UTC)

В описании алгоритма ничего толком не описано

Что значит на "нужную позицию" ? Каким образом эту нужную позицию вычислять? 93.185.45.95 19:25, 28 декабря 2022 (UTC)