Самый быстрый алгоритм сортировки для конкретной ситуации

Question

Какой самый быстрый алгоритм сортировки для большого числа (десятки тысяч) групп с 9 положительными значениями двойной точности, где каждая группа должна сортироваться индивидуально?Поэтому необходимо быстро отсортировать небольшое количество повторяющихся значений двойной точности, много раз подряд.Значения находятся в интервале [0..1].Меня не волнует космическая сложность или стабильность, просто скорость.

Answer 1

Сортировка каждой группы отдельно, сортировка слиянием, вероятно, будет проще всего осуществить с хорошими результатами.

Сортировочная сеть, вероятно, будет самым быстрым решением: http://en.wikipedia.org/wiki/Sorting_network

Answer 2

Похоже, вам нужен самый цикличный способ сортировки 9 значений. Поскольку количество значений ограничено, я бы (как предложила Кэти) сначала выполнил бы развернутую сортировку вставки для первых 4 элементов и вторых 5 элементов. Тогда я бы объединил эти две группы.

Вот развернутый вид вставки из 4 элементов:

if (u[1] < u[0]) swap(u[0], u[1]);
if (u[2] < u[0]) swap(u[0], u[2]);
if (u[3] < u[0]) swap(u[0], u[3]);

if (u[2] < u[1]) swap(u[1], u[2]);
if (u[3] < u[1]) swap(u[1], u[3]);

if (u[3] < u[2]) swap(u[2], u[3]);

Вот цикл слияния. Первый набор из 4 элементов находится в u, а второй набор из 5 элементов - в v. Результат в r.

i = j = k = 0;
while(i < 4 && j < 5){
  if (u[i] < v[j]) r[k++] = u[i++];
  else if (v[j] < u[i]) r[k++] = v[j++];
  else {
    r[k++] = u[i++];
    r[k++] = v[j++];
  }
}
while (i < 4) r[k++] = u[i++];
while (j < 5) r[k++] = v[j++];

Answer 3

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

• сортировочная сеть
• сортировка вставок
• быстрая сортировка (один уровень - вставка сортировки ниже)
• сортировка слиянием

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

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

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

Answer 4

Хороший вопрос, потому что это сводится к «Самому быстрому способу сортировки массива из 9 элементов», и большинство сравнений и анализа методов сортировки касаются больших N. Я предполагаю, что «группы» четко определены и не играют реальная роль здесь.

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

В любом случае, параллельное звучание звучит как хорошая идея. Используйте Parallel.For(), если вы можете использовать, NET4.