quick sort estructuras de datos universidad autónoma de tlaxcala unidad académica...
TRANSCRIPT
Quick Sort
Estructuras de Datos
Universidad Autónoma de TlaxcalaUnidad Académica Multidisciplinaria
14 de Septiembre de 2012
Ordenación rápida: Quick Sort
Quick Sort divide el vector en dos partes que se ordenan recursivamente. Se puede resumir en tres pasos:
1. Escoger un Elemento de Pivote.
•Existen varias maneras de obtener el elemento de pivote.
•En este caso se devuelve el primer elemento.
•No hay ninguna manera que garantice mejores resultados.
Ordenación rápida: Quick Sort
Quick Sort divide el vector en dos partes que se ordenan recursivamente. Se puede resumir en tres pasos:
2. Particionar el vector en dos partes: una cuyos elementos son menores que el pivote, otra cuyos elementos son mayores.
3. Ordenar cada partición de manera recursiva con QuickSort.
Ordenación rápida: Quick Sort
•Existen varias maneras de obtener el elemento de pivote.
•En este caso se devuelve el último elemento.
•No hay ninguna manera que garantice mejores resultados.
Ordenación rápida: Quick Sort
Algoritmo QuickSort: Animación
http://www.cs.ubc.ca/spider/harrison/Java/http://en.wikipedia.org/wiki/Quicksort
http://www.cs.mu.oz.au/aia/QuickSort.html
Recorrido de grafos
Muchos problemas se pueden representar por grafos
Un grafo G=(V,E) consiste en un conjunto V de vértices y un conjunto E de aristas
Hay varias razones para recorrer grafos:- visitar todos los vértices- buscar un(os) vértice(s)
L M N O P
G
Q
H JI K
FED
B C
A
Búsqueda en profundidad (DFS; depth-first search)
Recorre todos los vértices de una rama antes de seguir con la siguiente
Visita a algunos vértices muy lejanos (profundos) del origen antes de otros cercanos
La implementación más fácil es recursivaL M N O P
G
Q
H JI K
FED
B C
A
Búsqueda en profundidad (DFS)
Para no visitar a un mismo vértice varias veces, hay que marcar los vértices ya visitados
Sólo visitamos a un nodo si no ha sido marcado
L M N O P
G
Q
H JI K
FED
B C
A
1 accion DFS(v: vertice)2 variable u: vertice;3 si (no marcado(v)) entonces4 marcado(v) := cierto;5 // procesamiento anterior de v6 para cada vecino u de v hacer7 DFS(u);8 fpara9 // procesamiento posterior de v10 fsi11 faccion
Búsqueda en profundidad (DFS)
1 funcion DFS(v,w: vertice) devuelve booleano2 variable u: vertice;3 b: booleano;4 si (marcado(v)) entonces5 devuelve falso;6 sino7 marcado(v) := cierto;8 si (v = w) entonces9 devuelve cierto;10 fsi11 b := falso;12 para cada vecino u de v hacer13 b := b o DFS(u, elem);14 fpara15 devuelve b;16 fsi17 ffuncion
Ejemplo: buscar un vértice w
Búsqueda en anchura (BFS; breadth-first search)
Recorre los vértices en orden de su distancia desde el origen
Visita a todos los vértices (el ancho) de un nivel antes de seguir con el siguiente
Siempre encuentra la distancia mínima entre un vértice y el origen
L M N O P
G
Q
H JI K
FED
B C
A
Búsqueda en anchura (BFS)
Mantener una cola de vértices a procesar
Cola: primer dato que entra, primero que sale (FIFO)
Marcar vértices ya visitados (igual que para DFS)
Agregar nuevos vértices a la cola
Seguir hasta que la cola esté vacía
1 accion BFS(v: vertice)2 variable c: cola;3 u,w: vertice;4 marcado(v) := cierto; // falso para otros vértices5 Inicializar(c);6 Agregar(c, v);7 mientras (no Vacia(c)) hacer8 u := Sacar(c);9 // procesamiento anterior de u10 para cada vecino w de u hacer11 si (no marcado(w)) entonces12 marcado(w) := cierto;13 Agregar(c, w);14 fsi15 fpara16 // procesamiento posterior de u17 fmientras18 faccion
Búsqueda en anchura (BFS)
1 tupla cola2 v: vector de vertice; i,d: natural;3 ftupla
Implementación de cola
1 accion Agregar(c: cola; v: vertice)2 c.v[c.d] := v; c.d := c.d + 1;3 faccion
1 funcion Vacia(c: cola) devuelve booleano2 devuelve c.d > c.i;3 ffuncion
1 funcion Sacar(c: cola) devuelve vertice2 c.i := c.i + 1; devuelve c.v[c.i – 1];3 faccion
1 accion Inicializar(c: cola)2 c.i := c.d := 1;3 faccion
1 funcion BFS(v,x: vertice) devuelve natural2 variable c: cola;3 u,w: vertice;4 marcado(v) := 0; // -1 para otros vértices5 Inicializar(c);6 Agregar(c, v);7 mientras (no Vacia(c)) hacer8 u := Sacar(c);9 para cada vecino w de u hacer10 si (marcado(w) < 0) entonces11 marcado(w) := marcado(u) + 1;12 Agregar(c, w);13 fsi14 fpara15 fmientras16 devuelve marcado(x);19 ffuncion
Ejemplo: devolver la distancia de v a un vértice x
Ordenación por intercalación: Merge Sort
Merge Sort es un algoritmo recursivo para ordenar los elementos de un vector.
Primero se divide el vector en dos partes iguales.
Después se ordenan las dos partes recursivamente.
Finalmente se combinan las dos partes ordenadas para obtener el resultado.
Ordenación por intercalación: Merge Sort
1 funcion MergeSort (V: vector de natural ; E,D: natural) devuelve vector de natural
2 variable medio : natural ;3 Ve , Vd : vector de natural ;4 si (E >= D) entonces5 devuelve [ V[E] ];6 sino7 medio := ( E + D ) / 2;8 Ve := MergeSort ( V, E, medio );9 Vd := MergeSort ( V, D, medio+1 );10 devuelve Combina (Ve , Vd , medio – E + 1, D – medio );11 fsi12 ffuncion
1 funcion Combina (V1,V2 : vector de natural ; m,n: natural) devuelve vector de natural
2 variable resultado : vector de natural ;3 r, i, j : natural;4 r := 1; i := 1; j := 15 mientras (( i <= m) y ( j <= n)) hacer6 si (V1 [i] <= V2 [j] ) entonces7 resultado[r] := V1[i];8 i := i + 1; r := r + 1;9 sino10 resultado[r] := V2[j];11 j := j + 1; r := r + 1;12 fsi13 fmientras14 mientras ( i <= m ) hacer15 resultado[r] := V1[i];16 i := i + 1; r := r + 1;17 fmientras18 mientras ( j <= n) hacer19 resultado[r] := V2[j];20 j := j + 1; r := r + 1;21 fmientras22 devuelve resultado;23 ffuncion
Dividir en el centro
Intercalar lasSoluciones
Ordenar recursivamente
Ordenación por intercalación: Merge Sort
Ordenación por intercalación: Merge Sort
6 12 4 9 8 13 5
4 6 9 12 5 8 13
4 5 6 8 9 12 13
Llamada recursiva 1 ( MergeSort )
Llamada recursiva 2 ( MergeSort )
Llamada recursiva 3 ( MergeSort )
Volver 3 a 2 ( Combina )
Volver 2 a 1 ( Combina )
Combina
Algoritmo MergeSort: Animación
http://www.cs.toronto.edu/%7Eneto/teaching/238/16/mergesort.html
http://www.cs.ubc.ca/spider/harrison/Java/http://www.sorting-algorithms.com/merge-sort