¿Cuál es la diferencia entre la clasificación externa y la clasificación interna? No veo cómo los datos de entrada pueden almacenarse en la RAM o no tienen que ver con el algoritmo.¿Cuál es la diferencia entre la clasificación externa y la clasificación interna?
En la ordenación interna, todos los datos a clasificar se almacenan en la memoria en todo momento mientras la clasificación está en progreso. En la clasificación externa, los datos se almacenan fuera de la memoria (como en el disco) y solo se cargan en la memoria en pequeños fragmentos. La clasificación externa se aplica generalmente en los casos en que los datos no pueden caber en la memoria por completo.
Por lo tanto, en la ordenación interna puede hacer algo parecido a la clasificación de shell: solo acceda a los elementos de la matriz que desee en el momento que desee. No puede hacer eso en la clasificación externa: la matriz no está completamente en la memoria, por lo que no puede acceder aleatoriamente a ningún elemento de la memoria y acceder a ella aleatoriamente en el disco suele ser extremadamente lento. El algoritmo de clasificación externo tiene que ocuparse de cargar y descargar trozos de datos de manera óptima.
memoria externa: ¿obtiene partes de los datos a la vez? – committedandroider
@committedandroider: Sí, porque no puede ajustar todos los datos en la memoria disponible. – sharptooth
http://en.wikipedia.org/wiki/External_sorting –
http://en.wikipedia.org/wiki/Internal_sort –
Si no puede ver la diferencia en la clasificación en memoria o sin memoria hace que no hayas pensado lo suficiente sobre el asunto. Te sugiero que escribas programas para hacer ambas cosas. Primero, clasifique una lista de enteros de longitud 100; a continuación, ordena una lista de enteros que se ejecutan en, digamos, 4TB. –