Programación

Avanzada
Miércoles: 1 pm – 4 pm
Miércoles: 6 pm – 9 pm
 Contenido

01 02
Importancia de Analizar diferentes
los algoritmos de algoritmos de
ordenamiento ordenamiento

03
Implementar
algoritmos de
ordenamiento.
 01
Importancia de
los algoritmos de
ordenamiento
¿Que son los
AO?
Son algoritmos que buscan ordenar
una lista de información de acuerdo a
algún criterio de ordenamiento
El ordenamiento puede estar
dado de forma iterativa o
recursiva según la naturaleza
y forma de ejecución del
mismo.
 Computer programmers

Sistemas Búsqueda y
Operativos rastreo web
archivos en un sistema Los datos deben organizarse
de archivos para facilitar la búsqueda y
recuperación
Comercio
electrónico Enrutamiento
Listar productos de en redes
manera ordena segun
filtros manipulación de tablas de
enrutamiento para organizar la
información sobre la mejor ruta
para enviar datos a través de una
red
02
Algunos
Algoritmos
Método de Ordenamiento de la Burbuja
Funciona revisando cada elemento de la lista a ordenar
con el que le sigue, cambiándolos de posición si están en
un orden incorrecto. Es necesario repetir este proceso
varias veces hasta que no se necesiten más cambios
• El algoritmo burbuja se compone de 2 bucles, uno
dentro del otro. Llamaremos “bucle hijo” al que se
encuentra dentro del otro bucle, es decir del “bucle
papá”
• El “bucle papá” realizará el número de iteraciones
necesarias para ordenar la lista (las iteraciones
necesarias son n-1 veces) y el “bucle hijo” se encargará
de comparar cada elemento con su adyacente y
ordenarlos
 Método de Ordenamiento de Selección

El Método de ordenamiento por selección consiste en

buscar el menor entre todos los elementos no ordenados
y colocarlo al principio, luego se debe repetir lo mismo con
los restantes (no se tienen en cuenta los ya ordenados).
 Pasos

1 2 3 4

Recorres la Al encontrar el
Repite lo
Comienzas con lista en elemento más
mismo para el
el primer busqueda de pequeño lo
siguiente
elemento de la un elemento intercambias
elemento de la
lista menor al que con el que
lista
tienes tienes
Método de Ordenamiento de Inserción
El método de ordenamiento de inserción actúa
recorriendo la lista a ordenar, tomando el elemento actual
e insertándolo donde debería comparándolo entre los que
ya ha recorrido
 Pasos

1 2 3 4

Compara el
Comienza con el Continúa
elemento actual con
segundo elemento Si el elemento actual comparando e
los elementos
de la lista (índice 1), es menor que el intercambiando
anteriores en la lista,
asumiendo que el elemento en la hasta encontrar la
comenzando desde
primer elemento ya posición anterior, posición correcta
el índice actual y
está "ordenado" en intercámbialos. para el elemento
retrocediendo hasta
su lugar actual.
el inicio de la lista.
Método de Ordenamiento Shell
El Método de ordenamiento Shell es una mejora del Método de Ordenamiento
por inserción ya que el Método de inserción es eficiente si la lista está casi
ordenada, para ello el Método Shell compara elementos separados por un
espacio de varias posiciones, esto permite que un elemento haga “pasos más
grandes” hacia su posición esperada, el mismo finaliza con un Ordenamiento por
inserción simple
Pasos
Tenemos la siguiente lista: [10, 5, 48, 12, 36, 51, 1]
Tenemos que ubicar algo llamado distancia, esto lo podemos realizar dividiendo
10 5 48 12 36 51 1 entre dos y esa será la cantidad de subgrupos que saldrán

10 5 48 12 36 51 1

1 10 12 Al tener un tamaño de 7, la distancia seria 3, siguiendo el patrón de colores se

aplica el algoritmo de inserción
5 36

48 51

Se vuelva a calcular la distancia, pero esta vez ya no será a partir del tamaño de
1 5 48 10 36 51 12 lista si no, de la distancia anterior

Como la distancia anterior era tres, cuando la volvemos a calcular nos da 1 que es
1 5 48 10 36 51 12 lo que buscamos (siempre debemos llegar a distancia uno), aquí es donde
aplicamos por última vez el algoritmo de inserción.
Método de Ordenamiento por mezcla
El Método de ordenamiento por mezcla tiene un funcionamiento muy particular,
primero debemos saber que, si la longitud de la lista es 0 o 1 ya está ordenada, En
otro caso: el algoritmo deberá dividir la lista desordenada en dos sub-listas de
aproximadamente la mitad del tamaño, luego ordenará cada sub-lista
recursivamente aplicando el ordenamiento por mezcla y por último mezcla las
dos sublistas en una sola lista ordenada.
Pasos
Basándose en la idea de divide y vencerás nos encontramos con un algoritmo que busca
dividir el vector inicial en dos recursivamente.

Caso base: Buscar la lista más fácil de [10,5,3,15,16,8]

ordenar.

Si el array tiene más de un elemento

[10,5,3] [15,16,8]

divide el array hasta llegar al caso

base [10] [5,3] [15] [16,8]

[5] [3] [16] [8]

Método de ordenamiento rápido
Al igual que el ordenamiento por mezcla, el ordenamiento rápido es un algoritmo
divide y ganarás, el mismo funciona seleccionando un elemento como pivot y
dividiendo la matriz dada alrededor del pivot elegido. Hay muchas versiones
diferentes de ordenamiento rápido que eligen pivotar de diferentes maneras.

• Elegir siempre el primer elemento como pivot.

• Elegir siempre el último elemento como pivot.
• Elegir un elemento aleatorio como pivot.
• Elegir la mitad como pivot.
Pasos
Teniendo nuestro pivote, procedemos a poner los elementos menores que el a la
izquierda y los mayores a su derecha.
10 5 48 12 36 51 1
Esto nos da dos sub arrays y el pivote
técnicamente quedo en su posición. 5 1 10 48 12 36 51

Con los dos sub arrays se vuelve 5 1 10 48 12 36 51

aplicar el algoritmo así 1 5 10 12 36 48 51

sucesivamente hasta encontrar el
caso base. 1 5 10 12 36 48 51

El caso base es cuando las listas 1 5 10 12 36 48 51

tienen un tamaño igual a 1

Gracias