Complessità del tempo di ordinazione rapida
Ora, ci sono diversi modi di scrivere le funzioni Pivot () e Partition (). La scelta del tipo di funzione Pivot () e/o partizione () determina l'efficienza dell'intero programma. L'efficienza è come il numero di operazioni principali che vengono eseguite dal programma.
La complessità del tempo è la fase di esecuzione relativa di un programma. Questo può essere visto come il principale funzionamento del programma.
L'ordinamento può essere ascendente o scendendo. In questo articolo, l'ordinamento è ascendente.
Lo scopo di questo articolo è produrre la complessità temporale per un programma QuickSort. Poiché QuickSort può essere scritto in diversi modi a seconda della scelta delle funzioni Pivot () e/o Partition (), ogni tipo di sort-sort ha la sua complessità. Tuttavia, esiste una serie di operazioni in cui si adattano i diversi tipi di programmi QuickSort. Questo articolo presenta solo uno dei diversi tipi di programmi QuickSort. Qualsiasi segmento di codice presentato è della lingua C.
Divisione integer da due
Quick Sords utilizza la divisione integer per dividere il suo set principale in set più piccoli.
Ora,
11/2 = 5 resto 1
Division Integer significa, prendendo 5 e abbandonando 1. Cioè, accetta l'intero numero e ignora il resto.
Anche,
10/2 = 5 resto 0
Qui, il resto è zero e non ha importanza. Tuttavia, Integer Division prende 5 e abbandona 0. Cioè, accetta l'intero numero e ignora qualunque restante sia lì, anche se è zero. A volte nella programmazione, è anche bene sapere se il resto è 0 o no - vedi più tardi.
Quando si dividono un elenco in un punto rapido, la divisione intera è ciò che viene utilizzato.
Per un Ordine rapido, per ottenere l'indice medio basato su zero per un elenco, fai intero divisione di due per la lunghezza dell'elenco. L'intero numero è l'indice medio basato su zero. Per ottenere la lunghezza dell'elenco, inizia a contare da 1.
Complessità temporale relativa al tipo rapido
Considera il seguente codice:
int n = 8;char a [] = 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h';
per (int i = 0; i
printf ("\ n");
L'output è:
A B C D E F G HCioè, tutti e otto gli elementi sono stati stampati.
Ci sono otto elementi identificati da n. Il corpo del per loop ha un contenuto.
printf ("%c", a [i]);Questa è un'operazione principale. Quindi, sono avvenute otto operazioni principali. La complessità del tempo per questo codice è scritta come:
SU)
Dove n è il numero di operazioni principali. Questa è la notazione Big-O. Nella notazione, la prima lettera è O in maiuscolo. Poi ci sono parentesi. All'interno delle parentesi c'è il numero di operazioni o il numero massimo possibile di operazioni.
Ora considera il seguente segmento di codice:
per (int i = 0; i<8; i++)per (int i = 0; i
if (i == 2)
rottura;
printf ("\ n");
L'output è:
a b cIl corpo del per loop ha un contenuto.
printf ("%c", a [i]);if (i == 2)
rottura;
Questa è ancora considerata un'operazione principale in questa situazione. Tre elementi sono stati stampati perché l'operazione principale è stata eseguita tre volte.
Ora,
8 = 23
=> 3 = log2(8)
Se 8 è n, allora 3 è,
tronco d'albero2(N)
E la complessità del tempo sarebbe data come:
O (log2N)
C'è ancora un altro segmento di codice da considerare in relazione alla complessità del tempo di QuickSort. È
per (int i = 0; iprintf ("\ n");
printf ("\ n");
L'output è:
A B C D E F G HA B C D E F G H
A B C D E F G H
A B C D E F G H
A B C D E F G H
A B C D E F G H
A B C D E F G H
A B C D E F G H
Il numero di caratteri stampati è 64, da un numero iniziale di 8. Ciò significa che l'operazione principale è stata eseguita 64 volte.
64 = 8 x 8 = 82
Se 8 è n, allora questo sarebbe n2. La complessità del tempo per questo codice è:
SU2)
Algoritmo di ordinamento rapido in questo articolo
Per questo articolo, i passaggi dell'algoritmo sono:
- Cerca la mediana (vedi sotto) tra il primo elemento, l'elemento centrale e l'ultimo elemento dell'elenco.
- Posizionare la mediana nel mezzo della lista.
- Invia tutti gli elementi a destra che sono inferiori alla mediana, ora nel mezzo, a sinistra della mediana e invia tutti gli elementi a sinistra che sono maggiori della mediana a destra della mediana. Questo si chiama partizionamento.
- Ripeti i tre passaggi precedenti in ordine, per ogni sotto-list, fino a quando l'elenco non è stato separato in singoli elementi.
- Quando l'elenco è costituito da singoli elementi separati, l'elenco viene ordinato.
Mediano
Per ottenere la mediana dei tre elementi,
TAXIriorganizzare i tre elementi in ordine, i.e.
A b cL'elemento medio, b, è la mediana.
Illustrazione di ordinamento rapido
L'elenco da ordinare è:
P V D Q S X T BCi sono otto elementi. Quando l'elenco è stato risolto, sarebbe:
B D P Q S T V XQuindi, il problema è: ordina l'elenco:
P V D Q S X T BUsando QuickSort.
La mediana tra P, Q e B è cercata. È p. Questa ricerca della mediana prevede tre operazioni. Quindi, finora ci sono un totale di tre operazioni. Mettere la mediana nel mezzo dell'elenco dà:
V d q p s x t bRicorda: l'indice per l'elemento centrale è il risultato della divisione interi di due. Ci sono quattro movimenti qui, per p e q. Quelle sono quattro operazioni. Questo fa un totale di sette operazioni finora (tre più quattro). Ora, B verrà inviato a sinistra e V e Q saranno inviati a destra, per avere:
D b p v q s x tSi noti che P non è più al centro. Tuttavia, c'erano tre movimenti. Queste sono tre operazioni. Quindi ci sono dieci operazioni finora (sette più tre). Ciascuno dei due sotto-listi deve essere diviso in tre parti (la mediana è una parte).
La mediana per d e b è d. La ricerca della mediana è tre operazioni. Questo fa un totale di tredici operazioni finora (dieci più tre). Partizionando questi elementi dà:
B dC'erano due movimenti qui. Quelle sono due operazioni. Questo fa un totale di quindici operazioni finora (tredici più due). Successivamente, la mediana per l'insieme v, q, s, x, t deve essere cercata e il set ha partizionato.
La mediana per v, s e t è t. La ricerca mediana è tre operazioni. Finora, ci sono state diciotto operazioni (quindici più tre). Mettere T nel mezzo dà:
V q t s xCi sono tre movimenti qui. Queste sono tre operazioni. Il numero totale di operazioni finora è di ventuno (diciotto più tre). Inviare elementi inferiori a destra di T a sinistra e elementi più alti a sinistra di T a destra, dà:
Q s t v xCi sono due movimenti qui. Queste sono due operazioni. Finora, ci sono un totale di ventitre operazioni (venti anni più due). Mettere insieme tutte le partizioni dà:
B D P Q S T V XSi noti che l'elenco è già risolto. Tuttavia, l'algoritmo deve terminare. Q, s e v, x devono essere seguiti. Non ci sarà alcun movimento di personaggi tra questi due. Tuttavia, la loro mediana sarà guardata. La ricerca di due mediane è sei operazioni. Questo fa un totale di ventinove operazioni per l'intero programma (ventitre più sei). L'elenco ordinato finale è:
B D P Q S T V XNota:
24 = 8 x 3
=> 24 = 8xlog28
29 è approssimativamente uguale a 24.
Conclusione
A seconda del tipo di funzione scelto per Pivot () e del tipo di funzione scelto per la partizione (), la complessità temporale per il programma QuickSort sarà tra un posto tra
SU.tronco d'albero2N)
E
SU2)
inclusivo. Si noti che il punto in O (n.tronco d'albero2n) significa moltiplicazione.