Modo efficiente per ordinare una grande serie di numeri

-5

Devo ordinare un set di 100000 interi come parte di una programmazione Q. Il limite di tempo è piuttosto restrittivo, quindi devo usare l'approccio più efficiente possibile nel tempo.

Il mio codice corrente -

#include<cstdio>
#include<algorithm>
using namespace std;

int main() {
    int n,d[100000],i;
    for(i=0;i<n;++i) {
                     scanf("%d",&d[i]);
    }
    sort(d,d+n);
    ....
}

Questo approccio sarebbe più ef fi cace?

int main() {
    int n,d[100000],i;
    for(i=0;i<n;++i) {
                     scanf("%d",&d[i]);
                     sort(d,d+i+1);
    }
    ....
}

Qual è il modo più efficiente per ordinare un set di dati di grandi dimensioni?

Nota - Non fare i compiti ...

    
posta 7Aces 02.11.2012 - 07:35
fonte

2 risposte

3

Per la massima efficienza, si desidera eseguire l'ordinamento solo una volta, quindi la versione 2 non è assolutamente la strada da percorrere.

Un'alternativa alla semplice memorizzazione dei numeri in una matrice nell'ordine in cui vengono letti e quindi nell'ordinamento, consiste nell'utilizzare una struttura dati che si ordinerà da sola ogni numero, come un albero binario (rosso / nero) o una lista di salto. Ciò richiederà memoria aggiuntiva per i collegamenti puntatore tra gli elementi, ma potrebbe essere più veloce - solo un esperimento può determinarlo.

Tuttavia, l'efficienza di un particolare algoritmo di ordinamento può spesso dipendere molto dall'ordine iniziale degli articoli - ad es. già ordinato / inverso ordinato / casuale.

    
risposta data 02.11.2012 - 09:51
fonte
-1

Se si desidera ordinare in base al tempo ed è garantito che i propri elementi siano numeri, quindi andare per Radix-Sort . Sta ordinando il set di dati in O(a*n) , a è la lunghezza del numero più lungo / più grande. 10 otterresti a = 2, 200 ti otterrebbero a = 3, 2 * 10 ^ (100) ti darebbero un = 1000 e così via.

Quicksort può ordinare in O (log (n) * n) ciò che è buono, ma può succhiare ed essere cattivo come Bubblesort e ordinare il set di dati in Theta (n²).

Puoi dirci quanto tempo hai per ordinarlo, o quanto tempo hai in generale?

    
risposta data 24.12.2015 - 21:26
fonte

Leggi altre domande sui tag