complemento 5

Vista previa del material en texto

UPN, PASIÓN POR
TRANSFORMAR VIDAS
SESIÓN 5: ANALISIS DE ALGORITMOS
ANALISIS DE ALGORITMOS Y ESTRATEGIAS DE PROGRAMACION
LOGRO DE LA SESIÓN
Al término de la sesión el estudiante aplica los algoritmos de búsqueda y ordenamiento en la solución de problemas propuestos y los representa a través de algoritmos.
¡Pregunta!
¿Qué algoritmos de búsqueda y ordenamiento conoces?
4
Algoritmo rápido (Quicksort)
Descripción del algoritmo:
1) Dividir : Si la secuencia S tiene 2 o más elementos, seleccionar un elemento x de S como pivote. Cualquier elemento arbitrario, como el último, puede servir. Elimiar los elementos de S dividiéndolos en 3 secuencias:
L, contiene los elementos de S menores que x
E, contiene los elementos de S iguales a x
G, contiene los elementos de S mayores que x
2) Recursión: De forma recursiva ordenar L y G
3) Vencer: Finalmente, colocar nuevamente los elementos en S en orden, primero insertar los elementos de L, después E, y los elementos de G.
5
Idea de Quick Sort
1) Selección: tomar un elemento
2) Dividir: reordenar los elementos tal que x va a su posición final E
3) Recursión y Vencer: ordenar recursivamente
		
6
Arbol Quicksort
7
Arbol Quicksort
8
Arbol Quicksort
9
Arbol Quicksort
10
Arbol Quicksort
11
Arbol Quicksort
12
Arbol Quicksort
13
Arbol Quicksort
14
Arbol Quicksort
15
Arbol Quicksort
16
Arbol Quicksort
17
Arbol Quicksort
18
... Arbol Quicksort (final)
19
Quicksort In-Place
Paso Dividir: l recorre la secuencia desde la izquierda, y r desde la 
derecha
Se realiza un intercambio cuando l está en un elemento mayor que el pivote y r está en uno menor al pivote.
20
In Place Quick Sort (contd.)
Un intercambio con el pivote completa el paso dividir cuando r < l
21
Algoritmo rápido (Quicksort)
void qsort(int izq, int der, int a[])
{
 int i, ult, m, tmp;
 if (izq >= der)
 return;
 tmp= a[izq];
 m= (izq+der)/2;
 a[izq]= a[m];
 a[m]=tmp;
 ult=izq;
for (i=izq+1;i<=der;i++)
 if (a[i] < a[izq])
 {
 tmp= a[++ult];
 a[ult]= a[i];
 a[i]=tmp;
 }
 tmp= a[izq];
 a[izq]= a[ult];
 a[ult]=tmp;
 qsort(izq,ult-1,a);
 qsort(ult+1,der,a);
}
22
Ordenación directa por base (radix sort)
A diferencia de otros métodos, radix sort considera la estructura de las llaves.
Se asume que las llaves están representadas en un sistema de numeración M (M=radix), e.g., si M=2, las llaves están representadas en binario.
Toma ventaja de la posición de cada dígito individual en la clave. Hay dos versiones de la ordenación radix: MSD (most significant digit), LSD (least significant digit).
La ordenación se realiza comparando los bits en cada posición.
23
Ejemplo Radix sort
Conjunto a ordenar: { 33, 60, 5, 15, 25, 12, 45, 70, 35, 7}
 frente cola
cola_digitos[0] 60 70
cola_digitos[1]
cola_digitos[2] 12
cola_digitos[3] 33
cola_digitos[4]
cola_digitos[5] 5	 15	 25	 45	 35
cola_digitos[6]
cola_digitos[7] 7
cola_digitos[8]
cola_digitos[9]
24
Ejemplo Radix sort
Conjunto a ordenar: { 33, 60, 5, 15, 25, 12, 45, 70, 35, 7}
 frente cola
cola_digitos[0] 05 07
cola_digitos[1]	 12
cola_digitos[2] 25
cola_digitos[3] 33				 35
cola_digitos[4]
cola_digitos[5] 45	
cola_digitos[6] 60
cola_digitos[7] 70
cola_digitos[8]
cola_digitos[9]
25
Radix sort directo
Se examinan los bits de derecha a izquierda
for k=0 to b-1
 ordenar el array de forma estable
 tomando solo el bit k 
26
Radix sort en enteros
La ordenación resultante es estable:
27
Análisis de Tiempo de Ejecución
Los algoritmos de burbuja, inserción, selección corren en O(n2).
El algoritmo quicksort, montones corren en O(nlogn)
El algoritmo radix sort es O(n)
Algoritmos voraces
¡Gracias por su atención!