Algoritmi di ordinamento sequenziale ottimali a dimensione fissa

Ho lavorato su algoritmi di ordinamento per alcune settimane, ma una delle mie domande non ha ancora una risposta: ci sono ordinamenti di confronto sequenziali ottimali per le collezioni a dimensione fissa e ad accesso casuale? La maggior parte degli algoritmi di ordinamento si adatta alle dimensioni della raccolta, ma conoscere la dimensione della raccolta da ordinare consente di scegliere un algoritmo di ordinamento specifico per questa dimensione. Ad esempio, il seguente algoritmo dovrebbe ordinare tre valori con un numero ottimale di confronti e un numero ottimale di swap o assegnazioni (è C ++, ma dovrebbe essere abbastanza facile da tradurre in qualsiasi lingua):

void sort3(int& x, int& y, int& z)
{    
    if (x < y) {
        if (z < y) {
            if (z < x) {
                int tmp = z;
                z = y;
                y = x;
                x = tmp;
            } else {
                std::swap(y, z);
            }
        }
    } else if (z < y) {
        std::swap(x, z);
    } else if (z < x) {
        int tmp = x;
        x = y;
        y = z;
        z = tmp;
    } else {
        std::swap(x, y);
    }
}

Qualunque sia l'input, questo algoritmo ordinerà tre valori con al massimo 3 confronti e 4 assegnazioni. Potrei sbagliarmi , ma non penso che l'ordinamento di tre valori possa essere fatto con meno confronti e meno assegnazioni rispetto a questo algoritmo. Se è davvero così, questo sarebbe un algoritmo di ordinamento di confronto ottimale per ordinare tre valori.

Sembra che algoritmi di ordinamento ottimali di questo tipo per qualsiasi dimensione potrebbero essere generati grazie ad un algoritmo di permutazione, ma non sono stato in grado di trovare un algoritmo di generazione e scrivere uno non sembra essere banale . Ho provato a trovare algoritmi di ordinamento quasi-ottimali per alcune dimensioni fisse, ma non ho trovato alcun modo semplice per generare tali algoritmi:

• L'ordinamento delle reti sembrava una buona idea, ma eseguivano sempre un numero fisso di confronti e swap, che significa che non si adattano ai dati. Anche reti di ordinamento ottimali di dimensioni superiori a 5 perdono rapidamente la battaglia contro un ordinamento di inserimento semplice per alcuni input.

• Gli algoritmi di ordinamento parallelo e gli ordinamenti di non confronto (spreadsort, radix sort ...) sono interessanti, ma sono interessato a ordinare sequenzialmente piccole raccolte. E queste categorie di algoritmi tendono a nascondere una grande complessità costante, il che significa che sono più adatte per le grandi collezioni.

• Il mio metodo attuale per trovare l'algoritmo di ordinamento più ottimale per ordinare una piccola raccolta di dimensioni fisse è contare il numero di confronti necessari per ordinare tutte le possibili permutazioni di una raccolta di dimensioni N:

  // Fill an array of size N
  std::array<int, N> collection;
  std::iota(std::begin(collection), std::end(collection), 0);
  
  // Count comparisons made by an insertion sort
  cppsort::counting_adapter<
      cppsort::insertion_sorter
  > sorter;
  
  // Total number of comparisons
  std::size_t count = 0;
  
  // For each possible permutation of collection
  do
  {
      auto to_sort = collection;
      // Sort collection, get the number of comparisons made
      count += sorter(to_sort);
  } while (std::next_permutation(std::begin(collection), std::end(collection)));
  

  Questo codice utilizza la mia libreria cpp-sort . L'ho usato perché semplifica il conteggio dei confronti effettuati da un algoritmo di ordinamento, ma potrebbe essere implementato senza di esso o in un'altra lingua. Questo metodo ha però un problema: prende in considerazione solo il numero di confronti e può solo aiutare a trovare l'algoritmo più ottimale tra algoritmi noti , non consente di scrivere generatori di algoritmi di ordinamento.

Questa è stata piuttosto l'introduzione, ma la mia domanda è fondamentalmente la seguente: esistono metodi noti per generare algoritmi di ordinamento di confronto sequenziali per collezioni a dimensione fissa che sono ottimali per quanto riguarda il numero di assegnazioni e / o il numero di confronti eseguiti ?