Implementazione dell'algoritmo di ordinamento sicuro più veloce

Question

Trascorro del tempo implementando un algoritmo di quicksort in C#. Dopo aver terminato, ho confrontato la velocità della mia implementazione e il metodo Array.Sort di C#.

Confronto solo la velocità su array int casuali.

Ecco la mia realizzazione:

static void QuickSort(int[] data, int left, int right) 
{ 
    int i = left - 1, 
     j = right; 

    while (true) 
    { 
     int d = data[left]; 
     do i++; while (data[i] < d); 
     do j--; while (data[j] > d); 

     if (i < j) 
     { 
      int tmp = data[i]; 
      data[i] = data[j]; 
      data[j] = tmp; 
     } 
     else 
     { 
      if (left < j) QuickSort(data, left, j); 
      if (++j < right) QuickSort(data, j, right); 
      return; 
     } 
    } 
} 

Performance (durante l'ordinamento un int casuale [] con la lunghezza di 100 milioni):
      - il mio algoritmo: 14.21 secondi
      - Net Array <int.>. Numero: 14,84 secondi

Qualcuno sa come implementare il mio a algoritmo ancora più veloce?
Oppure qualcuno può fornire un'implementazione più veloce (non è necessario essere un quicksort!) Che la mia corsa più veloce?

Nota:
      - si prega di non algoritmi che usano più core/processori per migliorare perrformance
      - unica sorgente C# valido codice

mi metterà alla prova le prestazioni degli algoritmi forniti all'interno di un pochi minuti se sono online.

MODIFICA:
Pensi che l'utilizzo di una rete di ordinamento ideale per le parti che contengono meno di 8 valori migliorerebbe le prestazioni?

Answer 1

Qualcuno sa come implementare l'algoritmo ancora più veloce?

Sono stato in grado di ridurre del 10% il tempo di esecuzione convertendo il codice per utilizzare i puntatori.

public unsafe static void UnsafeQuickSort(int[] data) 
    { 
     fixed (int* pdata = data) 
     { 
      UnsafeQuickSortRecursive(pdata, 0, data.Length - 1); 
     } 
    } 

    private unsafe static void UnsafeQuickSortRecursive(int* data, int left, int right) 
    { 
     int i = left - 1; 
     int j = right; 

     while (true) 
     { 
      int d = data[left]; 
      do i++; while (data[i] < d); 
      do j--; while (data[j] > d); 

      if (i < j) 
      { 
       int tmp = data[i]; 
       data[i] = data[j]; 
       data[j] = tmp; 
      } 
      else 
      { 
       if (left < j) UnsafeQuickSortRecursive(data, left, j); 
       if (++j < right) UnsafeQuickSortRecursive(data, j, right); 
       return; 
      } 
     } 
    } 

Answer 2

L'ordinamento di inserimento binario quasi sempre vince per tirature brevi (~ 10 articoli). Spesso è meglio di una rete di ordinamento ideale a causa della struttura di diramazione semplificata.

Dual pivot quicksort è più veloce di quicksort. Il documento collegato contiene un'implementazione Java che potresti presumibilmente adattare.

Se si stanno solo ordinando numeri interi, un radix sort sarà probabilmente ancora più veloce su array lunghi.

Answer 3

Dai un'occhiata a Ordinamento per ordinamento e ordinamento dispari: http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html e http://home.westman.wave.ca/~rhenry/sort/.

C'è un'implementazione C# di Cesoia Ordina qui: http://www.codeproject.com/KB/recipes/cssorters.aspx.

Gli esempi sono in Java ma è terribilmente vicino a C#. Sono tipi paralleli perché corrono più velocemente su più core, ma dovrebbero comunque essere molto veloci.

Answer 4

Questo primo (e probabilmente il secondo) algoritmo di ordinamento rapido si interrompe quando si ordinano gli array con elementi duplicati. Ho usato uno this, che funziona bene.