Реализация алгоритма FAST для сортировки очень маленького списка

Question

Реализация алгоритма FAST для сортировки очень маленького списка

Это - проблема, с которой я столкнулся давным-давно. Я думал, что могу попросить у Вашего Ваших идей. предположите, что у меня есть очень маленький список чисел (целые числа), 4 или 8 элементов, которые должны быть отсортированы, быстро. каков был бы лучший подход/алгоритм?

мой подход должен был использовать макс. функции / минимальные функции (10 функций для сортировки 4 чисел, никаких ответвлений, iirc).

// s(i,j) == max(i,j), min(i,j)
i,j = s(i,j)
k,l = s(k,l)
i,k = s(i,k) // i on top
j,l = s(j,l) // l on bottom
j,k = s(j,k)

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

В этой точке это становится несколько аппаратно-зависимым, таким образом давайте примем Intel 64-разрядный процессор с SSE3.

Спасибо

36

algorithm performance sorting sorting-network

задан VividD 8 April 2019 в 18:33

6 ответов

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

Самый эффективный способ сортировки, например, четырех элементов - это раскрыть алгоритм сортировки до линейных сравнений, тем самым устраняя все накладные расходы:

function sort(i,j,k,l) {
  if (i < j) {
    if (j < k) {
      if (k < l) return [i,j,k,l];
      if (j < l) return [i,j,l,k];
      if (i < l) return [i,l,j,k];
      return [l,i,j,k];
    } else if (i < k) {
      if (j < l) return [i,k,j,l];
      if (k < l) return [i,k,l,j];
      if (i < l) return [i,l,k,j];
      return [l,i,k,j];
    } else {
      if (j < l) return [k,i,j,l];
      if (i < l) return [k,i,l,j];
      if (k < l) return [k,l,i,j];
      return [l,k,i,j];
    }
  } else {
    if (i < k) {
      if (k < l) return [j,i,k,l];
      if (i < l) return [j,i,l,k];
      if (j < l) return [j,l,i,k];
      return [l,j,i,k];
    } else if (j < k) {
      if (i < l) return [j,k,i,l];
      if (k < l) return [j,k,l,i];
      if (j < l) return [j,l,k,i];
      return [l,j,k,i];
    } else {
      if (i < l) return [k,j,i,l];
      if (j < l) return [k,j,l,i];
      if (k < l) return [k,l,j,i];
      return [l,k,j,i];
    }
  }
}

Однако код значительно увеличивается для каждого добавляемого вами дополнительного элемента. Добавление пятого элемента увеличивает размер кода примерно в четыре раза. В восьми элементах это будет примерно 30000 строк, поэтому, хотя он по-прежнему самый эффективный, это большой объем кода, и вам придется написать программу, которая пишет код, чтобы сделать его правильным.

7