Portada
mis comunidades
otras secciones
#2:
De arrays (listas, como las llama el autor), o de ficheros. Lo que es el sort, vaya.
Aquí teneis el enlace a todos los artículos de la serie que ya son bastantes.
http://eltamiz.com/elcedazo/category/Macluskey/
Aquí teneis el enlace a todos los artículos de la serie que ya son bastantes.
http://eltamiz.com/elcedazo/category/Macluskey/
Comentarios
De arrays (listas, como las llama el autor), o de ficheros. Lo que es el sort, vaya.
Aquí teneis el enlace a todos los artículos de la serie que ya son bastantes.
http://eltamiz.com/elcedazo/category/Macluskey/
#10
Para entender la recursividad primero hay que entender la recursvidad. Te dejo un ejemplo en C++ muy sencillo.
bool entender_recursividad()
#19 Mierda, adiós stack
#20 Cagontó
#12 El método de la burbuja (bubble sort) es una de las implementaciones de sort.
Los hay mejores, pero no me voy a extender porque veo que el artículo explica alguna de ellas (solo me lo he mirado por encima de momento).
Fdo Belfe: Un no tan viejo informático pero que tambien ha tenido que lidiar con eso.
Quicksort en haskell... entender eso es asi como sentir que te enrollas con Alyssa Milano
ofuscacion en estado alarmante, digna del listo de The big bang theory.
el de phyton es incluso peor.
si, me acabo de dar cuenta (tarde) que soy un nerd en estado puro.
#19
Stack overflow
#9: Arreglado. Gracias por el comentario, me había comido la n... y mira que lo he repasado veces...
(en términos técnicos, su complejidad es del orden de O²)
Mis hojos!! Será de O(n²), como bien está escrito en el artículo de wikipedia al que enlaza. Y siendo más precisos, sería Θ(n²)...
#1 De listas en general.
#2 o de ficheros
Nop, para ficheros, lo que es en memoria secundaria, esos algoritmos como que no.
#22 Haskell en realidad es de lo mejorcito para aprender metología de la programación y por eso, sorpresa, se usa mucho para enseñar metodología de la programación.
#31 Jajaja, sí, sí, si lo sé. Pero una cosa es consensuado y otra es demostrado matemáticamente, simplemente que me extrañaba
PD: Mi favorito siempre será: http://en.wikipedia.org/wiki/Bogosort
Meneo ahora, aunque lo leeré más tarde, confiando en la calidad demostrada de los artículos de esta serie (ya iba haciendo falta una historia cotidiana de la informática patria)
#0 Con tu permiso he corregido:
magnifia por magnífica
Aún estoy dándole vueltas a la parte que dice [de Hoare, sobre el Quicksort], que "algún tiempo después, demostró matemáticamente que era el más rápido posible para ordenar listas.".
Me gustaría saber de donde ha salido eso, porque choca con lo que yo sé (o creo saber) sobre ordenación...
Si no recuerdo mal, se ha demostrado que la complejidad mínima del problema de ordenación es O(n log n). El quicksort tiene un caso medio de O(n log n), sí, pero un caso peor de O(n^2). Por tanto, mejor complejidad tiene el Heapsort, que siempre es O(n log n). Pero eso en cuanto a complejidad, que está relacionado con la velocidad, pero no son sinónimos, depende del caso.
Por ejemplo, para listas casi ordenadas el selection sort, de nuevo si no recuerdo mal, es mejor que el quicksort. En cualquier caso, dado que la velocidad depende del impacto de la lista a ordenador, del impacto de la caché y de varias cosas, me pregunto cómo va a hacerse una demostración matemática que demuestre que el quicksort es más rápido...
En fin, tras este rollo aportaré algo interesante: una página con applets que muestran cómo ordenan los diferentes algoritmos (click en los applets para verlos funcionar): http://linux.wku.edu/~lamonml/algor/sort/sort.html
#19 También es importante el concepto condición de parada de la recursividad
¿Es el metodo de ordenación de la burbuja no ?
método de ordenación de arrays, quizás?
Hace tiempo que encontre este video donde se hace una demostracion del algoritmo de quicksort usando una baraja de cartas:
function bool recursividad()
return true && recursividad();
ese creo que no muere por stack oveflow... segun que compilador.
#32 Joder con el Bogosort, jamás lo había visto y a partir de ahora también es mi favorito
#27 A mí me suena que para listas pequeñas es preferible un método directo como puede ser la selección directa debido al menor coste de las operaciones y si encima está casi ordenada como comentas ya ni te cuento. Usar quicksort para esos casos es como matar moscas a cañonazos.
Por lo demás para listas grandes parece que sí está consensuado que lo mejor es quicksort y derivados, que por algo he elegido este nick
#34 lo se, se haskell, y aun sabiendo haskell me parece un codigo turbio, nada mas
Fallo técnico... este comentario no iba aquí : (
¿Para que sirve un ordenador entonces si no ordena nada¿
#7 Empieza hablando de ficheros y base de datos. Luego pasa a hablar de algoritmos para ordenación de memoria principal, ram vamos, para luego rematar comentando en unas líneas otra vez sobre ficheros.
Sí que queda un poco confuso pero aún así se merece un meneo.
#5 Ahí, ahí
Con lo sencillo que es ahora, hacer un c&p del manual (básicamente el QuickSort, a veces recursivo, a ves repetitivo)...
Tengo examen justamente de esto la semana que viene!
Bah, tonterías, donde esté el método shell que se quite todo lo demás
)
(sí, odio los algoritmos recursivos
#25 A mí me enseñaron con Pascal, qué malos recuerdos!!!
#27 El otro día en clase nos comentó el profesor que hay una modificación no trivial del quicksort para elegir la mediana garantizando siempre O (n log n).
Se puede demostrar que un algoritmo es más rápido que otro matemáticamente obteniendo la constante multiplicativa, por ejemplo para dos algoritmos que son O(n), si uno es 1,4 * n, y otro 0,5 * n el segundo es más rápido.
#29 Cierto, lo había olvidado, hay métodos para elegir siempre el pivote óptimo.
En cuanto a hallar la constante multiplicativa... es una aproximación, pero sigues dependiendo de los casos debido a las ramificaciones (ifs) de los algoritmos. Podrás decir si es más rápido en el peor caso, o en el mejor, o en el medio... pero salvo que se estudien todos los caminos posibles y se vea que en todos la constante particularizada es menor, no se puede decir que sea "el más rápido" tal cual. Además, recordemos que la complejidad en los algoritmos de ordenación viene dada por el número de comparaciones, pero pueden ser necesarias otras operaciones que no se estarían teniendo en cuenta, pero sí afectan a la velocidad.
Y aún así, de todos modos, seguiríamos teniendo sólo una velocidad teórica, porque incluso si dos algoritmos hacen N comparaciones, NO da igual en qué orden las hagan, la velocidad puede variar sustancialmente (por la caché, burbujas en la pipeline...).
Uyuyuy, me parece que a nuestro querido Viejo Informático se le ha ido un poco la bola esta vez... está mezclando un programa de ordenación concreto con los algoritmos de ordenación en general, por lo menos al principio. Esta vez se le perdona.
#22 no me jodas, compáralo con la versión C o Python (ya no te digo la de Cobol, madre mía). Con saber un poco la sintaxis de Haskell se explica sólo: el quicksort para una lista compuesta por un elemento y el resto (x:xs), devuelves el quicksort de los elementos menores de x concatenados con x y concatenados con los elementos mayores de x. El quicksort de una lista vacía es igual auna lista vacía.
Noooooooooooooooooooooooooo
Aún sueño con la mezcla polifásica (basada en la serie de Fibonacci) que vimos en una asignatura llamada Ficheros y Bases de Datos. Todavía tengo pesadillas.