Quicksort en listas enlazadas

[Dany Joel Ucañay Barreto]

Buenas tardes. Me gustaria saber si alguien me podria ayudar en este problema que tengo.

Necesito crear un metodo en JAVA que ordene por QUICKSORT una lista enlazada de numeros enteros.

Si alguien pudiese ayudarme le agradeceria bastante.

Atte.

Dany Ucañay Barreto

Cel.: 986479129

[Pwned 0wn!]

http://lc.fie.umich.mx/~calderon/programacion/notas/Quicksort.html
Me parece buen informacion de lo que estas buscando .

[Cesar ALLAIN]

Mira la mejor forma sería guardar los elementos de la lista enlazada en un arreglo de la misma longitud que el número de elementos de la lista en lazada, luego aplicar QuickSort en el arreglo por último regresar estos elementos ordenados a la lista enlazada.

en todo caso la eficiencia sería la de O(n) ya que la eficiencia de Quicksort es de O(n*log(n)) y es menor que O(n).

Otra forma sería utilizando la clase List y ver sus métodos. (Ver también LinkedList y sus derivados).

Espero que te sirva,

Saludos,

César.

2011/10/10 Dany Joel Ucañay Barreto <dad...@hotmail.com>

--
Para enviar mensajes al grupo: sp...@googlegroups.com
Para retirarse del grupo: spc-l-un...@googlegroups.com
Para mas opciones: http://groups.google.com/group/spc-l?hl=es

--
Ing. César Allain Pacheco
Universidad de Piura
WEB:
http://callain.net16.net/

[Dany Joel Ucañay Barreto]

gracias por la ayuda pero creo que ese es una funcion para un array y no para una lista enlazada.

Gracias de todas maneras.

---

Date: Mon, 10 Oct 2011 17:31:32 -0500
Subject: Re: [spc-l] Quicksort en listas enlazadas
From: pwned...@gmail.com
To: sp...@googlegroups.com

http://lc.fie.umich.mx/~calderon/programacion/notas/Quicksort.html
Me parece buen informacion de lo que estas buscando .

[Alfredo Paz-Valderrama]

Si construyes una clases ListaEnlazada con los métodos get y put
adecuados podrías usar la implementación de Quicksort estandar (con
arreglos) usando los índices como argumentos para get y put, pero esto
podría hacer que el costo de búsqueda y modificación sea O(n) y no
O(1) como cuando se usan arreglos. Entonces, la solución de pasar los
elementos a un arreglo, ordenarlos y volver a llenar la lista es la
más razonable. Salvo que el objetivo de la tarea haya sido crear la
clase ListaEnlazada :-)

saludos

2011/10/10 Dany Joel Ucañay Barreto <dad...@hotmail.com>:

> --
> Para enviar mensajes al grupo: sp...@googlegroups.com
> Para retirarse del grupo: spc-l-un...@googlegroups.com
> Para mas opciones: http://groups.google.com/group/spc-l?hl=es

--
Alfredo Paz-Valderrama
Sociedad Peruana de Computación

[Cesar ALLAIN]

ve este link

http://stackoverflow.com/questions/5091168/quick-sort-using-recursion-on-a-linked-list

saludos

cesar.

2011/10/10 Dany Joel Ucañay Barreto <dad...@hotmail.com>

gracias por la ayuda pero creo que ese es una funcion para un array y no para una lista enlazada.

[Mauricio Lopez]

Hola Cesar,
 
Me parece bien que quieras ayudar a Dany, pero deberias informarte minimamente antes de responder porque no sólo no lo estas ayudando, sino que lo estás desinformando.

En primer lugar, el costo asintótico O(n) no es menor que O(n*log(n)) (donde log n es el logaritmo en base 2)
 
Si n > 2 entonces O(n log n) > O(n).
 
Prueba: Si n = 1 entonces log n = 0. y para n = 2, log n = 1. Para n > 2 entonces log n > 1. Por lo tanto n*log(n) > n.
 
