Reporte 4 - Algoritmos de Ordenamiento y Busqueda

UNIVERSIDAD AUTÓNOMA
DE NUEVO LEÓN
FACULTAD DE INGENIERÍA
MECÁNICA Y ELÉCTRICA
UNIDAD DE APRENDIZAJE
ALGORITMOS
COMPUTACIONALES
REPORTE 4. “ALGORITMOS DE
ORDENAMIENTO Y BÚSQUEDA”
NOMBRE: DIANA LAURA ZAMORANO CHÁVEZ

MATRÍCULA: 1659774
CARRERA: INGENIERO EN TECNOLOGÍA DE SOFTWARE
MAESTRO: ING. JESSICA NATALIA MARTÍNEZ
BALDERAS
HORA: M1 GRUPO: 02 SALÓN: 1203
SEMESTRE: AGOSTO-ENERO 2020-2021
FECHA: 24-OCTUBRE-2020
INTRODUCCIÓN
Existen muchos distintos tipos de algoritmos que podemos usar al manejar datos.
En este documento en particular, se darán a conocer el algoritmo de ordenamiento
y de búsqueda, así como sus respectivas clasificaciones.
El algoritmo de ordenamiento nos permite, como su nombre lo dice, ordenar. Un

algoritmo de búsqueda es un conjunto de instrucciones que están diseñadas para
localizar un elemento con ciertas propiedades dentro de una estructura de datos;
por ejemplo, ubicar el registro correspondiente a cierta persona en una base de
datos, o el mejor movimiento en una partida de ajedrez.
Al término de esta lectura, conoceremos un poco de cada método distinto de

ordenamiento y de búsqueda, desde uno simple hasta el más complejo.
ALGORITMO DE ORDENAMIENTO
Un algoritmo de ordenamiento ayuda a reagrupar o reorganizar un conjunto de

datos en una secuencia específica.
En el procesamiento de datos a los métodos de ordenación se les clasifican en dos

grandes categorías, según donde hayan sido almacenados:
 Ordenación de arreglos.
 Ordenación de archivos.
La primera categoría se denomina también ordenación interna, ya que los

elementos o componentes del arreglo se encuentran en la memoria principal de la
computadora. La segunda categoría se llama ordenación externa, ya que los
elementos se encuentran en archivos almacenados en dispositivos de
almacenamiento secundario.
ORDENACIÓN INTERNA
Consta de tres pasos en general:
 Leer los datos.

 Ordenar los datos en memoria.
 Escribir o presentar los datos.
Algunos tipos de algoritmos de ordenamiento interno son:
 Bubblesort
Es el más sencillo de los algoritmos de ordenamiento, revisa cada elemento
de la lista que va a ser ordenada con el siguiente, intercambiándolos de
posición si están en el orden equivocado.
En este es necesario revisar varias veces toda la lista hasta que no se
necesiten más intercambios.
Este algoritmo obtiene su nombre de la forma con la que suben por la lista
los elementos durante los intercambios, como si fueran "burbujas".
Ejemplo:
 Mergesort
La idea de mergesort es la misma para todos los métodos de ordenamiento
externo. Ordenar, mediante algún algoritmo de ordenamiento interno, una
cantidad de datos que pueda almacenarse en memoria.
Combina los distintos grupos de datos mediante el método de mezcla. El
algoritmo de mezcla parte de dos vectores de entrada A y B produciendo un
vector de salida C.
Se apoya en tres contadores:
1. Acont
2. Bcont
3. Ccont
En cada paso el menor de los valores A y B se copia en la próxima posición
de C, actualizándose los contadores apropiados. Cuando uno de los
vectores
de entrada se acaba, el resto del otro vector se copia en C.
Ejemplo:
 Quicksort
Es el algoritmo de ordenamiento más rápido. El algoritmo quicksort es
recursivo y está formado por cuatro pasos:
1. Dado un conjunto S de números, si el número de elementos es menor o
igual a 1, terminar.
2. Escoger un elemento cualquiera de S, el cuál será llamado pivote {v}.
3. Hacer una partición de S-{v} en dos grupos disjuntos:
I = {x ∈ S – {v} | x < v}
D= {x ∈ S – {v} | x > v}
4. Devolver el resultado de Quicksort (I), seguido de v y luego el resultado
de Quicksort (D).
Selección del pivote
El algoritmo básico de Qsort permite tomar cualquier elemento como pivote,

de la elección del pivote depende la eficiencia del algoritmo. Algunos
métodos para elegir el elemento que se utilizará como pivote son:
 Elección aleatoria del pivote.

 No se requiere ningún cálculo adicional.
 El algoritmo puede tener un gran número de iteraciones.
 Recorrer la lista para ver que pivote es el conveniente.
 Tomar el elemento de que está en medio del arreglo.
Ejemplo:
ORDENACIÓN EXTERNA
En la actualidad es muy común procesar tales volúmenes de información que los

datos no se pueden almacenar en la memoria principal de la computadora. Estos
datos, organizados en archivos, se guardan en dispositivos de almacenamiento
secundario.
El proceso de ordenar los datos almacenados en varios archivos se conoce como

fusión o mezcla; se entiende por este concepto a la combinación o intercalación de
dos o más secuencias ordenadas en una única secuencia ordenada. Se debe
hacer hincapié en que sólo se colocan en la memoria principal de la computadora
los datos que se pueden acceder en forma directa.
Algunos tipos de algoritmos de ordenamiento externo son:
 Intercalación
Pre condiciones:
 Los archivos de entrada contienen registros homogéneos.
 Los archivos de entrada deben estar ordenados en base a la misma
