UNI_223_40_27_B2A_LO_TI6L_TOL515 B2.
ESTRUCTURA DE DATOS
Semana 3
Mtro. Gerardo Estrada Gutiérrez
1. 5. Algoritmos de búsqueda.
2. 6. Listas.
1 / 28
Algoritmos de búsqueda
Una de las tareas que realizan más frecuentemente las
computadoras en el procesamiento de datos es la
ordenación.
La ordenación o clasificación de datos (sort, en inglés) es
una operación consistente en disponer un conjunto -
estructura- de datos en algún determinado orden con
respecto a uno de los campos de los elementos del
conjunto.
2 / 28
Algoritmos de búsqueda
Una colección de datos (estructura) puede ser
almacenada en memoria central o en archivos de datos
externos guardados en unidades de almacenamiento
magnético (discos, cintas, CD-ROM, DVD, etc.). Cuando
los datos se guardan en un array, en una lista enlazada o
en un árbol, se denomina ordenación interna; estos datos
se almacenan exclusivamente para tratamientos internos
que se utilizan para gestión masiva de datos, se guardan
en arrays de una o varias dimensiones. Si los datos están
almacenados en un archivo, el proceso de ordenación se
llama ordenación externa.
3 / 28
Algoritmos de búsqueda
Existen diferentes algoritmos de ordenación elementales
o básicos cuyos detalles de implementación se pueden
encontrar en diferentes libros de algoritmos.
Los algoritmos presentan diferencias entre ellos que los
convierten en más o menos eficientes y prácticos según
sea la rapidez y eficiencia demostrada por cada uno de
ellos. Los algoritmos básicos de ordenación más simples y
clásicos son:
• Ordenación por selección.
• Ordenación por inserción.
• Ordenación por burbuja.
4 / 28
Método de la burbuja
Los métodos más recomendados son el de selección y el
de inserción, aunque se estudiará el método de burbuja
por ser el más sencillo, pero también es el más
ineficiente; por esta causa no se recomienda su uso, pero
si conocer su técnica.
La ordenación por burbuja es uno de los métodos más
fáciles de ordenación. El método (algoritmo) de
ordenación es muy simple. Se compara cada elemento del
array con el siguiente (por parejas), si no están en el
orden correcto, se intercambian entre sí sus valores. El
valor más pequeño flota hasta la parte superior del array
como si fuera una burbuja en un vaso de refresco con gas.
5 / 28
Método de inserción
El método de ordenación por inserción es similar al
proceso típico de ordenar tarjetas de nombres
(cartas de una baraja) por orden alfabético consistente en
insertar un nombre en su posición correcta dentro de una
lista que ya está ordenada. El proceso en el caso de la lista
de enteros es:
6 / 28
Método de inserción
El algoritmo correspondiente a la ordenación por
inserción contempla los siguientes pasos:
1. El primer elemento a[0] se considera ordenado; es
decir, la lista inicial consta de un elemento.
2. Se inserta a[1] en la posición correcta; delante o detrás
de a[0], dependiendo de si es menor o mayor
7 / 28
Método de inserción
3. Por cada bucle o iteración i (desde i=1 hasta n-1) se
explora la sublista a[i-1] ... a[0] buscando la posición
correcta de inserción de a[i]; a la vez, se mueven hacia
abajo (a la derecha en la sublista) una posición todos los
elementos mayores que el elemento a insertar a[i], para
dejar vacía esa posición.
4. Insertar el elemento a[i] a la posición correcta.
8 / 28
Método de Shell
La ordenación Shell debe el nombre a su inventor, D. L.
Shell. Se suele denominar también ordenación por
inserción con incrementos decrecientes. Se considera que
el método Shell es una mejora del método de inserción
directa.
9 / 28
Método de Shell
En el algoritmo de inserción, cada elemento se compara
con los elementos contiguos de su izquierda, uno tras
otro. Si el elemento a insertar es el mas pequeño, hay que
realizar muchas comparaciones antes de colocarlo en su
lugar definitivo.
El algoritmo de Shell modifica los saltos contiguos
resultantes de las comparaciones por saltos de mayor
tamaño, y con ello se consigue que la ordenación sea más
rápida. Generalmente, se toma como salto inicial n/2
(siendo n el número de elementos), y luego se reduce el
salto a la mitad en cada repetición hasta que sea de
tamaño 1.
10 / 28
Método de Shell (Ejemplo)
Obtener las secuencias parciales del vector al aplicar el
método Shell para ordenar de modo creciente la lista:
6 5 2 3 4 0
El número de elementos que tiene la lista es 6, por lo que
el salto inicial es 6/2 = 3. La siguiente tabla muestra el
número de recorridos realizados en la lista con los saltos
correspondiente.
11 / 28
QuickSort
El algoritmo conocido como quicksort (ordenación rápida)
recibe su nombre de su autor, Tony Hoare. La idea del
algoritmo es simple, se basa en la división en particiones
de la lista a ordenar, por ello se puede considerar que
aplica la técnica "divide y vencerás". El método es,
posiblemente, el más pequeño de código, más rápido,
más elegante y más interesante y eficiente de los
algoritmos conocidos de ordenación.
12 / 28
QuickSort
Este método se basa en dividir los n elementos de la lista
a ordenar en dos partes o particiones separadas por un
elemento: una partición izquierda, un elemento central
denominado pivote o elemento de partición y una
partición derecha. La partición o división se hace de tal
forma que todos los elementos de la primera sublista
(partición izquierda) sean menores que todos
los elementos de la segunda sublista (partición derecha).
Las dos sublistas se ordenan entonces
independientemente.
13 / 28
QuickSort
Para dividir la lista en particiones (sublistas) se elige uno
de los elementos de la lista y se utiliza como pivote o
elemento de partición. Si se elige una lista cualquiera con
los elementos en orden aleatorio, se puede elegir
cualquier elemento de la lista como pivote, por ejemplo,
el primer elemento de la lista. Si la lista tiene algún orden
parcial que se conoce, se puede tomar otra decisión para
escogerlo. Idealmente, el pivote se debe elegir de modo
que se divida la lista exactamente por la mitad de acuerdo
al tamaño relativo de las claves.
14 / 28
QuickSort
Por ejemplo, si se tiene una lista de enteros de 1 a 10, 5 o
6 serían pivotes ideales, mientras que 1 o 10 serían
elecciones “pobres” de pivotes.
Una vez que el pivote ha sido elegido, se utiliza para
ordenar el resto de la lista en dos sublistas: una tiene
todas las claves menores que el pivote y la otra, todos los
elementos (claves) mayores o iguales que el pivote (o al
revés). Estas dos listas parciales se ordenan
recursivamente utilizando el mismo algoritmo; es decir, se
llama sucesivamente al propio algoritmo quicksort.
15 / 28
QuickSort
La lista final ordenada se consigue concatenando la
primera sublista, el pivote y la segunda lista,
en ese orden, en una única lista. La primera etapa de
quicksort es la división o “particionado”
recursivo de la lista hasta que todas las sublistas constan
de sólo un elemento.
El algoritmo quicksort requiere una estrategia de
partición y la selección idónea del pivote. Las etapas
fundamentales del algoritmo dependen del pivote
elegido, aunque la estrategia de partición suele ser
similar.
16 / 28
QuickSort (Ejemplo)
17 / 28
Método de selección
Considérese el algoritmo para ordenar un array a[] de
enteros en orden ascendente, es decir, si el array a[] tiene
n elementos, se trata de ordenar los valores del array de
modo que a[0] sea el valor más pequeño, el valor
almacenado en a[1] sea el siguiente más pequeño, y así
hasta a[n-1] que ha de contener el elemento de mayor
valor. El algoritmo se apoya en las pasadas que
intercambian el elemento más pequeño, sucesivamente
con el elemento de la lista, a[], que ocupa la posición
igual al orden de pasada (hay que considerar el índice 0).
La pasada inicial busca el elemento más pequeño de la
lista y se intercambia con a[0], primer elemento de la
lista.
18 / 28
Método de selección
Después de terminar esta primera pasada, el frente de la
lista está ordenado y el resto de la lista a[1], a[2]...a[n-1]
permanece desordenado. La siguiente pasada busca en
esta lista desordenada y selecciona el elemento más
pequeño, que se almacena entonces en la posición
a[1]. De este modo, los elementos a[0] y a[1] están
ordenados y la sublista a[2], a[3]…a[n-1] desordenado;
entonces, se selecciona el elemento más pequeño y se
intercambia con a[2]. El proceso continúa hasta realizar n-
1 pasadas, en ese momento la lista desordenada se
reduce a un elemento (el mayor de la lista) y el array
completo queda ordenado.
19 / 28
Método de selección (Ejemplo)
Consideremos un array a[] con 5 valores enteros 51, 21,
39, 80, 36:
20 / 28
Listas
Un array (lista o tabla) es una secuencia de datos del
mismo tipo. Los datos se llaman elementos del array y se
numeran consecutivamente 0,1,2,3, etc. El tipo de
elementos almacenados en el array puede ser cualquier
tipo de dato de C, incluyendo estructuras definidas por el
usuario. Normalmente el array se utiliza para almacenar
tipos tales como char, int o float. Un array puede
contener, por ejemplo, la edad de los alumnos de una
clase, las temperaturas de cada día de un mes en una
ciudad determinada, o el número de personas que
residen en cada una de las diecisiete comunidades
autónomas españolas. Cada item del array se denomina
elemento.
21 / 28
Listas
Una lista es una agrupación lineal de elementos, que
pueden duplicarse. A una lista se añaden elementos por
la cabeza, por el final y, en general, por cualquier punto.
También, se pueden eliminar elementos de uno en uno, o
bien todos aquellos que estén en una colección. Existen
dos tipos de listas: secuenciales y enlazadas. El concepto
general de lista está representado por la
interfaz List, esta interfaz es la raíz de la jerarquía y por
conversión automática toda colección de tipo lista se
puede tratar con una variable de tipo List.
22 / 28
Operaciones e implementación de listas
La implementación del TAD Lista requiere, en primer
lugar, declarar la clase Nodo, en la que se combinarán sus
dos partes: el dato (entero, real, doble, carácter o
referencias a objetos) y un enlace. Además, la clase Lista
con las operaciones y el atributo con la cabeza de la lista.
Las operaciones tendrán las siguientes funciones:
• Inicialización o creación.
• Insertar elementos en la lista.
• Eliminar elementos de la lista.
• Buscar elementos de la lista.
• Recorrer la lista enlazada.
• Comprobar si la lista está vacía.
23 / 28
Listas circulares
En las listas lineales simples o en las dobles siempre hay
un primer nodo (cabeza) y un último nodo (cola). Una
lista circular, por propia naturaleza, no tiene ni principio ni
fin. Sin embargo, resulta útil establecer un nodo a partir
del cual se acceda a la lista y así poder acceder a sus
nodos.
A continuación se muestra una lista circular con enlace
simple; podría considerarse que es una lista lineal cuyo
último nodo apunta al primero.
24 / 28
Listas circulares
Las operaciones que se realizan sobre una lista circular
son similares a las operaciones sobre listas lineales,
teniendo en cuenta que no hay primero ni último nodo,
aunque sí un nodo de acceso a la lista. Estas operaciones
permiten construir el TAD ListaCircular y su funcionalidad
es la siguiente:
• Inicialización o creación.
• Inserción de elementos en una lista circular.
• Eliminación de elementos de una lista circular.
• Búsqueda de elementos de una lista circular.
• Recorrido de cada uno de los nodos de una lista
circular.
• Verificación de lista vacía.
25 / 28
Listas doblemente ligadas
Una lista doblemente enlazada es aquella en la que cada
nodo tiene una referencia a su sucesor y otra a su
predecesor. Las listas doblemente enlazadas se pueden
recorrer en ambos sentidos. Las operaciones básicas son
inserción, borrado y recorrer la lista, similares a las
de las listas simples.
26 / 28
Listas doblemente ligadas
Existen numerosas aplicaciones en las que es conveniente
poder acceder a los elementos o nodos de una lista
en cualquier orden, tanto hacia adelante como hacia
atrás. En este caso, se recomienda el uso de
una lista doblemente enlazada. En esta lista, cada
elemento contiene dos punteros (referencias),
además del valor almacenado. Una referencia apunta al
siguiente elemento de la lista y la otra referencia apunta
al elemento anterior.
27 / 28
Bibliografía
Zohonero Martínez, I. & Joyanes Aguilar, L. (2008),
Estructuras de datos en Java. McGraw-Hill España.
Ruiz Rodríguez, R. (2009), Fundamentos de la
programación orientada a objetos: una aplicación a las
estructuras de datos en Java.
Malik, D. S. (2013), Estructuras de datos con C++ (2a. ed.).
Cengage Learning México.
Joyanes Aguilar, L. (2006), Programación en C++:
Algoritmos, Estructuras de datos y objetos (2a. ed.).
McGraw-Hill España.
28 / 28
