Ordina N numeri in ordine numerico

Question

Dato un intervallo di numeri N es. [Da 1 a 100], ordina i numeri in ordine numerico (es.) Per i numeri da 1 a 100, la ferita di uscita ordinata è 1 10 100 11 12 13. . . 19 2 20 21 ..... 99

Questo è proprio come Radix Sort ma solo che le cifre sono ordinate in ordine inverso rispetto a quello che si farebbe in un normale ordinamento Radix.

Ho cercato di memorizzare tutte le cifre di ciascun numero come elenco collegato per un'operazione più rapida, ma si traduce in una grande complessità dello spazio.

Ho bisogno di un algoritmo di lavoro per la domanda.

Da tutte le risposte, "Conversione in stringhe" è un'opzione, ma non c'è altro modo per farlo? È anche possibile fornire un algoritmo per l'ordinamento delle stringhe come menzionato sopra.

Answer 1

Utilizzare qualsiasi algoritmo di ordinamento che ti piace, ma confrontare i numeri come stringhe, non come numeri. Questo è fondamentalmente ordinamento lexiografico di numeri regolari. Ecco un esempio Gnome sort in C:

#include <stdlib.h> 
#include <string.h> 

void sort(int* array, int length) { 
    int* iter = array; 
    char buf1[12], buf2[12]; 
    while(iter++ < array+length) { 
     if(iter == array || (strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0) { 
      iter++; 
     } else { 
      *iter ^= *(iter+1); 
      *(iter+1) ^= *iter; 
      *iter ^= *(iter+1); 
      iter--; 
     } 
    } 
} 

Naturalmente, questo richiede la funzione non-standard itoa essere presenti in stdlib.h. Un'alternativa più standard sarebbe utilizzare sprintf, ma ciò rende il codice un po 'più disordinato. Probabilmente sarebbe meglio convertire prima l'intero array in stringhe, quindi ordinare, quindi riconvertirlo.

Edit: Per riferimento, il bit rilevante è strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0, che sostituisce *iter >= *(iter-1).

Answer 2

Penso che se si convertono i numeri in stringa, è possibile utilizzare il confronto delle stringhe per ordinarli. puoi usare anny sorting alghorighm per questo.

"1" < "10" < "100" < "11" ...

Answer 3

ho una soluzione ma non esattamente un algoritmo .. Tutto quello che devi fare è converte tutti i numeri in stringhe & ordinali come stringhe ..

Answer 4

Modifica: Ho perso che è un intervallo contiguo. Stando così le cose, tutte le risposte che parlano di ordinare un array sono sbagliate (compresa la tua idea affermata nella domanda che è come un ordinamento digitale), e la risposta di True Soft è giusta.

proprio come Radix Sort, ma solo che le cifre sono ordinati in ordine inverso

Bene avvistati :-) Se effettivamente fare in questo modo, stranamente, si chiama un MSD.

http://en.wikipedia.org/wiki/Radix_sort#Most_significant_digit_radix_sorts

È possibile implementare un modo molto semplice, o con un sacco di alta tecnologia e fanfare. Nella maggior parte dei linguaggi di programmazione, il tuo particolare esempio presenta una leggera difficoltà. L'estrazione di cifre decimali dal formato di archiviazione naturale di un intero non è un'operazione particolarmente veloce. Puoi ignorarlo e vedere quanto tempo impiega (consigliato), oppure puoi aggiungere ancora più fanfare convertendo tutti i numeri in stringhe decimali prima di ordinare.

Ovviamente non è necessario implementarlo come ordinamento digitale: è possibile utilizzare un algoritmo di confronto con un comparatore appropriato. Ad esempio, in C, il seguente è adatto per l'uso con qsort (a meno che non ho scompigliato in su):

int lex_compare(void *a, void *b) { 
    char a_str[12]; // assuming 32bit int 
    char b_str[12]; 
    sprintf(a_str, "%d", *(int*)a); 
    sprintf(b_str, "%d", *(int*)b); 
    return strcmp(a_str,b_str); 
} 

Non

terribilmente efficace, dal momento che fa un sacco di lavoro ripetuto, ma semplice.

Answer 5

Ecco come si può fare con una funzione ricorsiva (il codice è in Java):

void doOperation(List<Integer> list, int prefix, int minimum, int maximum) { 
    for (int i = 0; i <= 9; i++) { 
     int newNumber = prefix * 10 + i; 
     if (newNumber >= minimum && newNumber <= maximum) { 
      list.add(newNumber); 
     } 
     if (newNumber > 0 && newNumber <= maximum) { 
      doOperation(list, newNumber, minimum, maximum); 
     } 
    } 
} 

si chiamano in questo modo:

List<Integer> numberList = new ArrayList<Integer>(); 
int min=1, max =100; 
doOperation(numberList, 0, min, max); 
System.out.println(numberList.toString()); 

---

EDIT:

Ho tradotto il mio codice in C++ here:

#include <stdio.h> 

void doOperation(int list[], int &index, int prefix, int minimum, int maximum) { 
    for (int i = 0; i <= 9; i++) { 
     int newNumber = prefix * 10 + i; 
     if (newNumber >= minimum && newNumber <= maximum) { 
      list[index++] = newNumber; 
     } 
     if (newNumber > 0 && newNumber <= maximum) { 
      doOperation(list, index, newNumber, minimum, maximum); 
     } 
    } 
} 

