Какой будет самый производительный алгоритм сортировки?

Question

[Paul Fawkes]

В общем у меня есть массив byte[N] 1<N<10^6 и из этого массива мне нужно подставить числа в формулу x = 2 * byte[i]; причем сперва в формулу должны подставляться самые большие числа, ну я подумал что для начала стоило бы отсортировать массив byte[N] по убыванию, или есть какой-то другой способ?

Comments

[edward_freedom]

ты перед созданием темы искал инфу или сразу тут запостил, чтобы за тебя поискали? https://habr.com/ru/post/335920/

[Paul Fawkes]

edward_freedom, помимо заголовка прочитайте пожалуйста еще и текст

[edward_freedom]

Paul Fawkes, ты указал в теме только

В общем у меня есть массив byte[N]

Я исходя из этой информации дал ответ тебе. А то что ты дописал потом, не считается

[Paul Fawkes]

edward_freedom, что за тупая логика? я попросил совет и вдруг есть реализации получше

[edward_freedom]

Paul Fawkes, человечество не придумало еще новых сортировок, все реализации уже давно описаны, ты хотя бы поискал перед созданием темы

[Paul Fawkes]

edward_freedom, я знаю что есть сортировки, и знаю какие есть! вопрос ставился еще в том что ПОДСКАЖИТЕ ДРУГИЕ РЕАЛИЗАЦИИ

[edward_freedom]

Paul Fawkes, другие от уже существующих или есть другие другие?

[Paul Fawkes]

#, спасибо буду признателен

Answer 1

[dollar]

Сложность сортировки в общем случае будет O(N*log(N)).

Но если есть или вы готовы ввести дополнительные ограничения, то можно улучшить этот показатель.

Вот пример для вашего случая.

spoiler

Что есть "большое число"? Предположим, это число от 90 до 100.

Предположим, у вас значения распределены в массиве более или менее равномерно (имеется в виду частота встречаемости). На самом деле не важно, какое распределение, главное знать, какое оно. В любом случае это дополнительное условие. То есть если про массив не известно ничего, то можно либо предположить это дополнительное условие, сославшись на отсутствие прочих данных, либо поменять программу так, чтобы оно соблюдалось.

Таким образом, если распределение равномерно, то большие числа составляют примерно 10% от общего количества элементов. На самом деле важнее всего, что пороговое число - 90.

Теперь мы можем сортировать массив простым алгоритмом сложности O(N) - просто на две кучи: большие и маленькие числа. Делим массив в соотношении 1 к 10, ну и сортируем за один проход. Конечно, будут накладки, но в целом это должно быть не критично. Отсутствие важности - это тоже дополнительное условие, увы.

В результате такой стремительной сортировки вы получаете самые большие числа в начале и остальные в конце. Дальше можно скормить это вашей формуле.

Comments

[Paul Fawkes]

ограничение по времени 5 сек, по памяти 256мб, числа в массиве расположены рандомно

[Paul Fawkes]

числа в массиве в рамках 1<число<100

[freeExec]

Paul Fawkes, Числа в массиве уникальны?

[dollar]

Paul Fawkes, было бы проще, если бы вы в вопросе указали предметную область, то есть где это всё используется. Но теперь уж поздно, я дал слишком развернутый ответ)

[Paul Fawkes]

dollar, обязательно что бы массив в итоге был отсортирован по убыванию

[dollar]

Paul Fawkes, если вам важно, чтобы это условие строго выполнялось, то тогда только классика, и сложность будет не менее N*logN, иначе никак.

Просто если вы готовы закрыть глаза на то, что в итоге два случайных элемента будут не на своих местах, то тогда уже можно торговаться с математикой, идти на прочие уступки, выигрывая время. То есть в любом случае за скорость нужно платить - либо точностью, либо памятью, либо чем-то еще. И если вы непреклонны, то скорость работы сортировки отвечает вам той же монетой, и выбор у вас не велик.

Вопрос лишь в том, чем вы готовы пожертвовать. Тогда можно думать, как провернуть сделку по обмену на скорость. Пока что вопрос слишком абстрактный.

[Paul Fawkes]

dollar, окей и какая лучше всего сортировка подойдёт под мой случай?

[dollar]

Paul Fawkes,
Быстрая.
Только ваш случай я не знаю, вы его не описали, он слишком абстрактный.

[Paul Fawkes]

dollar, описываю: формула testi = (2*x + 1) * ci, где testi — время, которое занимает тест i-й задачи, x — количество задач, ранее протестированных на этом устройстве.
Условиe:
число задач 1 < N < 106
число устройств 1 ≤ k ≤ N
и время на задачу 0 < ci < 100
Долго не думая я понял, что лучше всего в формулу подставлять числа по убыванию поэтому добавил все числа ci в массив byte[] и хочу отсортировать! НО Вопрос какой сортировкой? БЫть может моя реализация в корне плоха?

[dollar]

Paul Fawkes, прочитал ваши первые комментарии. :)

С учетом того, что количество у вас под миллион, а значений всего 100, то подойдет сортировка подсчетом.

[dollar]

Paul Fawkes, не совсем понимаю задачу, но мне кажется, что подсчитав количество каждого значения, эту инфу можно использовать в формуле. То есть за один проход O(N) можно подсчитать значения, а дальше уже работать с результатами подсчета. Как вам?

[Paul Fawkes]

dollar, забыл добавить условие время общее время testi должно быть наименьшее, так что сначала нужно подставлять максимальные числа

[#]

Paul Fawkes, вы сообщаете массу информации, по существу противоречащей изначальной постановке вопроса
нанем с малого:
- зачем вам вообще сортртировать иоги тестов. не, ну понятно что может быть интересна какая то статистика после окончания всего цикла тестов. но чем она вам поможет в процессе проведения тестов?

нсли вы хоите реальной помощи - реально пишите проблему

все что вы говорите в этих каментах, делает ваш вопрос абсолютно лишенным смысла

Answer 2

[Владимир Коротенко]

Корень всех зол предварительная оптимизация (С)

byte[] bytes =  { 88, 77,67,43,74,99,89 };
	    foreach(var b in bytes.OrderByDescending(x=>x)){			
			var r = 2 * b;
		}

Comments

[shai_hulud]

OrderByDescending

Идрить ты синьйор.

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.

[Владимир Коротенко]

shai_hulud, Чем вам не нравится этот код?
И аргументация из детского сада.

Идрить ты синьйор

[shai_hulud]

Владимир Коротенко, мемори трафиком, аллокацией временного мусора как не в себя. Ответ выпускника каких нибудь интернет курсов.

Полную цитату про "преждевременную оптимизацию" я привел. Но современные "синьеры" не упускают возможности преждевременно де-оптимизировать.

[Владимир Коротенко]

shai_hulud, Код понятный, дубовый, линейный понятный даже выпускнику каких нибудь курсов, если данные будут из БД, то там уже сам компилятор позаботится про то как лучше сделать меппэнг.

Так чем, после приведения этих аргументов, он плох? Или же вы хак на хаке предпочитаете писать, игнорируя рекомендуемые конструкции языка, без веских на то причин?

Answer 3

[GavriKos]

byte - т.е. целые, да еще и максимум 256? Проходим по массиву, считаем количество каждого числа. Т.е. заводим массив из 256 нулей, идем по вашему массиву, и инкрементим значение маленького массива, используя в качестве индекса значение из большого массива. Получим то что нужно без сортировки вообще.
Потом просто вызываем формулу нужное количество раз для каждого элемента.

Что то похожее в комментах предложил dollar, если я правильно понял.