Sottolineatura extra spazio MergeSort

4

Sto rivedendo gli algoritmi di base di un libro intitolato Algorithms di Robert Sedgewick, e mi sono imbattuto in un problema in MergeSort che sono, purtroppo, in difficoltà a risolvere. Il problema è sotto:

Sublinear Extra Space. Develop a merge implementation that reduces that extra space requirement to max(M, N/M), based on the following idea: Divide the array into N/M blocks of size M (for simplicity in this description, assume that N is a multiple of M). Then, (i) considering the blocks as items with their first key as the sort key, sort them using selection sort; and (ii) run through the array merging the first block with the second, then the second block with the third, and so forth.

Il problema che ho con il problema è che, in base all'idea che Sedgewick consiglia, il seguente set di matrici non verrà ordinato: {0, 10, 12}, {3, 9, 11}, {5, 8, 13}. L'algoritmo che uso è il seguente:

  1. Dividi l'intero array in sottoschemi di dimensioni M.
  2. Esegui selezione ordinamento su ciascuno dei sottoarray.
  3. Unisci ognuno dei sottoarray usando il metodo raccomandato da Sedgwick in (ii). (È qui che incontro il problema di dove memorizzare i risultati dopo l'unione.)

Questo porta a voler aumentare le dimensioni dello spazio ausiliario necessario per gestire almeno due sottoreti alla volta (per la fusione), ma in base alle specifiche del problema, ciò non è consentito.

Ho anche preso in considerazione l'utilizzo dell'array originale come spazio per un subarray e l'utilizzo dello spazio ausiliario per il secondo subarray. Tuttavia, non posso immaginare una soluzione che non finisca per sovrascrivere le voci del primo sottoarray.

Qualche idea su altri modi in cui ciò può essere fatto?

NOTA: se questo è supposto essere su StackOverflow.com, per favore fammi sapere come posso spostarlo. Ho postato qui perché la domanda era accademica.

    
posta hulkmeister 14.12.2012 - 14:19
fonte

1 risposta

4

Per unire 2 blocchi di dimensioni M hai solo bisogno di M di spazio extra:

Se hai un blocco da i a j e un blocco da j a k devi prima copiare il primo blocco nello spazio aggiuntivo in modo che i a j sia libero di ricevere il blocco array ordinato.

Quindi l'unione viene implementata come:

extra = new array[j-i]
arraycopy(arr,i,extra,0,j-i)//copy from arr to extra
p =0
while i<k
    if(arr[j]<extra[p])
       arr[i++]=arr[j++]
    else
       arr[i++]=extra[p++]
    if(j==k)break;
    if(i==j)break;
end while
arraycopy(extra,p,arr,i,extra.length-p)//copy remaining from extra

puoi notare che i incrementa solo senza j fino a j-i volte, quindi i non è mai maggiore di j

    
risposta data 14.12.2012 - 16:08
fonte

Leggi altre domande sui tag