Имеется некий массив целых чисел. Необходимо найти моду этой выборки.
(Мода - значение, которое встречается наиболее часто)
Нужен самый оптимальный алгоритм.

бруталфорсно... загнать в ТЧ, добавить колонку, вписать в нее 1. Свернуть и отсортировать

(0) в таблице значений создать две колонки:
1. ваши значения
2. число 1
свернуть по значениям, суммирую по второй колонке
отсортировать по второй колонке в обратном порядке

(1) эх...

ТЗ с двумя колонками. В первой число, во второй 1. Свернуть по первой колонке, суммировать вторую. Сортировать по второй колонке по убыванию.

т.е. в ТЗ

гы

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

подумайте, что делать, когда мода неоднозначно определяется

а простой цикл по массиву не будет быстрее операций с ТЗ?

(0) если нужен именно алгоритм (реализация не на 1C), то быстрее будет так: сортируем массив. Проходим его с начала до конца, считая одинаковые значения и обновляя максимум.

(9) как минимум нужно несколько циклов, в том числе вложенные

(10) >то быстрее будет так: сортируем массив

как?

Если известен диапазон разброса целых чисел, то хватит двух циклов и доп. массива.

(12) по порядку. Главное, чтобы одинаковые значения стояли вместе

(14) вроде как нету штатного метода сортировки... а если его изобретать самому, то быстрее не получится

(15) в (10) я специально уточнил [если нужен именно алгоритм (реализация не на 1C)]

(7) нужен алгоритм. Задача не для 1С

(13) если неизвестен, то 3 цикла

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

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

(0) Ты не указал сортированный массив или нет.
А посему 2 разных подхода.

(18) речь ведь о целых числах.

(18) [делаем массив длиной, равной ширине диапазона ]

слишком строгое допущение. Как тебе такой массив из двух элементов [1, 12345678901234567891237890]?

(19) Точно! Отсортировать массив и сравнивать в цикле каждое последующее значение с предыдущим, запоминая количество совпадений и само число. Искать максимум этой переменной, которая содержит количество совпадений

(22) а в (10) что, не так что ли? )

(21) поэтому я и спрашивал про ширину диапазона, для частных случаев будет самым быстрым решением.

(22) сортировка не самая быстрая операция над массивом.

http://www.lotos-khv.narod.ru/algoritm/sort/sort6.htm

(24) Наоборот, грамотная сортировка одна из быстрейших операций над массивом.

(26) она медленнее, чем один проход по массиву. поэтому в ЧАСТНЫХ случаях, мой способ отработает быстрее.

(24) а нельзя ли совместить сортировку с основной обработкой?

(28) Ссылку в (25) уже смотрел?!

(29) смотрю.. думаю..
Еще вариант, на пробу - обходить основной массив, для каждого уникального элемента создавать свой массив. И в конце подсчитать, чей массив "больше весит".
Для больших выборок это может быть быстрее, чем сортировка

(30) Если тупо, то делаешь вспомогательный массив, гоняешь по данному массиву и считаешь количество элементов и суешь во вспомогательный массив. Далее поиск максимального во вспомогательном массиве массиве. Их может быть несколько, что тоже не проблема.
Все. Сортировки нет.

(30) добавь поиск нужного массива, получишь O(n^2), а в (10) O(n*log n)

Получается, что данную задачу свели к 2-м.
1) Определить количество вхождений каждого значения в массив.
2) Поиск максимума по количеству значений.

(31) соответствие между элементами первого и второго массива какое будешь делать?

(34) Если тупо, то индекс в индекс.

(34) и как тогда будешь различать одинаковые элементы? сначала найдешь все максимумы во втором массиве, потом их будешь сравнивать?

и получается, что по первому массиву ты проходишься n раз? n - длина первого массива.

(36) на (35)

http://doors.infor.ru/allsrs/alg/paper/sort.html

(36) Если тупо, то да.

(38) откуда ты откопал такую древность?

