Quicksort Por Mediana De 3
Páginas: 6 (1337 palabras)
Publicado: 10 de octubre de 2011
UNIVERSIDAD TECNOLÓGICA NACIONAL
FACULTAD REGIONAL CÓRDOBA
CÁTEDRA:
“TECNOLOGÍA DE SOFTWARE DE BASE”
INFORME:
“VARIANTE DEL MÉTODO QUICKSORT: SELECCIÓN DEL PIVOTE POR MEDIANA DE 3”
CURSO:
“3K1”
FECHA DE ENTREGA:
“03/10/2011”
INTEGRANTES:
LEG. 50456 AGÚ, JUAN HORACIO
LEG. 51522 MACINA, VALERIA
LEG. 52894 PALOMANES, DAMIÁN ALBERTO
LEG. 52846 RAMOS, NICOLÁS MARTÍNIntroducción
Este informe aborda el análisis de la variante conocida como “Selección del pivote por Mediana de 3” del algoritmo de ordenamiento “QuickSort”.
El algoritmo básico fue diseñado por C. A. R. Hoare en el año 1960, con su publicación en 1962. Desde entonces ha sido una revolución y se ha convertido en el algoritmo mas utilizado cuando se trata de ordenamiento.
Es muy popularporque es relativamente fácil de implementar, ofrece buenos resultados generales, en muchos casos consume menos recursos que otros método de ordenación, y está bien estudiado (ha sido expuesto a un minucioso análisis matemático que ha sido corroborado con amplia experiencia práctica).
Quicksort en el mejor y peor caso se puede ver que es uno de los mejores métodos de ordenación.
Particularmente, sehablará de la variante “Mediana de 3” desarrollado desde un aspecto algorítmico así como matemático explicando características de la misma.
Contenido
Se conoce como Quicksort a un algoritmo de ordenamiento, también conocido como “método rápido” o de “ordenamiento por participación”. Este algoritmo se basa en la estrategia de “Divide y Vencerás”.
La idea de este algoritmo, consta de:Tomar un elemento x de una posición cualquiera del arreglo.
Tratar de ubicar a x en una posición correcta del arreglo, de forma que todos los elementos que se encuentren a su izquierda sean menores que x, y los de la derecha, mayores.
Repetir los pasos anteriores, pero tomando como subconjunto los conjuntos “menores” y “mayores” a x. Posterior a esto, se sigue realizando repetitivamente estos pasoshasta lograr que la lista de elementos queden ordenados.
Veremos un ejemplo de cómo este algoritmo ordena una lista de números, tomando un pivote al azar y re acomodando las sublistas que aparecen luego de este proceso.
Tenemos una lista formada por 7 números sin ningún orden entre si y lo queremos ordenar de menor a mayor.
Para llevar a cabo este ejemplo, nombraremos con “p” la pivote,“i” el primer elemento y “j” el anterior al pivote, tanto i como j se irán moviendo hacia el centro de la lista, paso por paso.
La lista esta formada por: 5 – 3 – 7 – 6 – 2 – 1 – 4.
Se toma como p, i y j, los siguientes elementos:
[pic]
Comenzaremos comparando el 5 por la izquierda y el 1 por la derecha. 5 es mayor que 4 y 1 es menor, por lo que colocamos el 5 en la derecha (posición j) y el1 por la izquierda (posición i) y avanzamos i a la segunda posición y j a la quinta posición.
[pic]
Como 3 es menor que 4, avanzamos una posición y dejamos al 3 en ese lugar. Como 2 es menor que 4, dejamos en esa posición a j.
[pic]
Ahora continuamos, 7 es mayor que 4 y 2 es menor, por lo que se intercambian ambos números y avanzamos nuevamente.
[pic]
En este momento es en el cualtermina el ciclo principal, cuando i se junta con j, se intercambia el valor “p” por el valor de i, lo cual queda:
[pic]
Como habíamos dicho anteriormente, nos quedan 2 sublistas armadas, la de la izquierda y la de la derecha. La izquierda esta formada por 1 – 3 – 2 y la de la derecha por 7 – 5 – 6, terminaremos el acomodamiento de la primera ya que en ambos lados se continúan los mismospasos.
Tomamos como pivote el 1.
[pic]
Realizamos la comparación, 1 es menor que 2, avanzamos y 3 es mayor, por lo que también avanzamos, como se intercambian los índices, se intercambia i con p, lo que queda:
[pic]
Realizando los mismos pasos de esta sublista con la sublista de la derecha, nos quedaría la lista completamente ordenada, lo cual seria:
[pic]
Técnicas para la...
FACULTAD REGIONAL CÓRDOBA
CÁTEDRA:
“TECNOLOGÍA DE SOFTWARE DE BASE”
INFORME:
“VARIANTE DEL MÉTODO QUICKSORT: SELECCIÓN DEL PIVOTE POR MEDIANA DE 3”
CURSO:
“3K1”
FECHA DE ENTREGA:
“03/10/2011”
INTEGRANTES:
LEG. 50456 AGÚ, JUAN HORACIO
LEG. 51522 MACINA, VALERIA
LEG. 52894 PALOMANES, DAMIÁN ALBERTO
LEG. 52846 RAMOS, NICOLÁS MARTÍNIntroducción
Este informe aborda el análisis de la variante conocida como “Selección del pivote por Mediana de 3” del algoritmo de ordenamiento “QuickSort”.
El algoritmo básico fue diseñado por C. A. R. Hoare en el año 1960, con su publicación en 1962. Desde entonces ha sido una revolución y se ha convertido en el algoritmo mas utilizado cuando se trata de ordenamiento.
Es muy popularporque es relativamente fácil de implementar, ofrece buenos resultados generales, en muchos casos consume menos recursos que otros método de ordenación, y está bien estudiado (ha sido expuesto a un minucioso análisis matemático que ha sido corroborado con amplia experiencia práctica).
Quicksort en el mejor y peor caso se puede ver que es uno de los mejores métodos de ordenación.
Particularmente, sehablará de la variante “Mediana de 3” desarrollado desde un aspecto algorítmico así como matemático explicando características de la misma.
Contenido
Se conoce como Quicksort a un algoritmo de ordenamiento, también conocido como “método rápido” o de “ordenamiento por participación”. Este algoritmo se basa en la estrategia de “Divide y Vencerás”.
La idea de este algoritmo, consta de:Tomar un elemento x de una posición cualquiera del arreglo.
Tratar de ubicar a x en una posición correcta del arreglo, de forma que todos los elementos que se encuentren a su izquierda sean menores que x, y los de la derecha, mayores.
Repetir los pasos anteriores, pero tomando como subconjunto los conjuntos “menores” y “mayores” a x. Posterior a esto, se sigue realizando repetitivamente estos pasoshasta lograr que la lista de elementos queden ordenados.
Veremos un ejemplo de cómo este algoritmo ordena una lista de números, tomando un pivote al azar y re acomodando las sublistas que aparecen luego de este proceso.
Tenemos una lista formada por 7 números sin ningún orden entre si y lo queremos ordenar de menor a mayor.
Para llevar a cabo este ejemplo, nombraremos con “p” la pivote,“i” el primer elemento y “j” el anterior al pivote, tanto i como j se irán moviendo hacia el centro de la lista, paso por paso.
La lista esta formada por: 5 – 3 – 7 – 6 – 2 – 1 – 4.
Se toma como p, i y j, los siguientes elementos:
[pic]
Comenzaremos comparando el 5 por la izquierda y el 1 por la derecha. 5 es mayor que 4 y 1 es menor, por lo que colocamos el 5 en la derecha (posición j) y el1 por la izquierda (posición i) y avanzamos i a la segunda posición y j a la quinta posición.
[pic]
Como 3 es menor que 4, avanzamos una posición y dejamos al 3 en ese lugar. Como 2 es menor que 4, dejamos en esa posición a j.
[pic]
Ahora continuamos, 7 es mayor que 4 y 2 es menor, por lo que se intercambian ambos números y avanzamos nuevamente.
[pic]
En este momento es en el cualtermina el ciclo principal, cuando i se junta con j, se intercambia el valor “p” por el valor de i, lo cual queda:
[pic]
Como habíamos dicho anteriormente, nos quedan 2 sublistas armadas, la de la izquierda y la de la derecha. La izquierda esta formada por 1 – 3 – 2 y la de la derecha por 7 – 5 – 6, terminaremos el acomodamiento de la primera ya que en ambos lados se continúan los mismospasos.
Tomamos como pivote el 1.
[pic]
Realizamos la comparación, 1 es menor que 2, avanzamos y 3 es mayor, por lo que también avanzamos, como se intercambian los índices, se intercambia i con p, lo que queda:
[pic]
Realizando los mismos pasos de esta sublista con la sublista de la derecha, nos quedaría la lista completamente ordenada, lo cual seria:
[pic]
Técnicas para la...
Leer documento completo
Regístrate para leer el documento completo.