Estou resolvendo um problema e envolve a classificação de 10 números (int32) muito rapidamente. Meu aplicativo precisa classificar 10 números milhões de vezes o mais rápido possível. Estou amostrando um conjunto de dados de bilhões de elementos e sempre que preciso escolher 10 números (simplificados) e ordená-los (e tirar conclusões da lista de 10 elementos).

Atualmente, estou usando a classificação por inserção, mas imagino que poderia implementar um algoritmo de classificação personalizado muito rápido para o meu problema específico de 10 números, que superaria a classificação por inserção.

Alguém tem alguma idéia de como abordar esse problema?

(Seguindo a sugestão do HelloWorld de analisar as redes de classificação.)

Parece que uma rede de 29 comparações / trocas é a maneira mais rápida de fazer uma classificação de 10 entradas. Eu usei a rede descoberta por Waksman em 1969 para este exemplo em Javascript, que deve ser traduzido diretamente para C, pois é apenas uma lista de ifdeclarações, comparações e swaps.

function sortNet10(data) {	// ten-input sorting network by Waksman, 1969
    var swap;
    if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; }
    if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; }
    if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; }
    if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; }
    if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; }
    if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; }
    if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; }
    if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; }
    if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; }
    if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; }
    if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; }
    if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; }
    if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; }
    if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; }
    if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; }
    if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; }
    if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; }
    if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; }
    if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; }
    if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; }
    if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; }
    if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; }
    if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; }
    if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; }
    if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; }
    if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; }
    if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; }
    if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; }
    if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; }
    return(data);
}

alert(sortNet10([5,7,1,8,4,3,6,9,2,0]));

Aqui está uma representação gráfica da rede, dividida em fases independentes. Para aproveitar o processamento paralelo, o agrupamento 5-4-3-4-4-4-3-2 pode ser alterado para um agrupamento 4-4-4-4-4-4-4-3-2.

Quando você lida com esse tamanho fixo, dê uma olhada em Classificação de redes . Esses algoritmos têm um tempo de execução fixo e são independentes de suas entradas. Para o seu caso de uso, você não possui uma sobrecarga que alguns algoritmos de classificação possuem.

A classificação bitônica é uma implementação dessa rede. Este funciona melhor com len (n) <= 32 em uma CPU. Em entradas maiores, você pode pensar em mudar para uma GPU. https://en.wikipedia.org/wiki/Sorting_network