(39) тогда прохождение n раз по массиву съедает всю экономию.

Вот еще вариант:
Создаем пустой массив. Обходим исходный массив в цикле. Если текущего значения нет в доп массиве, то копируем его в доп массив и удаляем этот элемент из исходного массива. Если есть - оставляем. Потом обнуляем доп массив и тоже самое, пока не останется один.
Пример:

1 1 2 3 4 5 4 5 5 6 9
Первый обход:
_ 1 _ _ _ _ 4 5 5 _ _  (_ - удаленные) (Доп массив: 1 2 3 4 5 6 9)
Обнуляем доп массив
Второй обход: (исходный: 1 4 5 5)
_ _ _ 5 (Доп массив: 1 4 5)

Итого: Победил 5, мода = число обходов +1

* Создаем пустой ДОПОЛНИТЕЛЬНЫЙ массив

(42) [Если текущего значения нет в доп массиве]

Означает N раз пройти доп. массив. В топку такие алгоритмы

"Если текущего значения нет в доп массиве", ""удаляем этот элемент из исходного массива" - две затратные операции.
тебе оптимальную или как?)

(44) И что взамен?!

(44) если в исходном массиве много повторяющихся значений, то доп массив будет очень мал. Это лучше, чем делать сортировку основного большого массива

(47) Дан массив, как ты определишь "много-мало"?!

+47 к тому же размер доп массива непостоянен, он прибавляет в весе только в процессе обхода

(46) да сколько раз повторять. Сортируем массив. Эта операция занимает О(n*log n) времени. Все одинаковые элементы оказываются рядом. Делаем проход, где подсчитываем одинаковые элементы, и если кол-во больше, обновляем максимум и устанавливаем текущий элемент как результат.

(46) пока что самый универсальный из быстрых - сортировка с последующим счетом одинаковых.

из неуниверсальных - тот, что я предлагал.

Товарищи. Предлагаю решить спор технически:
Обработка с рандомной выборкой до 10, с различными способами обработки

+52 количество элементов 1000, включаем замер и смотрим

(52) до десяти - сам считай на пальцах. А в рамках статистики интересны от миллиона..

(52) а полное условие исходной задачи, точное, можно в студию?

(50) Я предложил вариант без сортировки, как хотел (0).
Согласен с тобой. Лично я бы не заморачился и сделал бы с сортировкой.
А вот какую сортировку взять, зависит о сложности задачи.
Если просто и тупо, то пузырек. Если повыпендриваться, то ... тоже ясно.

(51) То есть (25).

(54) до 10 - это разброс целых значений. А количество элементов можно сделать какое угодно.

доча такую задачу решала в инстике, первый курс
динамических массивов она не знает по определению задачи

(57) для известного малого диапазона, (18) самое оптимальное.

(58) при чем здесь динамические массивы?

(59) Только что будем делать с отрицательными числами?!
Вводить сдвиг индекса?!

(60) с ним все просче
за один проход и вкладываем значения и суммируем количество

(62) на реализацию постоянной реалокации массива закрываем глаза?

(55) полный текст задачи примерно такой и есть. Единственное, что выборка из дробных значений, и для моды нужно установить округление. А так все тоже самое.
http://s60.radikal.ru/i168/1006/a1/a329e28ef27a.jpg

(63) ага ))

(61) да

(64) гы) "Единственное, что выборка из дробных значений" - это многое меняет

(67)нет. Для этого есть округление, которое выстанавливает экспериментатор. Тогда значения 0,7651  0,7792 0,7813  превращаются в 0,76 0,78 0,78 - что по сути не мешает никак. выбирай любое округление - и рассчитывай моду

(68) короче, какой разброс диапазона?
я так понимаю, что он известен?

(69) известен, он задается округлением. Для значений 0,7651  0,7792 0,7813 0,7112
Диапазон может быть как 0,7 - 0,8 (0,8  0,8 0,8 0,7), так и 0,70 - 0,80 (0,76 0,78 0,78 0,71).