Algoritmo STL __merge_without_buffer?

Question

Dove posso ottenere una descrizione decente di alto livello dell'algoritmo utilizzato in __merge_without_buffer () in C ++ STL? Sto cercando di reimplementare questo codice nel linguaggio di programmazione D, con alcuni miglioramenti. Non riesco a capire cosa stia facendo a livello algoritmico semplicemente leggendo il codice sorgente STL perché ci sono troppi dettagli di basso livello che lo oscurano. Inoltre, non voglio tradurre ciecamente il codice perché, se non funzionasse, non saprei perché e non sarei in grado di aggiungere i miei miglioramenti.

Answer 1

__merge_without_buffer () sta eseguendo un unione sul posto , come il passaggio di unione di un ordinamento di fusione sul posto. Richiede come input due intervalli di dati [first, middle) e [middle, last) che si presume siano già ordinati. I parametri len1 e len2 sono uguali alle lunghezze dei due intervalli di input, vale a dire (primo - medio) e (ultimo - al centro) rispettivamente.

Innanzitutto, seleziona un elemento pivot . Quindi, riorganizza i dati nell'ordine A1 B1 A2 B2 , dove A1 è l'insieme di elementi in [primo, medio) che sono inferiore al pivot, A2 è l'insieme di elementi in [primo, medio) maggiore o uguale al pivot, B1 è l'insieme di elementi in [medio, ultimo) inferiore al perno e B2 è l'insieme di elementi in [medio, ultimo) maggiore di o uguale al perno. Nota che i dati sono originariamente nell'ordine A1 A2 B1 B2 , quindi tutto ciò che dobbiamo fare è trasformare A2 B1 in B1 A2 . Questo è con una chiamata a std :: rotate () , che fa proprio questo.

Ora abbiamo separato gli elementi che sono inferiori al pivot ( A1 e B1 ) da quelli che sono maggiori o uguali al pivot ( A2 e B2 ), quindi ora possiamo unire in modo ricorsivo i due sottogrange A1 A2 e B1 B2 .

Come scegliamo un perno? Nell'implementazione che sto osservando, sceglie l'elemento mediano dal sottogruppo più grande (cioè se [primo, medio) ha più elementi di [medio, ultimo) , sceglie la mediana di [first, middle) ; altrimenti, sceglie la mediana di [middle, last) ). Dal momento che i subrange sono già ordinati, la scelta della mediana è banale. Questa scelta pivot assicura che quando si uniscono in modo ricorsivo i due subrange, ciascun sottoproblema non è più di 3/4 della dimensione del problema attuale, perché nel caso peggiore, almeno 1/4 degli elementi sono più grandi o più piccoli del perno .

Qual è il tempo di esecuzione di questo? La chiamata std :: rotate () richiede tempo O (N) e facciamo due chiamate ricorsive a noi stessi. Ciò equivale a un tempo di esecuzione di O (N log N). Tuttavia, tieni presente che questo è solo un passo in mergesort: ricorda che in mergesort devi prima ordinare in modo ricorsivo entrambe le metà e poi unire. Pertanto, la relazione di ricorrenza per il tempo di esecuzione di mergesort è ora:

T (N) = 2T (N / 2) + O (N log N)

Collegalo al Teorema principale , e ottieni che il mergesort ora gira su O (N log ² N) ora!

Come interessante punto finale, considera le seguenti tre qualità di un algoritmo di ordinamento basato sul confronto:

1. In-luogo
2. stabile
3. Esegue nel tempo O (N log N)

Di solito puoi ottenerne solo 2 alla volta: quicksort ti ottiene (1) e (3), mergesort ti riceve (2) e (3) e un mergesort sul posto ti ottiene (1) e (2 ). Gli ordinamenti non basati sul confronto come l'ordinamento conteggio possono ottenere tutti e 3, ma tali ordinamenti possono ordinare solo determinati tipi di dati. È possibile che esista un ordinamento basato sul confronto che raggiunge tutti e 3, ma se esiste, non sono consapevole della sua esistenza ed è quasi certamente molto più complicato.