Btw, uma boa página para comparar algoritmos de classificação é esta aqui (embora esteja faltando o bitonic sort.

http://www.sorting-algorithms.com

Use uma rede de classificação que tenha comparações em grupos de 4, para que você possa fazer isso nos registros SIMD. Um par de instruções mínimas / máximas compactadas implementa uma função comparadora compactada. Desculpe, não tenho tempo agora para procurar uma página que lembro de ter visto sobre isso, mas espero que a pesquisa nas redes de classificação SIMD ou SSE aconteça algo.

O x86 SSE possui instruções mínimas e máximas de inteiro de 32 bits para vetores de quatro ints de 32 bits. O AVX2 (Haswell e posterior) tem o mesmo, mas para vetores 256b de 8 polegadas. Também existem instruções de shuffle eficientes.

Se você tiver muitas classificações pequenas independentes, poderá ser possível realizar 4 ou 8 classificações em paralelo usando vetores. Esp. se você estiver escolhendo elementos aleatoriamente (para que os dados a serem classificados não sejam contíguos na memória de qualquer maneira), você pode evitar embaralhar e simplesmente comparar na ordem que precisar. 10 registros para armazenar todos os dados de 4 (AVX2: 8) listas de 10 polegadas ainda deixam 6 registros para espaço vazio.

As redes de classificação vetorial são menos eficientes se você também precisar classificar os dados associados. Nesse caso, a maneira mais eficiente parece ser usar uma comparação compactada para obter uma máscara de quais elementos foram alterados e usar essa máscara para misturar vetores de (referências a) dados associados.

Que tal um tipo de seleção desenrolado e sem ramificação?

#include <iostream>
#include <algorithm>
#include <random>

//return the index of the minimum element in array a
int min(const int * const a) {
  int m = a[0];
  int indx = 0;
  #define TEST(i) (m > a[i]) && (m = a[i], indx = i ); 
  //see http://stackoverflow.com/a/7074042/2140449
  TEST(1);
  TEST(2);
  TEST(3);
  TEST(4);
  TEST(5);
  TEST(6);
  TEST(7);
  TEST(8);
  TEST(9);
  #undef TEST
  return indx;
}

void sort( int * const a ){
  int work[10];
  int indx;
  #define GET(i) indx = min(a); work[i] = a[indx]; a[indx] = 2147483647; 
  //get the minimum, copy it to work and set it at max_int in a
  GET(0);
  GET(1);
  GET(2);
  GET(3);
  GET(4);
  GET(5);
  GET(6);
  GET(7);
  GET(8);
  GET(9);
  #undef GET
  #define COPY(i) a[i] = work[i];
  //copy back to a
  COPY(0);
  COPY(1);
  COPY(2);
  COPY(3);
  COPY(4);
  COPY(5);
  COPY(6);
  COPY(7);
  COPY(8);
  COPY(9);
  #undef COPY
}

int main() {
  //generating and printing a random array
  int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
  std::random_device rd;
  std::mt19937 g(rd());
  std::shuffle( a, a+10, g);
  for (int i = 0; i < 10; i++) {
    std::cout << a[i] << ' ';
  }
  std::cout << std::endl;

  //sorting and printing again
  sort(a);
  for (int i = 0; i < 10; i++) {
    std::cout << a[i] << ' ';
  } 

  return 0;
}

http://coliru.stacked-crooked.com/a/71e18bc4f7fa18c6

As únicas linhas relevantes são as duas primeiras #define.

Ele usa duas listas e verifica novamente a primeira por dez vezes, o que seria um tipo de seleção mal implementado, mas evita ramificações e loops de comprimento variável, o que pode compensar os processadores modernos e um conjunto de dados tão pequeno.

Referência

Comparei a rede de classificação e meu código parece ser mais lento. No entanto, tentei remover o desenrolar e a cópia. Executando este código:

#include <iostream>
#include <algorithm>
#include <random>
#include <chrono>

int min(const int * const a, int i) {
  int m = a[i];
  int indx = i++;
  for ( ; i<10; i++) 
    //see http://stackoverflow.com/a/7074042/2140449
    (m > a[i]) && (m = a[i], indx = i ); 
  return indx;
}

void sort( int * const a ){
  for (int i = 0; i<9; i++)
    std::swap(a[i], a[min(a,i)]); //search only forward
}


void sortNet10(int * const data) {  // ten-input sorting network by Waksman, 1969
    int swap;
    if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; }
    if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; }
    if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; }
    if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; }
    if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; }
    if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; }
    if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; }
    if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; }
    if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; }
    if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; }
    if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; }
    if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; }
    if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; }
    if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; }
    if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; }
    if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; }
    if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; }
    if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; }
    if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; }
    if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; }
    if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; }
    if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; }
    if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; }
    if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; }
    if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; }
    if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; }
    if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; }
    if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; }
    if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; }
}


std::chrono::duration<double> benchmark( void(*func)(int * const), const int seed ) {
  std::mt19937 g(seed);
  int a[10] = {10,11,12,13,14,15,16,17,18,19};
  std::chrono::high_resolution_clock::time_point t1, t2; 
  t1 = std::chrono::high_resolution_clock::now();
  for (long i = 0; i < 1e7; i++) {
    std::shuffle( a, a+10, g);
    func(a);
  }
  t2 = std::chrono::high_resolution_clock::now();
  return std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1);
}

int main() {
  std::random_device rd;
  for (int i = 0; i < 10; i++) {
    const int seed = rd();
    std::cout << "seed = " << seed << std::endl;
    std::cout << "sortNet10: " << benchmark(sortNet10, seed).count() << std::endl;
    std::cout << "sort:      " << benchmark(sort,      seed).count() << std::endl;
  }
  return 0;
}

Estou sempre obtendo melhores resultados para a classificação de seleção sem ramificação em comparação com a rede de classificação.

$ gcc -v
gcc version 5.2.0 (GCC) 
$ g++ -std=c++11 -Ofast sort.cpp && ./a.out
seed = -1727396418
sortNet10: 2.24137
sort:      2.21828
seed = 2003959850
sortNet10: 2.23914
sort:      2.21641
seed = 1994540383
sortNet10: 2.23782
sort:      2.21778
seed = 1258259982
sortNet10: 2.25199
sort:      2.21801
seed = 1821086932
sortNet10: 2.25535
sort:      2.2173
seed = 412262735
sortNet10: 2.24489
sort:      2.21776
seed = 1059795817
sortNet10: 2.29226
sort:      2.21777
seed = -188551272
sortNet10: 2.23803
sort:      2.22996
seed = 1043757247
sortNet10: 2.2503
sort:      2.23604
seed = -268332483
sortNet10: 2.24455
sort:      2.24304

