Estructura de Datos
Introducción
La programación es el proceso utilizado para
idear y ordenar las acciones necesarias para realizar un proyecto, preparar
ciertas máquinas o aparatos para que empiecen a funcionar en el momento y en la
forma deseados o elaborar programas para su empleo en computadoras.
En
la actualidad, la noción de programación se encuentra muy asociada a la
creación de aplicaciones informática y videojuegos. Es el proceso por el cual
una persona desarrolla un programa valiéndose de una herramienta que le permita
escribir el código (el cual puede estar en uno o varios lenguajes, como C++,
Java y Python, entre otros) y de otra que sea capaz de “traducirlo” a lo que se
conoce como lenguaje de máquina, que puede comprender el microprocesador
Estructura de datos
En
ciencias de la computación, una estructura de datos es una forma particular de
organizar datos en una computadora para que puedan ser utilizados de manera
eficiente. Diferentes tipos de estructuras de datos son adecuados para diferentes
tipos de aplicaciones, y algunos son altamente especializados para tareas
específicas.
Las
estructuras de datos son un medio para manejar grandes cantidades de datos de
manera eficiente para usos tales como grandes bases de datos y servicios de
indización de Internet. Por lo general, las estructuras de datos eficientes son
clave para diseñar algoritmos eficientes. Algunos métodos formales de diseño y
lenguajes de programación destacan las estructuras de datos, en lugar de los
algoritmos, como el factor clave de organización en el diseño de software.
es
una serie de elementos en un orden específico, por lo general todos del mismo
tipo (si bien los elementos pueden ser de casi cualquier tipo). Se accede a los
elementos utilizando un entero como índice para especificar el elemento que se
requiere. Las implementaciones típicas asignan palabras de memoria contiguas a
los elementos de los arreglos (aunque no siempre es el caso). Los arreglos
pueden cambiar de tamaño o tener una longitud fija.
Un vector asociativo
(también llamado diccionario o mapa) es una
variante más flexible que una matriz, en la que se puede añadir y eliminar
libremente pares nombre-valor. Una tabla de hash es una implementación usual de
un arreglo asociativo.
Un registro
(también
llamado tupla o estructura) es una estructura de datos agregados. Un registro
es un valor que contiene otros valores, típicamente en un número fijo y la
secuencia y por lo general un índice por nombres. Los elementos de los
registros generalmente son llamados campos o celdas.
Una unión
es una estructura de datos que especifica cuál
de una serie de tipos de datos permitidos podrá ser almacenada en sus
instancias, por ejemplo flotante o entero largo. En contraste con un registro,
que se podría definir para contener un flotante y un entero largo, en una
unión, sólo hay un valor a la vez. Se asigna suficiente espacio para contener
el tipo de datos de cualquiera de los miembros.
Un tipo variante
(también
llamado registro variante o unión discriminada) contiene un campo adicional que
indica su tipo actual.
es
un tipo de datos abstracto que puede almacenar valores específicos, sin orden
particular y sin valores duplicados.
es
un tipo de datos abstracto que puede almacenar valores específicos, sin orden
particular. A diferencia de los conjuntos, los multiconjuntos admiten
repeticiones.
Un grafo
es
una estructura de datos conectada compuesta por nodos. Cada nodo contiene un
valor y una o más referencias a otros nodos. Los grafos pueden utilizarse para
representar redes, dado que los nodos pueden referenciarse entre ellos. Las
conexiones entre nodos pueden tener dirección, es decir un nodo de partida y
uno de llegada.
Un árbol
es
un caso particular de grafo dirigido en el que no se admiten ciclos y existe un
camino desde un nodo llamado raíz hasta cada uno de los otros nodos. Una
colección de árboles es llamada un bosque.
Una clase
es
una plantilla para la creación de objetos de datos según un modelo predefinido.
Las clases se utilizan como representación abstracta de conceptos, incluyen
campos como los registros y operaciones que pueden consultar el valor de los
campos o cambiar sus valores.
Soporte en los lenguajes
La
mayoría de los lenguajes ensambladores y algunos lenguajes de bajo nivel, tales
como BCPL, carecen de soporte de estructuras de datos. En cambio, muchos
lenguajes de alto nivel y algunos lenguajes ensambladores de alto nivel, tales
como MASM, tienen algún tipo de soporte incorporado para ciertas estructuras de
datos, tales como los registros y arreglos. Por ejemplo, los lenguajes C y
Pascal soportan estructuras y registros, respectivamente, además de arreglos y
matrices multidimensionales. La mayoría de los lenguajes de programación
disponen de algún tipo de biblioteca o mecanismo que permita el uso de
estructuras de datos en los programas. Los lenguajes modernos por lo general
vienen con bibliotecas estándar que implementan las estructuras de datos más comunes.
Ejemplos de ello son la biblioteca Standard Template Library de C++, las
colecciones de Java3 y las bibliotecas .NET de Microsoft.
Estructuras de datos en programación
En
programación, una estructura de datos puede ser declarada inicialmente
escribiendo una palabra reservada, luego un identificador para la estructura y
un nombre para cada uno de sus miembros, sin olvidar los tipos de datos que
estos representan. Generalmente, cada miembro se separa con algún tipo de operador,
carácter o palabra reservada.
En
el lenguaje de programación Pascal, es posible crear una estructura de datos de
la forma mencionada. La sintaxis básica es:
Estruct Identificador, _
Miembro1:TipoDeDato, _
Miembro2:TipoDeDato, _
...
Miembro9:TipoDeDato
Para acceder a los miembros de una
estructura, primero se debe crear una referencia a esta, generalmente con una
variable de tipo; luego se pueden editar y obtener los datos de los miembros libremente.
Estruc
Estructura,Miembro1:Entero,Miembro2:Cadena,Miembro3:Byte
Var Variable:Estructura
Variable.Miembro1 = 40000
Variable.Miembro2 = "Hola Mundo"
Variable.Miembro3 = 255
Mensaje(Variable.Miembro2) ' Muestra
"Hola Mundo"
Arreglos de una y dos dimensiones.
Cuando
hablamos de variables podemos imaginarlas como una caja para guardar cosas, una
caja que tiene una etiqueta en la que podemos indicar que esta guardado dentro.
etiqueta
= valor
Dependiendo
del lenguaje que estemos usando, en esa caja solo podremos guardar un tipo
específico de informacion números enteros, números flotantes, cadenas de
caracteres, un solo carácter. O sera una caja multipropósito que nos permitirá
guardar cualquier tipo de información en ella.
¿Pero
qué ocurre cuando necesitamos guardar más de un dato de la misma índole?
Imaginemos
que estamos haciendo un algoritmo para generar el listado de los asistentes a
nuestra fiesta de cumpleaños. El algoritmo solicitará el nombre de las personas
y luego al finalizar imprimirá el listado. Supongamos que sólo deseamos invitar
a 5 amigos.
|
Inicio Fin |
Como
en una variable es posible guardar un solo dato, esto nos obliga a tener una
variable por cada invitado que queremos que venga a nuestra fiesta.
¿Pero
qué ocurre si queremos invitar a más personas?
Tendremos
que agregar mas variables y agregar las lineas correspondientes para leer el
valor del nuevo invitado y luego imprimir su nombre.
Quien
use nuestro algoritmo no percibirá diferencia alguna, pero para nosotros que
debemos darle mantenimiento empezará a ser una pesadilla a medida que se
necesite agregar más personas.
Arreglos de una dimensión
Para
estos casos contamos con una estructura de datos llamada arreglo o vector, que
nos permite agrupar bajo una misma etiqueta un conjunto de datos. Podemos
imaginarlos como una caja grande dividida en compartimientos iguales. Al
crearla debemos suministrar la cantidad de compartimientos que deseamos que
tenga nuestra caja.
etiqueta_arreglo[cantidad]
Cuando
queremos guardar algo en nuestro arreglo debemos guardarlo en alguna de las
cajas.
|
invitados[5] invitados[0]
= "Cosme Fulanito" |
En
la primera línea crea nuestro conjunto de cajas, la segunda guarda dentro de la
primera caja la información del nombre. El número que está encerrado entre
corchetes al crear la variable es la cantidad de cajas que deseamos que tenga.
Luego al interactuar con el arreglo el número entre los corchetes representa la
caja dentro del arreglo a la que estamos haciendo referencia. Este valor es
llamado índice.
Ahora,
reescrito nuestro algoritmo queda de la siguiente forma:
|
Inicio |
Ahora
no importa cuántos invitados nos pidan, con hacer unos cambios menores podremos
satisfacer el requerimiento.
La
primera línea luego del inicio es la “creación” del arreglo. Su igualación a la
cadena vacía es una forma de indicar que estamos iniciando todos los valores
del arreglo a una cadena vacía. Las sintaxis para hacer esto varían de lenguaje
en lenguaje, así que para estos artículos yo escogí esta forma de hacerlo. El
ciclo nos permite llenar el arreglo de forma ordenada es decir, la primera
caja, luego la segunda, la tercera y asi sucesivamente hasta completar todas. Nótese
que la instrucción leer contiene el nombre del arreglo y como como índice la
variable contador del ciclo, lo que permite guardar en cada vuelta el nuevo
dato en cajas contiguas.
Luego
para mostrar los datos volvemos a hacer uso de un ciclo e imprimimos el valor
de la caja correspondiente al valor que posea el contador en ese momento.
¿Cómo
hacemos para guardar datos de distinto tipo para un grupo grande de
informacion?
Imaginemos
por ejemplo que queremos hacer un listado de nuestros amigos y su teléfono y
dirección, pero tenemos la limitante de poder guardar solo un tipo de dato en
un arreglo.
¡Podemos
usar varios arreglos y usarlos en paralelo!
Veamos:
|
Inicio |
Como puede observarse en el apartado de
la carga de datos, guardamos todos los datos de una persona con el mismo índice
en los tres arreglos. Así el nombre, el teléfono y la dirección de índice 3 le
pertenecen a la misma persona
Arreglos de dos dimensiones
Pero ahora. ¿Que pasa si
queremos guardar más de un teléfono o mas de una dirección? Volvemos al mismo
dilema anterior, el crear arreglos de tipo telefono1, telefono2 o direccion1,
direccion2 escala hasta cierto nivel.
Bueno, para esto también
tenemos opción, se llaman arreglos de dos dimensiones o matrices.
Tomemos nuevamente nuestro
ejemplo anterior y decidamos que guardaremos 2 teléfonos por persona y 2
direcciones.
|
Inicio |
Obsérvese
que ahora además del ciclo que nos permite avanzar en las personas que vamos a
guardar, tenemos un ciclo adicional para el telefono y asi poder guardar los
dos telefonos que queremos por persona, y repetimos la estrategia para guardar
las direcciones. Asi para cada persona nos preguntara, dos telefonos y dos
direcciones.
Luego
para mostrar la informacion volvemos a hacer uso de la misma estrategia, un
ciclo para movernos en las personas y dos pequeños ciclos, uno para imprimir
los teléfonos y otro para imprimir las direcciones.
|
variable[indice]
= valor |
La nomenclatura tambien cambia ahora en lugar de tener Tenemos
variable[indice1][indice2] = valor |
En
el caso de nuestro ejemplo especifico seria:
|
telefon[persona][orden_telefono] |
El
primer índice corresponde a la posición de la persona en el listado y el
segundo al orden de los teléfonos, primer teléfono introducido o segundo
teléfono introducido.
Pero
con los arreglos de dos dimensiones podemos hacer mucho mas, por ejemplo
podemos guardar los datos ventas de x cantidad de vendedores durante los 12
meses del año para ello creariamos una matriz como la siguiente:
|
ventas[vendedor][meses] |
||
|
Ahora para hacerlo un ejemplo tenemos: Inicio |
|
En
este ejemplo recorrimos la matriz de dos formas distintas, la primera fila a
fila, es decir para cada vendedor, sumando las ventas de cada mes y dar el
total y poder calcular también el promedio dividiendo todo lo vendido durante
el año por un vendedor entre los meses del año.
La
segunda forma fue columna a columna, sumando todo lo vendido por cada vendedor
en un mes específico y calculando el total y el promedio de ventas de los
vendedores en ese mes.
Nótese
como los ciclos permanecen igual, i el más externo, j el más interno pero en la
variable de la matriz se usan distinto, obviamente los límites también cambian.
ARREGLOS DE MÁS DE DOS DIMENSIONES
Para
algunas aplicaciones se requieren arreglos de más de dos dimensiones. En esta
lección se consideran sólo arreglos de tres dimensiones, ya que sólo unas
cuantas aplicaciones especializadas requieren arreglos de mayor dimensión. La
forma más fácil de imaginar un arreglo de tres dimensiones es dibujar un cubo.
Piense en un arreglo de tres dimensiones como la combinación de algunos
arreglos de dos dimensiones para formar una tercera dimensión, profundidad. El
cubo se hace de filas (dimensión vertical), columnas (dimensión horizontal) y
planos (dimensión de profundidad) De esta manera, se localiza un elemento dado
dentro de un arreglo de cubo especificando su plano, fila y columna.
Ahora,
veamos un ejemplo práctico de un arreglo de tres dimensiones para que sea
posible observar cómo se define y se acceda en C++. Piense en estas lecciones
como un arreglo en tres dimensiones, donde cada página de las lecciones es un
arreglo bidimensional compuesto de filas y columnas. Entonces las páginas
combinadas forman los planos dentro de un arreglo de tres dimensiones que conforman las lecciones.
Después suponga que existen 45 líneas en cada página que forman las filas para
el arreglo y 80 caracteres por fila que forman las columnas del arreglo.
Si
existen 750 páginas en las lecciones, existen 750 planos en el arreglo. De esta
manera, este arreglo de las lecciones es un arreglo de 45 × 80 × 750. ¿Cuáles
son los elementos del arreglo y cuántos hay? Bueno, los elementos del arreglo
serán caracteres, ya que éstos forman las palabras en una página. Además
existirán 45 × 80 × 750 = 2, 700,000 caracteres, incluyendo espacios en blanco,
porque éste es el tamaño de las lecciones en términos de filas, columnas y
páginas. ¿Cómo se definirá el arreglo lecciones en C++? ¿Qué opina de esta
forma?
|
const
int PAGINAS = 750; const
int FILAS = 45; const
int COLUMNAS = 80; char
lecciones[PAGINAS][FILASI[COLUMNASI; |
Es
posible comprender esta definición a partir de su trabajo con arreglos de una y
dos dimensiones. Existen tres dimensiones [PAGINAS], [FILAS] y [COLUMNAS] que
definen el tamaño del arreglo lecciones. Un arreglo de tres dimensiones en C y
C++ se ordena con el plano principal. Esto es porque primero se especifica el
tamaño del plano, seguido por el tamaño del renglón, seguido por el tamaño de columna.
La clase de datos del arreglo es char, ya que los elementos son caracteres.
Después,
¿cómo supone que se acceda a la información del arreglo lecciones? La forma más
fácil es utilizar ciclos anidados. ¿Cómo deberán anidarse los ciclos? Ya que el
arreglo está ordenado por el plano principal, el ciclo página deberá ser el
ciclo externo, y el ciclo columna, el ciclo interno. Esto deja que el ciclo
fila se inserte entre los ciclos página y columna. Traduciendo esto al arreglo
lecciones, se obtiene:
|
for
(int pagina = 0; pagina < PAGINAS; ++pagina) for
(int fila = 0; fila < FILAS; ++fila) for
(int columna = 0; columna < COLUMNAS; ++columna) <proceso
lecciones[pagina][fila][columna]> |
Con
este enfoque de anidamiento, se ejecuta 80 veces el ciclo columna por cada
iteración
del ciclo fila, que se ejecuta 45 veces por cada iteración del ciclo pagina.
Desde luego, el ciclo pagina se ejecuta 750 veces. Esta estructura for
procesará elementos una fila a la vez para una página dada. Observe la
utilización de las variables pagina, fila, y columna como los contadores de
ciclo. Aquéllas deberán ser diferentes de las constantes (PAGINAS, FILAS,
COLUMNAS) que se utilizan para definir el arreglo, ya que éstas son locales
para los ciclos for.
PRECAUCIÓN
Cuando se define un arreglo, C++ reserva suficiente
memoria primaria para almacenarlo. Ésta es exclusiva para el arreglo definido y
no es posible utilizarlo para otras tareas de programación o del sistema. En
otras palabras, un arreglo grande consume mucha memoria. Por ejemplo, el
arreglo lección, contiene 2,700,000 caracteres elemento. Cada uno de éstos
requiere un byte de memoria para almacenarse, por lo tanto C++ asignará casi
2,637 Kbytes de memoria de usuario para el arreglo lecciones. Esto es mucho más
de lo que está disponible en algunos sistemas PC y podrá enviar un mensaje de
error array size too big durante la compilación. Por lo tanto, cerciórese de
que sus arreglos no sean demasiado grandes para almacenarlos en su sistema.
Existen otras formas más eficientes del uso de la memoria para almacenar
grandes cantidades de datos -una lista vinculada dinámica.
Características de un arreglo
tridimensional
1. Tienen filas y columnas, por lo tanto
cuenta con dos indices. Generalmente se maneja el concepto de [Fila][Columna],
aunque podria ser tambien [Columna][Fila].
2.
La relacion entre valores se da por los indices.
3.
Los arreglo unidimensionales se ordenan en fila, en cambio los
multidimensionales se pueden acomodar en columnas dadas por lo indices.
4.
En el anterior ejemplo usamos 5 arreglos que muestra una tabla o una matriz de
4×4, con los arreglos multidimensionales podriamos usar 1 solo arreglo del
mismo tamaño (4×4).
5.
El recorrido de filas y columnas se hace por medio de ciclos, esta a nuestra
eleccion el primer recorrido que deseemos hacer, podriamos recorrer primero la
columna que la fila, o recorrer desde determinado índice.
Matriz poco densa regular
Una matriz poco densa es aquella que
está formada por elementos que en su mayoría son ceros.
Este tipo de matrices son matrices cuadradas que se dividen en los siguientes
tipos:
·
Matriz triangular superior
·
Matriz triangular inferior
·
Matriz tridiagonal
Matriz triangular superior
En este tipo de matriz los elementos iguales a cero se
encuentran debajo de la diagonal principal. Ejemplo:
Para evitar el desperdicio de memoria que se ocasionaría al almacenar
una matriz en donde la mayoría de los elementos son ceros, es
conveniente traspasar a un arreglo unidimensional todos los elementos
diferentes de cero.
El arreglo con los elementos distintos de cero de
la matriz anterior es el siguiente:
Una vez que hallamos vaciado la matriz es
indispensable conocer el lugar dentro del arreglo unidimensional en el cual
quedaron situados los elementos, y esto se logra con la siguiente formula:
LOC(A[i,j])=base(A) + (n*(i-1)) – ((i-2)*(i-1))/2 + (j-1)
donde:
A=Matríz triangular superior
n=No. total de elementos
j= renglones
i=columnas
Matriz triangular inferior
En este tipo de matrices los elementos iguales a cero se encuentran por
encima de la diagonal principal. Ejemplo:
Una vez que vaciamos la matriz en un arreglo unidimensional,
la formula para obtener las posiciones de los elementos es la siguiente:
LOC(A[i,j])=base(A) + ((i-1)*i)/2 + (j-1)
Matriz tridiagonal
En ésta, los elementos diferentes de cero se encuentran en la diagonal
principal ó en las diagonales por debajo ó encima de ésta. Ejemplo:
Y el arreglo con los elementos diferentes de cero correspondiente a
esta matriz es el siguiente:
La localización de los elementos distintos de cero en el arreglo
unidimensional se realiza aplicando la siguiente formula:
LOC(A[i,j])=base(A) + 2*i + (j-3)
Matrices irregulares
Java nos permite crear matrices irregulares. Se dice que
una matriz es irregular si la cantidad de elementos de cada fila varía. Luego
podemos imaginar una matriz irregular:
Como
podemos ver la fila cero tiene reservado dos espacios, la fila uno reserva
cuatro espacios y la última fila reserva espacio para tres componentes.
Para crear la matriz irregular del gráfico:
La declaración es la misma que para matrices regulares:
int
[][] mat;
Primero creamos la cantidad de filas dejando vacío el
espacio que indica la cantidad de columnas:
mat=new
int[3][];
Luego debemos ir creando
cada fila de la matriz indicando la cantidad de elementos de la respectiva
fila:
mat[0]=new
int[2];
mat[1]=new
int[4];
mat[2]=new
int[3];
Luego la forma para acceder a sus componentes es
similar a las matrices regulares, siempre teniendo en cuenta y validando que
exista dicha componente:
mat[0][0]=120;
Dará un error si queremos
cargar la tercera componente de la fila cero (esto debido a que no existe):
mat[0][2]=230;
Luego si queremos saber la
cantidad de filas que tiene la matriz:
Sytem.out.println(mat.length);
Si queremos saber la cantidad de elementos
de una determinada fila:
Sytem.out.println("Cantidad
de elementos de la fila 0:"+mat[0].length);
Sytem.out.println("Cantidad
de elementos de la fila 1:"+mat[1].length);
Sytem.out.println("Cantidad
de elementos de la fila 2:"+mat[2].length);
Problema 1:
Confeccionaremos un programa que permita crear una
matriz irregular y luego imprimir la matriz en forma completa.
import
java.util.Scanner;
public
class MatrizIrregular1 {
private Scanner teclado;
private int[][] mat;
public void cargar() {
teclado=new Scanner(System.in);
System.out.print("Cuantas fila
tiene la matriz:");
int filas=teclado.nextInt();
mat=new int[filas][];
for(int f=0;f<mat.length;f++) {
System.out.print("Cuantas
elementos tiene la fila " + f + ":");
int elementos=teclado.nextInt();
mat[f]=new int[elementos];
for(int c=0;c<mat[f].length;c++)
{
System.out.print("Ingrese
componente:");
mat[f][c]=teclado.nextInt();
}
}
}
public void imprimir() {
for(int f=0;f<mat.length;f++) {
for(int c=0;c<mat[f].length;c++)
{
System.out.print(mat[f][c]+" ");
}
System.out.println();
}
}
public static void main(String[] ar) {
MatrizIrregular1 ma=new
MatrizIrregular1();
ma.cargar();
ma.imprimir();
}
}
Primero creamos la
cantidad de filas que tendrá la matriz (en los corchetes para las columnas no
disponemos valor):
System.out.print("Cuantas fila
tiene la matriz:");
int filas=teclado.nextInt();
mat=new int[filas][];
Dentro del primer for pedimos que ingrese la cantidad
de elementos que tendrá cada fila y utilizamos el operador new nuevamente, pero
en este caso se están creando cada fila de la matriz (Java trata a cada fila
como un vector):
for(int f=0;f<mat.length;f++) {
System.out.print("Cuantas
elementos tiene la fila " + f + ":");
int elementos=teclado.nextInt();
mat[f]=new int[elementos];
Dentro del for interno hacemos la carga de las
componentes propiamente dicho de la matriz (podemos ir cargando cada fila a
medida que las vamos creando):
for(int c=0;c<mat[f].length;c++)
{
System.out.print("Ingrese
componente:");
mat[f][c]=teclado.nextInt();
}
Luego
imprimimos la matriz en forma completa teniendo cuidado las condiciones que
disponemos en cada for.
El primer for se repite tantas veces como filas tiene la matriz:
f<mat.length y
el for interno se repite tantas veces como elementos tiene la fila que estamos
procesando
c<mat
[f].length:
for(int f=0;f<mat.length;f++) {
for(int c=0;c<mat[f].length;c++)
{
System.out.print(mat[f][c]+" ");
}
System.out.println();
}
Ordenación
Un
diagrama de árbol o metodo de Ordenamiento es una herramienta que se utiliza
para determinar todos los posibles
resultados de un experimento aleatorio. En el cálculo de la probabilidad se
requiere conocer el número de elementos que forman parte del espacio muestral,
estos se pueden determinar con la construcción del diagrama de árbol.
El
diagrama de árbol es una representación gráfica de los posibles resultados del
experimento, el cual consta una serie de pasos, donde cada uno de los pasos
tiene un número finito de maneras de ser llevado a cabo. Se utiliza en los
problemas de conteo y probabilidad.
Ordenamiento
por Burbuja
La
idea básica de este método de ordenamiento es la de comparar pares de valores
de llaves e intercambiarlos si no están en sus posiciones relativas correctas.
Como
los métodos de selección e inserción vistos anteriormente, el método de burbuja
requiere O(n^2) comparaciones. No obstante, el método de la burbuja es
frecuentemente usado.
La
idea de este método es la de permitir que cada llave flote a su posición adecuada
a través de una serie de pares de comparaciones e intercambios con los valores
adyacentes. Cada paso haces que una llave suba a su posición final, como una
burbuja, en la lista ordenada.
Consideremos
otra vez nuestro ejemplo de lista de llaves no ordenadas:
Ordenamiento
por Selección
La
idea básica de un ordenamiento por selección es la selección repetida de la
llave menor restante en una lista de datos no clasificados, como la siguiente
llave (dato o registro), en una lista de datos ordenada que crece.
La
totalidad de la lista de llaves no ordenadas, debe estar disponible, para que
nosotros podamos seleccionar la llave con valor mínimo en esa lista. Sin
embargo, la lista ordenada, podrá ser puesta en la salida, a medida que
avancemos.
Ordenamiento
de Intercalación
no
es propiamente un método de ordenación, consiste en la unión de dos aráis
ordenados de modo que la unión esté también ordenada. Para ello, basta con
recorrer los aráis de izquierda a derecha e ir cogiendo el menor de los dos
elementos, de forma que sólo aumenta el contador del array del que sale el
elemento siguiente para el array-suma. Si quisiéramos sumar los arrays {1, 2,4}
y {3, 5,6},
Tipos
de ordenamiento optima segun la estrutura de datos utilizados
Los
métodos de ordenamiento interno se aplican cuando el conjunto de datos a
clasificar es lo suficientemente pequeño, de tal forma que pueda caber en
memoria principal. El tiempo requerido para leer o escribir registros no se
considera significativo para la evaluación del rendimiento interno.
Comentarios