llave.
Post condiciones:
 El archivo de salida quedará ordenado por la misma llave que los
archivos de entrada.
 El archivo de salida contendrá todos los registros de los archivos
de entrada.
 Mezcla directa
Suponer que 900 MB de información deben ser ordenados utilizando
únicamente 100 MB de RAM.
1. Leer 100MB de información en memoria principal y ordenar utilizando un
algoritmo tradicional (normalmente QSort).
2. Escribir la información ordenada en disco.
3. Repetir hasta que toda la información esté ordenada en pedazos de 100
MB.
4.Mezclar todos los pedazos ordenados:
 Leer los primeros 10MB de cada pedazo ordenado a la memoria
principal (total de 90 MB) y dejar 10 MB restantes para el buffer de
salida.
 Buscar el menor de los nueve pedazos mezclándolos y grabar el
resultado en el buffer de salida.
 El pedazo de los 9 buffers leídos que quedó vacío, se llena con los
siguientes 10 MB de su pedazo original de 100 MB o se marca como
completado si ya no se tienen más registros.
ALGORITMO DE BÚSQUEDA
Los procesos de búsqueda involucran recorrer un arreglo completo con el fin de

encontrar algo. Lo más común es buscar el menor o mayor elemento (cuando se
puede establecer un orden), o buscar el índice de un elemento determinado.
Para buscar el menor o mayor elemento de un arreglo, podemos usar la estrategia,
de suponer que el primero o el último es el menor (mayor), para luego ir
comparando con cada uno de los elementos, e ir actualizando el menor (mayor). A
esto se le llama Búsqueda Lineal.
Definición:
Para encontrar un dato dentro de un arreglo, para ello existen diversos algoritmos
que varían en complejidad, eficiencia, tamaño del dominio de búsqueda.
Tipos de algoritmos de búsqueda:
Búsqueda Secuencial
Consiste en ir comparando el elemento que se busca con cada elemento del

arreglo hasta cuándo se encuentra.
Ejemplo:
 Busquemos el elemento ‘u’.
Búsqueda Binaria
Una búsqueda más eficiente puede hacerse sobre un arreglo ordenado. Una de
éstas es la búsqueda binaria. Ésta compara si el valor buscado está en la mitad
superior o inferior. En la que esté, subdivido nuevamente, y así sucesivamente
hasta encontrar el valor.
Ejemplo:
CONCLUSIÓN
Desde hace muchos años se conoce la importancia de guardar información y

recuperarla. Hoy, gracias a los sistemas de cómputo, pueden almacenarse grandes
cantidades de información, por lo que se hace necesario contar con medios
eficaces para hallar la que es de utilidad cuando ésta es requerida.
Una de las principales conclusiones que se extraen del documento es que para que
un algoritmo de ordenamiento sea el más rápido para cualquier conjunto de datos a
ordenar, debe ser consciente tanto de la jerarquía de memoria del computador,
como de la forma de ordenarse de los elementos.
Los algoritmos de búsqueda son esenciales ya que ahorrar demasiado tiempo en la

búsqueda de información, por lo cual es de vital importancia conocer cómo
funcionan, como pudimos conocer en este documento.
BIBLIOGRAFÍA
 Cairó, O., & Guarati, S. (2006). Estructuras de datos (3a. ed.). McGraw-Hill

Interamericana.
 Academicos.azc.uam.mx. (2020). Recuperado 23 octubre 2018, de
http://academicos.azc.uam.mx/jfg/diapositivas/almacenamiento/Unidad_6.pdf
 Inf.utfsm.cl. (2017). Recuperado 23 octubre 2020, cd
https://www.inf.utfsm.cl/~noell/IWI-131-p1/Tema8b.pdf.

Reporte 4 - Algoritmos de Ordenamiento y Busqueda

Cargado por

Copyright:

Formatos disponibles

Reporte 4 - Algoritmos de Ordenamiento y Busqueda

Cargado por

Información del documento

Título original

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

Reporte 4 - Algoritmos de Ordenamiento y Busqueda

Cargado por

Copyright:

Formatos disponibles

UNIVERSIDAD AUTÓNOMA

NOMBRE: DIANA LAURA ZAMORANO CHÁVEZ

El algoritmo de ordenamiento nos permite, como su nombre lo dice, ordenar. Un

Al término de esta lectura, conoceremos un poco de cada método distinto de

Un algoritmo de ordenamiento ayuda a reagrupar o reorganizar un conjunto de

En el procesamiento de datos a los métodos de ordenación se les clasifican en dos

La primera categoría se denomina también ordenación interna, ya que los

Consta de tres pasos en general:

 Leer los datos.

Algunos tipos de algoritmos de ordenamiento interno son:

Selección del pivote

El algoritmo básico de Qsort permite tomar cualquier elemento como pivote,

 Elección aleatoria del pivote.

En la actualidad es muy común procesar tales volúmenes de información que los

El proceso de ordenar los datos almacenados en varios archivos se conoce como

Algunos tipos de algoritmos de ordenamiento externo son:

Los procesos de búsqueda involucran recorrer un arreglo completo con el fin de

Tipos de algoritmos de búsqueda:

Consiste en ir comparando el elemento que se busca con cada elemento del

 Busquemos el elemento ‘u’.

Desde hace muchos años se conoce la importancia de guardar información y

Los algoritmos de búsqueda son esenciales ya que ahorrar demasiado tiempo en la

 Cairó, O., & Guarati, S. (2006). Estructuras de datos (3a. ed.). McGraw-Hill

También podría gustarte