A pergunta não diz que este é algum tipo de aplicativo baseado na Web. A única coisa que chamou minha atenção foi:

Estou amostrando um conjunto de dados de bilhões de elementos e sempre que preciso escolher 10 números (simplificados) e ordená-los (e tirar conclusões da lista de 10 elementos).

Como engenheiro de software e hardware, isso absolutamente grita "FPGA" para mim. Não sei que tipo de conclusões você precisa tirar do conjunto classificado de números ou de onde vêm os dados, mas sei que seria quase trivial processar algo entre cem milhões e um bilhão desses "triagem e classificação". analisar "operações por segundo . Eu fiz o trabalho de sequenciamento de DNA assistido por FPGA no passado. É quase impossível superar o enorme poder de processamento dos FPGAs quando o problema é adequado para esse tipo de solução.

Em algum nível, o único fator limitante se torna a rapidez com que você pode inserir dados em um FPGA e a rapidez com que consegue obtê-los.

Como ponto de referência, projetei um processador de imagem em tempo real de alto desempenho que recebia dados de imagem RGB de 32 bits a uma taxa de cerca de 300 milhões de pixels por segundo. Os dados foram transmitidos através de filtros FIR, multiplicadores de matriz, tabelas de pesquisa, blocos de detecção de arestas espaciais e várias outras operações antes de sair do outro lado. Tudo isso em um FPGA Xilinx Virtex2 relativamente pequeno, com clock interno que varia de 33 MHz a, se bem me lembro, 400 MHz. Ah, sim, ele também teve uma implementação de controlador DDR2 e executou dois bancos de memória DDR2.

Um FPGA pode emitir um tipo de dez números de 32 bits em cada transição de relógio enquanto opera a centenas de MHz. Haveria um pequeno atraso no início da operação, à medida que os dados preenchessem os pipelines de processamento. Depois disso, você poderá obter um resultado por relógio. Ou mais, se o processamento puder ser paralelo através da replicação do pipeline de classificação e análise. A solução, em princípio, é quase trivial.

O ponto é: se o aplicativo não estiver ligado ao PC e o fluxo e o processamento de dados forem "compatíveis" com uma solução FPGA (independente ou como uma placa de coprocessador na máquina), não há como você seguir em frente. ser capaz de superar o nível atingível de desempenho com software escrito em qualquer idioma, independentemente do algoritmo.

EDITAR:

Basta executar uma pesquisa rápida e encontrar um documento que possa ser útil para você. Parece que remonta a 2012. Você pode fazer MUITO melhor desempenho hoje (e até então). Aqui está:

Classificação de redes em FPGAs

Recentemente, escrevi uma pequena classe que usa o algoritmo Bose-Nelson para gerar uma rede de classificação em tempo de compilação.

Pode ser usado para criar uma classificação muito rápida para 10 números.

/**
 * A Functor class to create a sort for fixed sized arrays/containers with a
 * compile time generated Bose-Nelson sorting network.
 * \tparam NumElements  The number of elements in the array or container to sort.
 * \tparam T            The element type.
 * \tparam Compare      A comparator functor class that returns true if lhs < rhs.
 */
