Qual è la differenza tra ordinamento esterno e ordinamento interno? Non vedo come mai i dati di input possono essere memorizzati nella RAM o non ha a che fare con l'algoritmo.Qual è la differenza tra l'ordinamento esterno e l'ordinamento interno?
Nell'ordinamento interno tutti i dati da ordinare vengono memorizzati in memoria in qualsiasi momento mentre è in corso l'ordinamento. Nell'ordinamento esterno i dati vengono archiviati fuori dalla memoria (come su disco) e caricati solo in memoria in piccoli blocchi. L'ordinamento esterno viene solitamente applicato nei casi in cui i dati non possono essere inseriti interamente nella memoria.
Così nell'ordinamento interno puoi fare qualcosa come l'ordinamento della shell: basta accedere a qualsiasi elemento dell'array desiderato nel momento desiderato. Non è possibile farlo nell'ordinamento esterno: l'array non è interamente in memoria, quindi non è possibile accedere in modo casuale a qualsiasi elemento in memoria e accedervi casualmente su disco è in genere estremamente lento. L'algoritmo di ordinamento esterno deve occuparsi di caricare e scaricare blocchi di dati in modo ottimale.
memoria esterna: si ottengono parti dei dati alla volta? – committedandroider
@committedandroider: Sì, perché non è possibile inserire tutti i dati nella memoria disponibile. – sharptooth
http://en.wikipedia.org/wiki/External_sorting –
http://en.wikipedia.org/wiki/Internal_sort –
Se non riesci a vedere la differenza che in memoria o ordinamento out-of-memory ti fa non aver pensato abbastanza a riguardo. Ti suggerisco di scrivere programmi per fare entrambe le cose. Per prima cosa, ordina una lista di interi di lunghezza 100; successivamente ordina una lista di interi che vanno, per esempio, a 4TB. –