En segundo lugar, es una contradiccion decir "en todo caso la eficiencia sería la de O(n)" para ordenar un array con quicksort y luego decir "la eficiencia de Quicksort es de O(n*log(n))".

 

En tercer lugar, la "mejor forma" enunciada no es para nada una solucion al problema de ordenar una lista enlazada.

 

El hecho es que la implementación de QuickSort requiere de una E.D. de acceso aleatorio y en general una lista enlazada es una E.D. de acceso secuencial. Lo que recomiendo es construir un indice de acceso aleatorio para la lista enlazada.

 

 

Saludos,

Mauricio

 

---

Date: Mon, 10 Oct 2011 18:26:12 -0500

Subject: Re: [spc-l] Quicksort en listas enlazadas

From: cal...@gmail.com
To: sp...@googlegroups.com

[Dany Joel Ucañay Barreto]

Muchas gracias Mauricio.
Tomare ne cuenta tu aporte. Estamos en contacto.

Atte.
Dany Joel Ucañay Barreto
Cel.: 986479129

---

From: skull...@hotmail.com
To: sp...@googlegroups.com
Subject: RE: [spc-l] Quicksort en listas enlazadas
Date: Mon, 10 Oct 2011 23:13:21 -0500

[Camilo Thorne]

Quicksort es O(n^2) en *tiempo* y O(n*log(n)) en *espacio*.

(N.B. O(n) < O(n*log(n)) - y no el contrario, creo que la inecuacion es obvia :-)).

Wikipedia resume bien las principales propiedades de los algos de sorting:

http://en.wikipedia.org/wiki/Sorting_algorithm

Buena suerte!

2011/10/11 Cesar ALLAIN <cal...@gmail.com>

--
Camilo Thorne

Research Fellow
KRDB Research Centre for Knowledge and Data
Free University of Bozen-Bolzano
3, Piazza Domenicani
39100,Bolzano, Italy
tel:  (+39)0471016123
fax: (+39)0471016009
http://www.inf.unibz.it/~cathorne

"Exegi monumentum aere perennius" 

(Horatius, Ode III-30)

[Victor Laguna]

De acuerdo con Alfredo.

Me pregunto si alguna implementación del Quicksort para ordenar una lista enlazada continua siendo O(n^2). Dado que una lista enlazada no tiene acceso aleatorio a sus elementos, me parece implementaciones tradicionales podrian dar como peor caso O(n^3).

Yo recomendaria el uso del Merge Sort, que tiene buen desempeño en "contenedores" con acceso secuencial.

Saludos!
Víctor Laguna

[Cesar ALLAIN]

Si, si,

Fue un lapsus

en realidad si calculas para n=10 o más te das cuenta que n*log n > n. Además no necesariamente tiene que ser base dos del logaritmo. Otra cosa: con la mejor forma, quise decir que si el objetivo es ordenar con quicksort pues la solución sería más fácil utilizando arreglos.

La idea de crear un indice de acceso aleatorio me parece bien, ¿cómo implementarlo? de todas maneras te topas con operaciones de inserción y eliminación en listas enlazadas.

Saludos,

César.

2011/10/10 Mauricio Lopez <skull...@hotmail.com>

[Abraham Santos]

El link enviado por Cesar ALLAIN es correcto. Quicksort no requiere que la estructura sea de acceso aleatorio si el pivote se toma del inicio o el final, y como el algoritmo recorre iterativamente desde el inicio y desde el final para colocar el pivote en su ubicación correcta lo único necesario es que se trate de una lista doblemente enlazada. El número de comparaciones es aproximadamente N log N.

Saludos.

2011/10/11 Cesar ALLAIN <cal...@gmail.com>

[Manuel Bellido]

Estimados,

El link enviado por Cesar ALLAIN es correcto. Quicksort no requiere que la estructura sea de acceso aleatorio si el pivote se toma del inicio o el final, y como el algoritmo recorre iterativamente desde el inicio y desde el final para colocar el pivote en su ubicación correcta lo único necesario es que se trate de una lista doblemente enlazada. El número de comparaciones es aproximadamente N log N.

Saludos.