template <unsigned NumElements, class Compare = void> class StaticSort
{
    template <class A, class C> struct Swap
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            T t = Compare()(v0, v1) ? v0 : v1; // Min
            v1 = Compare()(v0, v1) ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A> struct Swap <A, void>
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            // Explicitly code out the Min and Max to nudge the compiler
            // to generate branchless code.
            T t = v0 < v1 ? v0 : v1; // Min
            v1 = v0 < v1 ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A, class C, int I, int J, int X, int Y> struct PB
    {
        inline PB(A &a)
        {
            enum { L = X >> 1, M = (X & 1 ? Y : Y + 1) >> 1, IAddL = I + L, XSubL = X - L };
            PB<A, C, I, J, L, M> p0(a);
            PB<A, C, IAddL, J + M, XSubL, Y - M> p1(a);
            PB<A, C, IAddL, J, XSubL, M> p2(a);
        }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 1>
    {
        inline PB(A &a) { Swap<A, C> s(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 2>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J); Swap<A, C> s1(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 2, 1>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J - 1); Swap<A, C> s1(a, I, J - 1); }
    };

    template <class A, class C, int I, int M, bool Stop = false> struct PS
    {
        inline PS(A &a)
        {
            enum { L = M >> 1, IAddL = I + L, MSubL = M - L};
            PS<A, C, I, L, (L <= 1)> ps0(a);
            PS<A, C, IAddL, MSubL, (MSubL <= 1)> ps1(a);
            PB<A, C, I, IAddL, L, MSubL> pb(a);
        }
    };

    template <class A, class C, int I, int M> struct PS <A, C, I, M, true>
    {
        inline PS(A &a) {}
    };

public:
    /**
     * Sorts the array/container arr.
     * \param  arr  The array/container to be sorted.
     */
    template <class Container> inline void operator() (Container &arr) const
    {
        PS<Container, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };

    /**
     * Sorts the array arr.
     * \param  arr  The array to be sorted.
     */
    template <class T> inline void operator() (T *arr) const
    {
        PS<T*, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };
};

#include <iostream>
#include <vector>

int main(int argc, const char * argv[])
{
    enum { NumValues = 10 };

    // Arrays
    {
        int rands[NumValues];
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
    }

    std::cout << "\n";

    // STL Vector
    {
        std::vector<int> rands(NumValues);
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
    }

    return 0;
}

Observe que, em vez de uma if (compare) swapdeclaração, codificamos explicitamente os operadores ternários para min e max. Isso é para ajudar a convencer o compilador a usar código sem ramificação.

Benchmarks

Os seguintes benchmarks são compilados com clang -O3 e executados no meu macbook air de meados de 2012.

Classificando dados aleatórios

Comparando-o com o código do DarioP, aqui está o número de milissegundos necessários para classificar 1 milhão de matrizes int de 32 bits de tamanho 10:

Rede de classificação codificada por código 10: 88,774 ms Classificação por
Bose-Nelson modelada 10: 27,815 ms

Usando essa abordagem de modelo, também podemos gerar redes de classificação no tempo de compilação para outro número de elementos.

Tempo (em milissegundos) para classificar 1 milhão de matrizes de vários tamanhos.
O número de milissegundos para matrizes de tamanho 2, 4, 8 são 1,943, 8,655, 20,246, respectivamente.

Créditos a Glenn Teitelbaum pela classificação de inserção desenrolada.

Aqui estão os relógios médios por classificação para pequenas matrizes de 6 elementos. O código de referência e os exemplos podem ser encontrados nesta pergunta:
Tipo mais rápido de comprimento fixo 6 int array

Direct call to qsort library function       : 326.81
Naive implementation (insertion sort)       : 132.98
Insertion Sort (Daniel Stutzbach)           : 104.04
Insertion Sort Unrolled                     : 99.64
Insertion Sort Unrolled (Glenn Teitelbaum)  : 81.55
Rank Order                                  : 44.01
Rank Order with registers                   : 42.40
Sorting Networks (Daniel Stutzbach)         : 88.06
Sorting Networks (Paul R)                   : 31.64
Sorting Networks 12 with Fast Swap          : 29.68
Sorting Networks 12 reordered Swap          : 28.61
Reordered Sorting Network w/ fast swap      : 24.63
Templated Sorting Network (this class)      : 25.37

Ele executa tão rápido quanto o exemplo mais rápido da pergunta para 6 elementos.

Desempenho para classificar dados classificados

Frequentemente, as matrizes de entrada já podem ser classificadas ou principalmente classificadas.
Nesses casos, a classificação por inserção pode ser uma melhor escolha.

Você pode escolher um algoritmo de classificação apropriado, dependendo dos dados.

O código usado para os benchmarks pode ser encontrado aqui .

Embora uma classificação de rede tenha boas chances de ser rápida em matrizes pequenas, às vezes você não pode superar a classificação de inserção se estiver otimizado adequadamente. Por exemplo, inserção em lote com 2 elementos:

{
    final int a=in[0]<in[1]?in[0]:in[1];
    final int b=in[0]<in[1]?in[1]:in[0];
    in[0]=a;
    in[1]=b;
}
for(int x=2;x<10;x+=2)
{
    final int a=in[x]<in[x+1]?in[x]:in[x+1];
    final int b=in[x]<in[x+1]?in[x+1]:in[x];
    int y= x-1;

    while(y>=0&&in[y]>b)
    {
        in[y+2]= in[y];
        --y;
    }
    in[y+2]=b;
    while(y>=0&&in[y]>a)
    {
        in[y+1]= in[y];
        --y;
    }
    in[y+1]=a;
}

Você pode desenrolar totalmente insertion sort

Para facilitar isso, templates recursivos podem ser usados ​​sem sobrecarga de função. Como já é um template, também intpode ser um templateparâmetro. Isso também torna a criação de tamanhos de matriz de codificação diferentes de 10.

Observe que para classificar int x[10]a chamada é insert_sort<int, 9>::sort(x);porque a classe usa o índice do último item. Isso pode ser resolvido, mas seria mais código para ler.

template <class T, int NUM>
class insert_sort;

template <class T>
class insert_sort<T,0>
// stop template recursion
// sorting 1 item is a no-op
{
public:
    static void place(T *x) {}
    static void sort(T * x) {}
};

template <class T, int NUM>
class insert_sort
// use template recursion to do insertion sort
// NUM is the index of the last item, eg. for x[10] call <9>
{
public:
    static void place(T *x)
    {
        T t1=x[NUM-1];
        T t2=x[NUM];
        if (t1 > t2)
        {
            x[NUM-1]=t2;
            x[NUM]=t1;
            insert_sort<T,NUM-1>::place(x);
        }
    }
    static void sort(T * x)
    {
        insert_sort<T,NUM-1>::sort(x); // sort everything before
        place(x);                    // put this item in
    }
};

Nos meus testes, isso foi mais rápido que os exemplos de rede de classificação.

Por razões semelhantes às que descrevi aqui , as seguintes funções de classificação sort6_iterator()e sort10_iterator_local(), devem ter um bom desempenho, onde a rede de classificação foi retirada daqui :

template<class IterType> 
inline void sort10_iterator(IterType it) 
{
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   auto data##a=*(data+a);
#define DD2(a,b) auto data##a=*(data+a), data##b=*(data+b);
#define CB1(a)   *(data+a)=data##a;
#define CB2(a,b) *(data+a)=data##a;*(data+b)=data##b;
  DD2(1,4) SORT2(1,4) DD2(7,8) SORT2(7,8) DD2(2,3) SORT2(2,3) DD2(5,6) SORT2(5,6) DD2(0,9) SORT2(0,9) 
  SORT2(2,5) SORT2(0,7) SORT2(8,9) SORT2(3,6) 
  SORT2(4,9) SORT2(0,1) 
  SORT2(0,2) CB1(0) SORT2(6,9) CB1(9) SORT2(3,5) SORT2(4,7) SORT2(1,8) 
  SORT2(3,4) SORT2(5,8) SORT2(6,7) SORT2(1,2) 
  SORT2(7,8) CB1(8) SORT2(1,3) CB1(1) SORT2(2,5) SORT2(4,6) 
  SORT2(2,3) CB1(2) SORT2(6,7) CB1(7) SORT2(4,5) 
  SORT2(3,4) CB2(3,4) SORT2(5,6) CB2(5,6) 
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

Para chamar essa função, passei para std::vectoriterador.

Uma ordenação por inserção requer, em média, 29,6 comparações para ordenar 10 entradas com um melhor caso de 9 e um pior de 45 (dada entrada que está na ordem inversa).

Um {9,6,1} shellsort exigirá, em média, 25,5 comparações para classificar 10 entradas. O melhor caso é 14 comparações, o pior é 34 e classificar uma entrada reversa requer 22.

Portanto, o uso do shellsort em vez da inserção por inserção reduz a média de casos em 14%. Embora o melhor caso seja aumentado em 56%, o pior caso é reduzido em 24%, o que é significativo em aplicações em que é importante manter o pior desempenho possível. O caso inverso é reduzido em 51%.

Como você parece familiarizado com a classificação por inserção, pode implementar o algoritmo como uma rede de classificação para {9,6} e, em seguida, aplicar a classificação por inserção ({1}) depois disso:

i[0] with i[9]    // {9}

i[0] with i[6]    // {6}
i[1] with i[7]    // {6}
i[2] with i[8]    // {6}
i[3] with i[9]    // {6}

i[0 ... 9]        // insertion sort