Progettazione dell'algoritmo per confrontare i tempi intermedi in una gara

Usa quicksort (o l'algoritmo di ordinamento di tua scelta) per ordinare un elenco di indici di array in base ai tempi intermedi corrispondenti. La matrice di indici è un proxy per l'array di tempi intermedi. Non vogliamo cambiare l'ordine dei tempi, ma vogliamo sapere quale sarebbe l'ordine dei tempi se lo ordinassimo.

Array split time: splits[] = {4.2, 3.9, 4.1, 3.8, 3.7}

Iniziamo con una serie di indici: indexes[] = {0, 1, 2, 3, 4}

Ora ordiniamo l'array indexes usando i valori di splits . Qualsiasi algoritmo di ordinamento richiede una funzione di confronto e la nostra è:

compare(i, j) := if splits[i] < splits[j], i is smaller,
                 else if splits[i] > splits[j], i is larger,
                 else they're equal

Quindi, ad esempio, compare(0, 1) dovrebbe restituire i > j perché 4.2 > 3.9 .

Di seguito è riportato un codice C che illustra la soluzione utilizzando un codice abbastanza piccolo. Si basa sulla funzione di libreria standard qsort_r() C, che è una versione di quicksort, ma è possibile utilizzare qualsiasi algoritmo di ordinamento. Un importante dettaglio di implementazione è che la routine qsort_r() ci consente di passare un parametro aggiuntivo fornito alla funzione di confronto; questo ci consente di passare l'array splits alla funzione di confronto.

void sortSplits(float splits[], int index[], int count)
{
    // initialize the index array
    for (int i = 0; i < count; i++) {
        index[i] = i;
    }

    qsort_r(index, count, sizeof(int), splits, compareSplits);
}

int compareSplits(void *thunk, const void *item1, const void *item2)
{
    float *splits = (float*)thunk;
    int i = *(int*)item1;
    int j = *(int*)item2;

    if (splits[i] < splits[j])
        return -1; // less than
    else if (splits[i] > splits[j])
        return 1;  // greater than
    else
        return 0;  // equal
}

Per usare questo codice, chiama sortSplits() che passa nell'array di tempi intermedi, una matrice di ints che è lunga almeno quanto l'array di volte e il numero di volte. Al ritorno, la matrice index conterrà la lista ordinata di indici. In altre parole, se la matrice risultante assomiglia a:

{3, 0, 1, 2}

significa che il tempo parziale all'indice 3 è il più piccolo, seguito dal tempo all'indice 0, seguito dal tempo all'indice 1, seguito dal tempo all'indice 2.

Gli indici qui funzionano davvero come dei puntatori. Potresti anche dire che sono indicatori in un certo senso. In effetti, è possibile implementare esattamente lo stesso algoritmo descritto sopra utilizzando una serie di puntatori al posto della serie di indici che eliminerebbe la necessità di passare l'array splits come parametro separato.

Se non si sta ordinando l'elenco, è necessario eseguire un'iterazione su di esso una volta (meno 1 elemento) per determinare tutte le classificazioni dei valori.

Oppure prova a mantenere un array separato che ordina su insert, quindi fai riferimento al valore (rank) di quella chiave (valore o tempo) quando stampi i tuoi dati.

Farei qualcosa di simile a questo:

• Crea una struttura dati contenente un valore temporale e un valore intero.
• Esegue l'iter sulla matrice originale e crea una seconda matrice delle strutture di dati. Il secondo valore (intero) sarebbe l'indice di volta in volta nell'array originale.
• Ordina il secondo array per volta.
• La posizione di ogni volta nell'array ordinato è il rango. Puoi applicare i ranghi all'array originale utilizzando il valore dell'indice

Per determinare la classifica è necessario ordinare la matrice in una matrice ordinata temporanea. Il modo più semplice a cui posso pensare è creare una struttura dati che contenga sia il tempo che la classifica, ad es. Stile Javascript:

var data = {
    time: 4.66,
    rank: 1
}

Quindi, inizia a creare la tua lista con i dati grezzi convertiti in oggetti dati graduabili:

var times = [];
var tempTimes = [];
var i;
// create from input arr objects and put to times and tempTimes
for (i = 0; i < arr.length(); ++i) {
    var obj = {
      time: arr[i]
    };
    times[i] = obj;
    tempTimes[i] = obj;
}

// sort tempTimes by time, using jQuery
tempTimes.sortElements(function(a, b) {
    return a.time > b.time ? 1 : -1; 
});
// iterate and add ranks to the objects
// since they are now ordered by time
for (i = 0; i < tempTimes.length(); i++ ) {
    tempTimes[i].rank = i;
}

// since times and tempTimes have the same objects
// (by reference), they should all now be updated 
// with the ranks set so use the times array to print 
// out the array with the ranks, since that is still
// in correct original order
printTable(times);

Ciò avverrebbe in modo un po 'diverso in altre lingue, sfruttando i loro idiomi, ma il passaggio fondamentale della creazione di una struttura di dati che contiene sia il tempo che il grado rimane ancora nel complesso. Il flusso di dati di base sarebbe simile allo schema seguente:

list of raw data
   |
   | convert
   v
list of rankable data ---wait for ranks to be set---> output
   |                        ^
   | sort by times          |
   v                        |
list of rankable data       |
sorted by time              |
   |                        |
   | add rank to data       |
   v                        |
list of data ranked --------+
by time