Y para evitar que se haga N^2, hay que verificar que no este ordenado. Se podría 'desordenar' la lista antes de aplicar el quicksort para asegurar que el comportamiento sea NlogN.

Saludos

[Victor Laguna]

Buen punto. Si se escoge el pivot en alguno de los extremos, se podria recorrer secuencialmente la lista en cada paso del quicksort.

Saludos

[Harry Guillermo]

Si el espacio/memoria no es problema (space complexity) estoy de acuerdo con Cesar. La mejor forma tiene que ser leer la lista y pasarlo a un array( O(n)), luego ordernar el arreglo usando quicksort (O(nlogn)) y finalmente actualizar la lista usando el arreglo (O(n)). Lo cual es basicamente O(n+nlogn+n)=O(2n+nlogn), pero como se eliminan constantes nos queda O(n+nlogn) y cuando n->infinito entonces se reduce a O(nlogn). Porque?  porque los valores grandes absorven los mas pequeños. n*n absorve n verdad? n no tiene mucha importancia cuando tu algoritmo en otra parte va a requerir n*n. (a menos que mi memoria me este fallando mi idea tiene que estar bien :) )

Si el espacio es importante entonces si que el problema se complica y habría que tomar la idea de Mauricio o algo similar. Pero parece ser que Dany no tiene problemas de espacio entonces mas facil todo. Ademas en estos tiempos la memoria es mas barata que el tiempo. Por ejemplo podríamos usar external sort si n es muy grande. Al final la mejor solución sigue siendo O(nlogn) en mi opinión.

Saludos,

Harry

SkypeId: harryguillermo
Web page: http://www.harryguillermo.com/

---

From: Victor Laguna <elvi...@gmail.com>
To: sp...@googlegroups.com
Sent: Tuesday, October 11, 2011 9:21 AM

Subject: Re: [spc-l] Quicksort en listas enlazadas

[Alfredo Paz-Valderrama]

Muy buen punto!

saludos

2011/10/11 Abraham Santos <amsa...@gmail.com>:

--

[Eduardo Morales]

El link http://stackoverflow.com/questions/5091168/quick-sort-using-recursion-on-a-linked-list

 enviado por ALLAIN no es correcto.

Ignorando que el codigo tiene un bug y el autor esta pidiendo ayuda. 

Ese codigo corre en tiempo promedio O(n^2). No importa el nombre que le pongan, ese codigo no es quicksort.

Si tienes un link list lo mejor que puedes usar es un merge sort. No solo lo digo yo, sino tambien wikipedia :)

y la pregunta que se ha debido hacer desde un principio. Por que estas usando un linked list? En mi experiencia son muy pocos los casos en los que realmente se necesita un linked list en lugar de un array.

2011/10/11 Alfredo Paz-Valderrama <alfre...@gmail.com>

--
Eduardo Morales

[Manuel Bellido]

En el capítulo 7 del libro: "Introduction to Algorithms"  (CLRS) 3ra ed., explica el algoritmo del quicksort randomizado que tiene como tiempo algorítmico O(nlogn).

Para el caso de una lista enlazada, basta elegir uno de los extremos como pivot pero se debe asegura que esta selección no sea en orden (randomizada) ya que el tiempo se hace O(n^2).

Saludos 

Manuel Bellido

2011/10/12 Eduardo Morales <eduardo...@gmail.com>

[Guillermo Medina]

Dany:

En el siguiente link http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/ podrás ver un index sobre varios Video Lectures al libro de cabecera de análisis de algoritmos que hacer referencia Manuel. Dado que tu inquietud es sobre el algoritmo de ordenamiento Quicksort, lo recomendable es que mires el video Lecture 4: Quicksort, Randomized Algorithms. También en este otro enlace http://books.google.com/books?id=NLngYyWFl_YC&printsec=frontcover&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false está on-line el capítulo siete del mismo libro y podrás leer más al respecto.

Existen otros algoritmos de ordenamiento como: Merge sort, head sort, buble sort, etc. El elegir uno y no el otro dependerá del problema a resolver.

