Алгоритм сортировки с наименьшим количеством операций - PullRequest
Новая
       6

Алгоритм сортировки с наименьшим количеством операций

4 голосов
/ 11 июня 2010

Что такое алгоритм сортировки с наименьшим количеством операций?Мне нужно реализовать его в HLSL как часть эффекта пиксельного шейдера v2.0 для WPF, поэтому он должен иметь действительно небольшое количество операций, учитывая ограничения Pixel Shader.Мне нужно отсортировать 9 значений, а именно текущий пиксель и его соседей.

Ответы [ 2 ]

4 голосов
/ 12 июня 2010

Вы хотите использовать сортировку вставкой или сортировку по Radix. Вот некоторые реализации C ++:

Radix Sort 

void radix (int byte, long N, long *source, long *dest)
{
  long count[256];
  long index[256];
  memset (count, 0, sizeof (count));
  for ( int i=0; i<N; i++ )
    count[((source[i])>>(byte*8))&0xff]++;

  index[0]=0;
  for ( i=1; i<256; i++ )
    index[i]=index[i-1]+count[i-1];
  for ( i=0; i<N; i++ )
    dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
}

Вам нужно позвонить radix() четыре раза, поскольку он работает только на один столбец.

Сортировка вставок 

void insertSort(int a[], int length)
{    
    int i, j, value;
    for(i = 1; i < length; i++)
    {
        value = a[i];
        for (j = i - 1; j >= 0 && a[j] > value; j--)
            a[j + 1] = a[j];
        a[j + 1] = value;
    }
}
2 голосов
/ 11 июня 2010

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

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

Сортировка вставкой :

  • Простая реализация
  • Эффективен для (довольно) небольших наборов данных
  • Адаптивный, т. Е. Эффективный для наборов данных, которые уже существенно отсортированы: сложность по времени составляет O (n + d), гдеd - число инверсий
  • Более эффективно на практике, чем большинство других простых квадратичных алгоритмов, то есть O (n2) алгоритмов, таких как выборочная сортировка или пузырьковая сортировка;лучший случай (почти отсортированный ввод) - O (n)
  • Стабильный, т.е. не меняет относительный порядок элементов с равными ключами
  • На месте, т.е. требует только постоянного количества O(1) дополнительной памяти
  • Online, т.е. может сортировать список по мере его получения.
...