Contare la complessità di ordinamento

Cosa sta contando il tipo?

Il conteggio dell'ordinamento è meglio illustrato con l'ordinamento degli interi. In C/C ++ e Java, i personaggi sono numeri interi e possono essere ordinati nel modo in cui vengono ordinati i numeri interi. Prendi in considerazione il seguente elenco non fatto da numeri interi:

16, 20, 12, 10, 18, 8, 12, 18, 12, 14

Questo elenco è ordinato in ordine crescente. Può essere dato (ricevuto dal programma di ordinamento) come un array. È costituito da numeri positivi maggiori o uguali a 0.

Notare qui che l'intero più alto è 20. Quindi, 20 + 1 = 21, devono essere fornite nuove posizioni di array. L'extra 1 è per la possibilità che uno dei numeri interi da ordinare sia 0. Ricorda che il programma di ordinamento non conosce i numeri da ordinare in anticipo. Quindi, la possibilità di avere 0 dovrebbe essere fatta.

Per ogni indice del nuovo array che corrisponde a un valore nell'elenco indicato, il numero di verificarsi del valore nell'elenco dato è assegnato come valore per quella nuova cella di array. Cioè, il nuovo array è costituito da contatori. Il precedente elenco non orientato è rappresentato come segue:

0	0	0	0	0	0	0	0	1	0	1	0	3	0	1	0	1	0	2	0	1
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

Questa tabella rappresenta un array che è la nuova serie di contatori. In questa fase, ci sono due array: l'array fornito dell'elenco non desiderato e l'array di contatori chiamato Array di conteggio.

Nella tabella, la seconda riga ha gli indici. La prima riga ha i conteggi. Ogni conteggio è il numero di occorrenza dell'indice corrispondente presente come valore nell'elenco non desiderato.

Per gli indici da 0 a 7 (inclusi), il conteggio è 0. Questo perché nessuno di questi indici è un valore nell'elenco non desiderato. L'indice 8 si verifica una volta nell'elenco, quindi il suo conteggio è 1. L'indice 9 si verifica zero volte nell'elenco, quindi il suo conteggio è 0. L'indice 10 avviene una volta nell'elenco, quindi il suo conteggio è 1. L'indice 12 si verifica tre volte nell'elenco, quindi il suo conteggio è 3. L'indice 13 avviene zero volte nell'elenco, quindi il suo conteggio è 0. Questo continua fino a quando l'indice 20 con un conteggio di 1 mentre l'indice 18 ha un conteggio di 2.

L'elenco ordinato è il seguente:

8, 10, 12, 12, 12, 14, 16, 18, 18, 20

Questo può essere ottenuto dall'array di conteggio (nuovo) come segue:

Spostarsi da sinistra a destra, se il valore di un indice è 0, quel valore non è nell'elenco non senza corti (array). Se il valore è 1, digita l'indice una volta. Se il valore è 2, digita due volte l'indice. Se il valore è 3, digita l'indice tre volte. Se il valore è 4, digita l'indice 4 volte e così via. Tutti questi possono essere fatti di nuovo sull'array non desiderato (elenco).

Contare l'algoritmo di ordinamento

• Fornire un array la cui lunghezza è il numero massimo nell'elenco non desiderato, più 1 (per tenere conto di uno possibile 0 nell'elenco). L'indice di questo array è un possibile valore nell'elenco non desiderato.
• Leggi l'array di conteggio da sinistra a destra, quindi digita l'indice il cui valore non è 0 e il numero di volte per il valore della cella dell'indice.

Operazioni

L'algoritmo ha due passaggi. Per l'elenco fornito precedente, il primo passo ha 10 operazioni principali perché il numero di elementi nell'elenco non mobili è 10. Il secondo passo ha 21 operazioni principali perché il valore massimo nell'elenco non desiderato è 20 (l'extra 1 è per un possibile valore 0). Quindi, il numero delle operazioni principali è considerato come segue:

O (10 + 20)

Dove 10 è il numero di elementi nell'elenco non desiderato e 20 è il valore massimo nell'elenco non cortioso. L'Aggiunto da 1 a 20 viene ignorato a questo punto, ma tieni presente che deve essere codificato.

Complessità temporale per il conteggio dell'ordinamento

La complessità del tempo è il numero approssimativo delle operazioni principali per un po 'di codice. La complessità del tempo indica la velocità del codice. La complessità temporale per il conteggio dell'ordinamento è data come segue:

O (n + m)

Dove n è il numero di elementi (lunghezza o dimensione) dell'array non senza prestito, e m è il valore massimo nell'array indicato. L'1 a M aggiunto viene ignorato a questo punto. Il Big-O con le sue parentesi e il contenuto è indicato come Big-O Notation.

Si noti che per ottenere il valore massimo nell'array, alcune operazioni devono verificarsi nel codice. Tuttavia, queste operazioni vengono ignorate quando si citano la complessità del tempo.

L'array di conteggio deve avere tutti i suoi elementi inizialmente realizzati come zero. Tutte queste operazioni vengono anche ignorate quando si citano la complessità del tempo per l'ordinamento del conteggio.

Spazio di memoria

Si noti che nell'array di conteggi precedenti, tutti i conteggi di 0 sono ridondanti. Sebbene i loro spazi siano ridondanti in memoria, devono essere lì. L'ordinamento di conteggio prende in generale lo spazio di memoria in generale. Normalmente non viene fatto nulla per evitare le posizioni ridondanti. Se è possibile noto il valore minimo nell'array non senza prestito, la parte iniziale dell'array di conteggio può essere omesso per ridurre lo spazio. Tuttavia, gli zeri intervallati nell'array di conteggio non possono essere omessi.

Nota: c'è anche complessità dello spazio, ma questo non è affrontato in questo articolo.

Coding in c

Una funzione di ordinamento di conteggio nel linguaggio del computer C è la seguente:

void CountingSort (int arr [], int n)
int max = 0;
per (int i = 0; i max)
max = arr [i];


INT COUNT [MAX+1];
per (int i = 0; i< max+1; i++)
conta [i] = 0;

//N
per (int i = 0; i< n; i++)
count [arr [i]] = count [arr [i]] + 1; // aggiungi 1 per ogni occorrenza

//M
int k = 0; // INDICE PER ARRAY DATO
per (int i = 0; iif (count [i] != 0)
per (int j = 0; jarr [k] = i; // rimettere il valore ordinato in un determinato array
K ++;

Il per anello nidificato e l'input sono i seguenti:

16, 20, 12, 10, 18, 8, 12, 18, 12, 14

In realtà ci sono 24 operazioni principali e non 20. L'operazione extra 3 + 1 = 4 viene ignorata quando si cita la complessità del tempo per l'ordinamento del conteggio.

Una funzione principale C idonea è la seguente:

int main (int argc, char ** argv)

int n = 10;
int arr [] = 16, 20, 12, 10, 18, 8, 12, 18, 12, 14;
conteggioSort (arr, n);
per (int i = 0; iprintf ("%d", arr [i]);
printf ("\ n");
restituzione 0;

L'output è:

8 10 12 12 12 14 16 18 18 20 20

Conclusione

La complessità temporale per l'ordinamento del conteggio è:

O (n + m)

Dove m è generalmente più grande di n, n è il numero di elementi (lunghezza) dell'elenco indortato dato e m è l'elemento massimo nell'elenco non senza cortili dati.