La fusione esterna ordina un algoritmo di divisione e conquista? [chiuso]

0

Oggi sono stato corretto per aver menzionato "External Merge Sort" come un esempio di algoritmo divide et impera (D & C) e dopo aver fatto molte ricerche online e nei libri più importanti sugli algoritmi, ho iniziato a rendi conto che External Merge Sort è di solito collocato nelle loro categorie separate e non viene mai definito come un algoritmo di D & C.

Dato che Merge Sort è uno degli esempi più famosi di un algoritmo di D & C, come mai l'External Merge Sort non è considerato D & C algoritmi nella maggior parte dei libri?

    
posta Mike Laren 24.06.2015 - 07:48
fonte

1 risposta

1

Personalmente non conosco il ragionamento alla base di questi libri e non pretendo di avere una visione unica su questo problema.

Tuttavia, l'ordinamento merge esterno può essere implementato esattamente in due fasi, e nessuno dei due stage contiene una suddivisione ricorsiva. In altre parole, in entrambi gli stadi, c'è solo un livello di suddivisione.

Scegli il numero di suddivisione N.

Fase 1: partizionare arbitrariamente i dati di input in N suddivisioni. Ordina all'interno di ciascuna suddivisione.

Fase 2: creare N code FIFO, ciascuna alimentata dalla suddivisione corrispondente nell'ordine ordinato. Eseguire un mergesort N-way (heap binario o ordinamento selezione) sbirciando la testa di ogni coda e rimuovendo l'elemento più piccolo, inviandolo alla coda FIFO di output. Ogni volta che una coda FIFO diventa vuota, si alimenterà dai dati rimanenti dalla suddivisione corrispondente. Le dimensioni delle code FIFO vengono scelte in base alla memoria disponibile, ma l'algoritmo funziona correttamente anche se tutte le code FIFO hanno dimensione 1.

Come spiegato sopra, non esiste una suddivisione ricorsiva del problema.

Questa è solo un'osservazione. Non so se gli autori di libri considerino la suddivisione ricorsiva come una parte fondamentale di D & C.

Esistono molti schemi di ordinamento unione esterni. Quello sopra descritto è solo un esempio. Questi altri schemi potrebbero fare uso della suddivisione ricorsiva. Non ne so molto di quelli quindi non potrò commentare.

    
risposta data 24.06.2015 - 08:53
fonte

Leggi altre domande sui tag