ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexandr A. Redchuck                 2:5020/400     06 Sep 2001  13:32:42
 To : Andrew Plyako
 Subject : Re: Поиск медианы в небольшом массиве
 -------------------------------------------------------------------------------- 
 

 4-Sep-01 20:24 Andrew Plyako wrote to All:
 
 AP> All, а какой алгоритма поиска медианы (среднего по величине элемента)
 AP> для
 AP> небольших (порядка 10-20 элементов) массивов. Для больших массивов Вирт
 AP> рекомендует 'облегченный' QuickSort - после каждой итерации обрабатывается
 AP> та часть массива, которая содержит средний элемент.
 
 AP> А как быть с небольшими массивами? Какие есть идеи|предложения как
 AP> побыстрее найти медиану в этом случае?
 
 Я когда-то на количествах 9-49 элементов (от 3x3 до 7x7 :-) пришел к выводу,
 что быстрее всего вставки с выходным массивом половинной длины.
 Все равно _полная_ сортировка не нужна, то что вышло по индексу за
 пределы (N+1)/2 уже явно на выброс. Т.е. для 25 входных элементов
 выходной массив берем 13 элементов и при вставке очередного элемента
 сдвигаем вверх элементы от "куда ставим" до 12-го. 13-й выбрасывается.
 
 WBR,
 
 --
 /* Alexandr Redchuck, Kyiv, Ukraine */
 /* real@real.kiev.ua                */
 
 --- ifmail v.2.15dev5
  * Origin: ReAl at home (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Поиск медианы в небольшом массиве   Andrew Plyako   04 Sep 2001 21:24:24   Re: Поиск медианы в небольшом массиве   Alexandr A. Redchuck   06 Sep 2001 13:32:42