Saludos,

Guillermo Medina

[Eduardo Morales]

De acuerdo... si es que estamos hablando de quicksort. Pero no es asi.

Ese codigo *no* implementa quicksort. Se parece pero no es. No es quicksort.

Ese codigo corre en tiempo *promedio* O(n^2).  Quicksort corre en O(nlogn).

Ese codigo no va a correr en O(nlogn). Never.

Ahora, no estoy diciendo que no se puede implementar quicksort para un link list. Se puede, pero no es la mejor opcion.

2011/10/12 Manuel Bellido <manub...@gmail.com>

--
Eduardo Morales

[Cesar ALLAIN]

Humm... 

No se si Wikipedia - el Internet- sea una buena referencia o por decirlo de otra manera, el que tiene la última palabra. Sería mejor buscarse un buen libro de algún autor de renombre para usarlo como referencia.

En los vídeos de Standford, al cual hacen referencia en esta cadena, es una buena ayuda. 

según mi humilde opinión el mejor algoritmo de ordenamiento es una combinación de quicksort + burbuja. Quicksort trabaja muy bien con cantidades de catos enormes y su mejor performance en cuando estas están desordenadas, luego cuando las particiones que genera quicksort, llegan a la cantidad de 100 elementos, ya estan casi ordenados y es ese momento se puede aplicar el método de la burbuja el cual con arreglos de tamaño igual a 100 trabaja muy eficientemente.

Por otra parte lo de utilizar una lista enlazada para imlementar quicksort no me parece la mas adecuada.

Finalmente, me parece muy gratificante este intercambio de ideas, siempre y cuando el fin sea aclarar las cosas. recordar siempre que "nadie sabe todo". 

Un saludo cordial,

César.

2011/10/12 Eduardo Morales <eduardo...@gmail.com>

[Abraham Santos]

El link, en efecto no era el quicksort para una lista doblemente enlazada... mi error.

Ya había indicado como era el quicksort no randomizado para una lista doblemente enlazada, ahora solo comento unos detalles adicionales.

Aquí hay dos cosas diferentes el costo en el peor caso (la cota superior del algoritmo) y el costo promedio. El quicksort randomizado tiene un desempeño en el peor caso de N^2 (lo cual es un caso raro) pero su costo promedio para todas las posibles permutaciones de entrada es N log N.

Tomando el caso de una lista doblemente enlazada en la que no elegimos un pivote aleatoriamente, el costo en el peor caso es N^2 pero el costo promedio sigue siendo N log N.

Lo cito de wikipedia:

"Even if pivots aren't chosen randomly, quicksort still requires only O(n log n) time averaged over all possible permutations of its input. Because this average is simply the sum of the times over all permutations of the input divided by n factorial, it's equivalent to choosing a random permutation of the input. When we do this, the pivot choices are essentially random, leading to an algorithm with the same running time as randomized quicksort."

Por supuesto, aún cuando el costo promedio de ambos es N log N merge sort se desempeña significativamente mejor que quicksort en listas.

"Merge sort is more efficient than quick sort for some types of lists if the data to be sorted can only be efficiently accessed sequentially, and is thus popular in languages such as Lisp, where sequentially accessed data structures are very common. Unlike some (efficient) implementations of quicksort, merge sort is a stable sort as long as the merge operation is implemented properly."

2011/10/12 Eduardo Morales <eduardo...@gmail.com>

[ARTURO LLAJA ALARCÓN]

Espero te sirva esto:

http://www.sorting-algorithms.com/

--

[pmendozav]

Acomodar el quicksort es como que perder el tiempo si es que puedes usar el mismo codigo con listas sin cambiar nada.
EN C++ PUEDES SOBRECARGAR LOS OPERADORES... ASI PUEDES USAR TU QUICKSORT PARA ARREGLOS EN LISTAS ENLAZADAS SIN HACER NINGUNA MODIFICACION AL PROGRAMA.. VE SI EN JAVA PUEDES HACER LO MISMO.. ¿Como?.. tu tarea, solo es un dato