Clasificación externa
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 23 de marzo de 2013; las comprobaciones requieren 2 ediciones .Clasificación externa : clasificación de datos ubicados en dispositivos periféricos y que no caben en la RAM , es decir, cuando es imposible aplicar una de las clasificaciones internas . Vale la pena señalar que la clasificación interna es mucho más eficiente que la clasificación externa, ya que lleva mucho menos tiempo acceder a la RAM que los discos magnéticos , cintas , etc.
La mayoría de las veces, la clasificación externa se usa en DBMS . El concepto principal cuando se utiliza la clasificación externa es el concepto de segmento. Un segmento de longitud es una secuencia de entradas , ,…, en la que todas las entradas están ordenadas por alguna clave. El número máximo de segmentos en el archivo (todos los elementos no están ordenados). El número mínimo de segmentos es 1 (todos los elementos están ordenados).
Por ejemplo, en algún archivo A hay una matriz unidimensional:
12 35 65 0 24 36 3 5 84 90 6 2 30
Dividamos la matriz en segmentos:
12 35 65 | 0 24 36 | 3 5 84 90 | 6 | 2 30
Podemos decir que la matriz en el archivo A consta de 5 segmentos.
Por ejemplo, en algún archivo B hay una matriz unidimensional:
1 2 3 4 5 6 7 8 9 10
Dividamos la matriz en segmentos:
| 1 2 3 4 5 6 7 8 9 10 |
Podemos decir que la matriz en el archivo B consta de 1 segmento.
Por ejemplo, en algún archivo A hay una matriz unidimensional:
20 17 16 14 13 10 9 8 6 4 3 2 0
Dividamos la matriz en segmentos:
| 20 | 17 | 16 | 14 | 13 | 10 | 9 | 8 | 6 | 4 | 3 | 2 | 0 |
Podemos decir que la matriz en el archivo A consta de 13 segmentos.
La idea de la mayoría de los métodos es dividir los datos en una serie de secuencias que encajan en la memoria RAM. A continuación, se aplica uno de los métodos de clasificación internos, después de lo cual se fusionan las secuencias. Cuanto mayor sea la cantidad de RAM, más largas serán las secuencias y, por tanto, menor será su número, lo que aumentará la velocidad de clasificación.
Si la cantidad de RAM es pequeña, puede dividir los datos de origen en varias secuencias y luego usar directamente el procedimiento de combinación.
Métodos básicos de clasificación:
- Clasificación natural (método de combinación natural)
- Clasificación de combinación equilibrada bidireccional
- Clasificación por combinación de n vías.
- Clasificación multifase (Fibonacci)
Literatura
- Richard Forsyth. Pascal para todos = Pascal en el trabajo y el juego. Una introducción a la programación de computadoras en Pascal. - M. : Mashinostroenie, 1986. - 288 p.
- Roberto Sedgwick. Algoritmos fundamentales en C. Fundamentos/Estructuras de datos/Ordenación/Búsqueda. - San Petersburgo. : DiaSoftYUP, 2003. - 672 p. — ISBN 5-93772-081-4 .
- Niklaus Wirth. Algoritmos y estructuras de datos. Nueva versión para Oberón. - M. : DMK Press, 2012. - 272 p. - ISBN 978-5-94074-734-5 .
| Algoritmos de clasificación | |
|---|---|
| Teoría | Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo |
| Intercambio | |
| Elección | |
| inserciones | |
| fusión | |
| sin comparaciones | |
| híbrido | |
| Otro | |
| poco práctico | |