Algoritmo di ordinamento più rapido per ordinare un numero basso di numeri interi

Question

Algoritmo di ordinamento più rapido per ordinare un numero basso di numeri interi

#1 da (7 voti)

4

Sto facendo un programma sul mio tempo libero che voglio correre il più rapidamente possibile. Il programma è scritto in C.

Un ampio set di procedure funziona su puntatori a 7 numeri interi ordinati in base ai loro valori numerici da alto a basso.

Fino a questo punto ho usato la funzione di libreria "qsort" per ordinare i miei interi. Ora, quando ho finito il resto dell'applicazione, voglio sostituire la mia chiamata a qsort con qualcosa di più veloce.

Voglio un algoritmo di ordinamento per ordinare un numero fisso di 7 numeri interi il più velocemente possibile. Per favore dimmi cosa vorresti usare e perché pensi che sia il migliore.

Ho letto della notazione di Big O e da quello che ho scoperto misura solo la durata dell'algoritmo in base al numero di elementi che deve essere ordinato. La notazione di Big O conta davvero quando ho solo bisogno di ordinare 7 elementi? O (n * log n) può essere più veloce di un O (n ^ 2) in questo caso?
"radixsort" sembra una buona scelta per me ma voglio ottenere anche le tue opinioni.

L'algoritmo di ordinamento verrà utilizzato milioni di volte e durante questo periodo l'utente del programma dovrà attendere. Il mio programma è quasi 10 volte più lento da quando ho iniziato a usare qsort (prima di misurarlo con un array hard-coded).

c algorithms optimization big-o sorting

posta wefwefa3 08.11.2014 - 15:06

fonte

1 risposta

Leggi altre domande sui tag c algorithms optimization big-o sorting

Qual è il rischio di mettere online il tuo codice di sviluppo attuale Perché stiamo comunque facendo la stima del software sapendo che è rotto? [duplicare]

score 7 · Accepted Answer

Dai un'occhiata a questa implementazione chiara di ordinare sei numeri interi . Secondo le reti di ordinamento, sono necessari 16 confronti per ordinare 7 numeri interi. Ecco il codice per sette numeri interi:

    static int sort7(int *d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
    SWAP(1, 2);
    SWAP(3, 4);
    SWAP(5, 6);
    SWAP(0, 2);
    SWAP(3, 5);
    SWAP(4, 6);
    SWAP(0, 1);
    SWAP(4, 5);
    SWAP(2, 6);
    SWAP(0, 4);
    SWAP(1, 5);
    SWAP(0, 3);
    SWAP(2, 5);
    SWAP(1, 3);
    SWAP(2, 4);
    SWAP(2, 3);
#undef SWAP
}

Si noti che non ho testato il codice!