int main(void) { 
     int min=1, max =100; 
     int* numberList = new int[max-min+1]; 
     int index = 0; 
     doOperation(numberList, index, 0, min, max); 
     printf("["); 
     for(int i=0; i<max-min+1; i++) { 
       printf("%d ", numberList[i]); 
     } 
     printf("]"); 
     return 0; 
} 

Fondamentalmente, l'idea è: per ogni cifra (0-9), la aggiungo all'array se è compresa tra minimum e maximum. Quindi, chiamo la stessa funzione con questa cifra come prefisso. Fa lo stesso: per ogni cifra, lo aggiunge al prefisso (prefix * 10 + i) e se è compreso tra i limiti, lo aggiunge all'array. Si ferma quando newNumber è maggiore del massimo.

Answer 6

Se non si desidera convertirli in stringhe, ma disporre di spazio sufficiente per memorizzare una copia aggiuntiva dell'elenco, si memorizzerebbe la potenza massima di dieci in meno rispetto all'elemento nella copia. Questo è probabilmente il più semplice da fare con un ciclo. Ora chiama l'array originale x e le potenze di dieci .

int findPower(int x) { 
    int y = 1; 
    while (y * 10 < x) { 
     y = y * 10; 
    } 
    return y; 
} 

Si potrebbe anche calcolare direttamente

y = exp10(floor(log10(x))); 

ma ho il sospetto che l'iterazione può essere più veloce conversioni da e in virgola mobile.

Al fine di confrontare i i ° e j TH elementi

bool compare(int i, int j) { 
    if (y[i] < y[j]) { 
    int ti = x[i] * (y[j]/y[i]); 
    if (ti == x[j]) { 
     return (y[i] < y[j]); // the compiler will optimize this 
    } else { 
     return (ti < x[j]); 
    } 
    } else if (y[i] > y[j]) { 
    int tj = x[j] * (y[i]/y[j]); 
    if (x[i] == tj) { 
     return (y[i] < y[j]); // the compiler will optimize this 
    } else { 
     return (x[i] < tj); 
    } 
    } else { 
    return (x[i] < x[j]; 
    } 
} 

Ciò che viene fatto qui è che stiamo moltiplicando il numero più piccolo con la forza appropriata di dieci a rendere i due numeri hanno un ugual numero di cifre, quindi confrontandole. se i due numeri modificati sono uguali, confrontare le lunghezze delle cifre.

Se non si dispone dello spazio per memorizzare gli array y, è possibile calcolarli su ciascun confronto.

In generale, è preferibile utilizzare le routine di conversione di cifre preottimizzate.

Answer 7

Ottimizza il modo in cui si memorizzano i numeri: utilizzare un tipo binary-coded decimal (BCD) che fornisce un accesso semplice a una cifra specifica. Quindi è possibile utilizzare l'algoritmo corrente, che Steve Jessop ha identificato correttamente come most significant digit radix sort.

ho cercato di memorizzare tutte le cifre in ogni numero come una lista concatenata per funzionamento più veloce ma si traduce in una grande complessità Spazio.

Memorizzazione di ogni cifra in uno spazio lista rifiuti collegato in due modi diversi:

1. Una cifra (0-9) richiede solo 4 bit di memoria per memorizzare, ma probabilmente si sta utilizzando ovunque da 8 a 64 bit. Un tipo char o short accetta 8 bit e un int può richiedere fino a 64 bit. Questo sta usando da 2 a 16 volte più memoria rispetto alla soluzione ottimale!
2. Gli elenchi collegati aggiungono ulteriore sovraccarico di memoria non necessario. Per ogni cifra, è necessario un ulteriore 32 a 64 bit per memorizzare l'indirizzo di memoria del collegamento successivo. Di nuovo, questo aumenta la memoria richiesta per cifra da 8X a 16X.

A più memoria efficiente esercizi soluzione BCD cifre contiguo in memoria:

1. BCD utilizza solo 4 bit per cifra.
2. Memorizza le cifre in un blocco di memoria contiguo, come un array. Ciò elimina la necessità di memorizzare gli indirizzi di memoria. Non è necessario l'inserimento di elenchi collegati 'per inserire/eliminare facilmente dal centro. Se hai bisogno della capacità di far crescere i numeri a una lunghezza sconosciuta, ci sono altri tipi di dati astratti che consentono di ridurre il sovraccarico. Ad esempio, un vector.

Un'opzione, se altre operazioni come addizione/moltiplicazione non sono importanti, è allocare memoria sufficiente per memorizzare ciascuna cifra BCD più un terminatore BCD. Il terminatore BCD può essere una qualsiasi combinazione di 4 bit che non viene utilizzata per rappresentare una cifra BCD (come binario 1111). Memorizzare in questo modo renderà più complicate altre operazioni come addizione e moltiplicazione.

Nota questo è molto simile all'idea di convertire in stringhe e di ordinare lessicograficamente quelle stringhe. I numeri interi sono memorizzati internamente come binari (base 2) nel computer. La memorizzazione in BCD è più simile alla base 10 (base 16, in realtà, ma 6 combinazioni sono ignorate) e le stringhe sono come base 256. Le stringhe useranno circa il doppio della memoria, ma ci sono già funzioni efficienti scritte per ordinare le stringhe. Probabilmente i BCD richiedono lo sviluppo di un tipo di BCD personalizzato per le tue esigenze.