Guía Lab AlgComp

Guía para ordinario lab algoritmos computacionales
Ordenamiento informático: colocar de una manera especial o bajo algún

criterio de información de datos, basados en algoritmos para llevar a cabo el
proceso.
Campo clave: es la parte de un registro (un renglón de excel) o de un dato de

información alojado en la lista para su posterior ordenamiento.
Criterio de ordenamiento: también es conocido comparación (estructura if)

es el criterio que llevas a cabo para asignar valores a los registros con base
a una o más claves. De esta manera se dice si un registro es mayor o menor
que el otro.
Registro: Es un grupo de datos que conforman la lista, estos datos pueden ser
atómicos (enteros, decimales, float, booleanos o de texto)
Requerimiento de memoria: el algoritmo puede necesitar memoria adicional

(ram) aunque es preferible que no sea así aunque es muy común en la
programación el tener que sacrificar memoria del equipo.
Estabilidad: es el como se comportan los registros que tienen claves iguales
Algoritmos de ordenamiento
Nombre Estabilidad Memoria adicional
Bubble sort Estable No
Selección No estable No
Insercción Estable No
Quick sort No estable No
Notas: “Tam” es el número de valores que tiene una serie y el número de

vueltas que se usen para acomodarla no debería rebasar este valor.
Método de la burbuja (Bubble sort)
Es el más sencillo consiste en ciclar repetidamente (for while / do while) a
través de una lista, comparando elementos adyacentes de dos en dos.
● Se utiliza normalmente cuando “Tam” es impar.
Pasos:
1. Tomar los primeros dos valores, y en caso de que el primer valor sea
mayor al otro se cambian de lugar.
2. Seguir con el siguiente par de números y hacer el mismo proceso
(segundo y tercer valor).
3. El mismo proceso con el otro par de números (tercer y cuarto valor).
4. Así sucesivamente hasta que esté en orden.
Ordenamiento por selección
Es uno de los más utilizados.
Pasos:
1. Buscas el elemento más pequeño de la lista
2. Lo intercambias o comparas con el elemento ubicado en la primera
posición
3. Buscas el segundo elemento más pequeño de la lista
4. Lo intercambias con el elemento que ocupa la segunda posición
5. Repites el proceso N cantidad de veces.
Ventajas:
● Fácil implementación
● No requiere memoria adicional
● Realiza pocos intercambios
● Buen rendimiento
Desventajas:
● Para nosotros, el proceso sigue siendo lento
Ordenamiento por inserción
Algoritmo bastante sencillo, en el cual se desplazan los elementos a una
sección llamada “temp” al momento de desplazarse para no perderlos.
● Cuando “temp” está vacío se le pone null, la cual es una variable vacía
no cero.
Pasos:
1. Guardar una copia del elemento actual y desplazas todos los elementos
de la lista mayores a él hacía la derecha (en caso de ser ASCENDENTE)
2. Copias el elemento guardados en la posición del último elemento que se
desplazó
3. Repites el proceso hasta que se ordene toda la información (usa FOR)
Características:
● No importa si “Tam” es par o impar
● Con este método siempre se puede lograr el ordenamiento en una sola
vuelta.
Ventajas:
● Fácil implementación
● Requerimiento mínimo de memoria.
Desventajas:
● Para nosotros, es un método lento.
Ejemplo en la siguiente página pookie >3<

Ordenamiento rápido (quicksort)
Es la técnica más rápida conocida.
Pasos:
1. Eliges un elemento de la lista, puede ser cualquiera (con que elijas una
posición que tenga más de 2 valores por los dos lados) y lo vas a llamar
pivote o elemento de división.
2. Buscas la posición que le corresponde a este elemento.
3. Acomodas los elementos en la lista a cada lado del pivote, de manera
que a un lado queden los menores a él, y al otro lado los mayores.
4. Se separa la lista en 2 sublistas.
5. Se realiza esto de manera recursiva para cada sublista mientras éstas
tengan un largo mayor que uno.
Ventajas:
● Muy rápido.
● No requiere memoria adicional.
Desventajas:
● Su implementación es un poco más compleja.
● Utiliza muchos recursos (mucha RAM).
● Muchas comparaciones.
Ejemplo en la siguiente página pookie >3<

Tabla hash: es un contenedor tipo diccionario que permite un almacenamiento
y posterior recuperación eficientes de elementos (denominados valores) a
partir de otros objetos, llamados claves.
Contienen:
● Los valores junto con su clave.
● Arreglo: que es el lugar donde se irán guardando los valores.
● Una función hash: se encarga de procesar la clave con alguna técnica
en específico - ej. sumar el número de letras en un nombre y
multiplicarlo por 3- y transformar la clave en un índice.
● Slots o bucket: el lugar donde se guardarán los valores, determinado
por el índice.
● Índice: indica a qué slot/bucket irá el valor, de esta manera cuando
quieras acceder a N valor podrás utilizar su índice para obtener ese
valor y que no sea necesario recorrer todos los datos del arreglo.
Función: las tablas hash son como un sistema de almacenamiento rápido para
pares clave-valor. Su función es permitir buscar, añadir y eliminar datos de
forma eficiente. Usan una "función hash" para convertir una clave en un
número, que luego se usa para encontrar rápidamente el valor
correspondiente en la tabla.
Estas tablas se utilizan en muchos lugares donde se necesita acceso rápido a
datos asociados a una clave, como en diccionarios y cachés.
Colisión: cuando tienes el mismo índice para dos valores diferentes

Soluciones:
● Buscando la siguiente casilla disponible
● Transformando tu arreglo en un arreglo de listas enlazadas (entonces
cada casilla se convertirá en una lista enlazada de tal forma que si nos
encontramos con una colisión, se creará una lista enlazada y se
guardarán los elementos uno tras otro y cuando entres a ese índice se
hará el recorrido de todos los elementos que están asociados en esa
lista enlazada)
● También se puede resolver cambiando tu función hash (básicamente
cambiando la forma en la que el programa decide el índice de cada
valor).

Guía Lab AlgComp

Cargado por

Copyright:

Formatos disponibles

Guía Lab AlgComp

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Guía Lab AlgComp

Cargado por

Copyright:

Formatos disponibles

Guía para ordinario lab algoritmos computacionales

Ordenamiento informático: colocar de una manera especial o bajo algún

Campo clave: es la parte de un registro (un renglón de excel) o de un dato de

Criterio de ordenamiento: también es conocido comparación (estructura if)

Requerimiento de memoria: el algoritmo puede necesitar memoria adicional

Estabilidad: es el como se comportan los registros que tienen claves iguales

Nombre Estabilidad Memoria adicional

Bubble sort Estable No

Quick sort No estable No

Notas: “Tam” es el número de valores que tiene una serie y el número de

Ejemplo en la siguiente página pookie >3<

Ejemplo en la siguiente página pookie >3<

Colisión: cuando tienes el mismo índice para dos valores diferentes

También podría gustarte