{"id":520,"date":"2007-05-17T10:36:27","date_gmt":"2007-05-17T17:36:27","guid":{"rendered":"http:\/\/www.gubatron.com\/blog\/2007\/05\/17\/recordando-algoritmos-quicksort\/"},"modified":"2007-05-17T10:36:27","modified_gmt":"2007-05-17T17:36:27","slug":"recordando-algoritmos-quicksort","status":"publish","type":"post","link":"https:\/\/www.gubatron.com\/blog\/recordando-algoritmos-quicksort\/","title":{"rendered":"Recordando algoritmos, Quicksort"},"content":{"rendered":"<p>Leyendo no se que en internet, lei mencionar algo sobre preguntas de entrevistas de trabajo, y mencionaron que siempre es bueno saber como funciona Quicksort. Por algun motivo, el algoritmo de ordenamiento que siempre recuerdo es Bubble sort, pero todos sabemos que no es el mejor. So decidi repasar y <a href=\"http:\/\/en.wikipedia.org\/wiki\/Quicksort\">leer como funciona quicksort<\/a>.<\/p>\n<p>Para los que no recuerdan quicksort es simplemente hacer 3 listas con la lista principal [PRINCIPAL]. Estas listas se generan bajo un criterio bien sencillo. Elige un numero cualquiera del arreglo, la primera lista tendra todos los numeros menores a ese numero [MENORES]. La segunda lista tendra todos los numeros que sean de igual valor a ese numero [IGUALES], y la tercera los mayores [MAYORES].<\/p>\n<p>Una vez que tienes estas 3 listas, el resultado de Quicksort es el siquiente (Donde ++ es concatenar una lista):<\/p>\n<blockquote><p>Quicksort([MENORES]) ++ [IGUALES] ++ Quicksort([MAYORES])<\/p><\/blockquote>\n<p>Como veras, el algoritmo es recursivo, y llegara el momento que no encuentres numeros menores, iguales o mayores, asi que cuando Quicksort recibe una lista de un solo elemento, devuelve ese elemento.<\/p>\n<p>En python esto sale en 4 lineas con list comprehension, literalmente:<\/p>\n<pre>\ndef qs(lista):\n   if len(lista) <= 1: return lista\n   p = lista[0] #el pivote\n   return qs([x for x in lista if x < p]) + [x for x in lista if x == p] + qs([x for x in lista if x > p])\n<\/pre>\n<p>Pudieras aplicar este algoritmo a cualquier tipo de objeto en Python si para ese objeto defines las funciones de comparacion.<br \/>\nDemasiado arrecho, viva python.<\/p>\n<p>PS: Despues de escribir esto, encontre una implementacion aun mas corta, en la que no utilizan list comprehension, utilizan<br \/>\nfunciones lambda, en vez de hacer [x for x in lista if x < pivote] hacen  filter(lambda x,y=pivote: x < y,lista), eso devuelve los elementos que cumplen con la funcion lambda en la lista, es decir   filter(funcion, lista)\n<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Leyendo no se que en internet, lei mencionar algo sobre preguntas de entrevistas de trabajo, y mencionaron que siempre es bueno saber como funciona Quicksort. Por algun motivo, el algoritmo de ordenamiento que siempre recuerdo es Bubble sort, pero todos sabemos que no es el mejor. So decidi repasar y leer como funciona quicksort. Para [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[15,30,43,65],"tags":[],"class_list":["post-520","post","type-post","status-publish","format-standard","hentry","category-code","category-geeklife","category-linux","category-python"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p5Unzf-8o","jetpack-related-posts":[{"id":422,"url":"https:\/\/www.gubatron.com\/blog\/comunidad-de-jugadores-venezolanos-de-xbox-live\/","url_meta":{"origin":520,"position":0},"title":"Comunidad de jugadores venezolanos de XBOX Live","author":"gubatron","date":"December 26, 2006","format":false,"excerpt":"Para los venezolanos que recien se compraron un Xbox 360 y tienen una cuenta en XBOX live, unete a nosotros en esta comunidad de Venezolanos. Habemos muchos jugando Gears of War, Call of Duty 3, Rainbow Six Vegas, Need for Speed Carbon... Jugar y hablar en \"Venezolano\" siempre sera lo\u2026","rel":"","context":"In &quot;Geeklife&quot;","block_context":{"text":"Geeklife","link":"https:\/\/www.gubatron.com\/blog\/category\/geeklife\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":582,"url":"https:\/\/www.gubatron.com\/blog\/linuxcomo-copiar-un-archivo-a-multiples-ubicaciones-con-un-solo-comando\/","url_meta":{"origin":520,"position":1},"title":"Linux: Como copiar un archivo a multiples ubicaciones con un solo comando","author":"gubatron","date":"August 29, 2007","format":false,"excerpt":"Aprovecho la ocasion para ilustrar un poco el poder del bash a los amigos que recien se unen al mundo de linux. Muchas veces tienes que hacer operaciones en las cuales tienes que tocar multiples archivos, por ejemplo, remplazar un archivo en varios lugares. Yendo a un ejemplo concreto, El\u2026","rel":"","context":"In &quot;Geeklife&quot;","block_context":{"text":"Geeklife","link":"https:\/\/www.gubatron.com\/blog\/category\/geeklife\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":179,"url":"https:\/\/www.gubatron.com\/blog\/consejos-para-nuevos-estudiantes-de-ingenieria\/","url_meta":{"origin":520,"position":2},"title":"Consejos para nuevos estudiantes de Ingenieria","author":"gubatron","date":"July 29, 2005","format":false,"excerpt":"Un primo muy querido acaba de entrar a la universidad para estudiar Ingenieria Inform\u00e1tica, no se imaginaran el orgullo que me ha provocado. Ma\u00f1ana es su primer dia de clases (En Bogot\u00e1, que rico) y supongo que hoy poco dormir\u00e1 de la emoci\u00f3n, ya que le cost\u00f3 mucho llegar a\u2026","rel":"","context":"In &quot;Gubatron&quot;","block_context":{"text":"Gubatron","link":"https:\/\/www.gubatron.com\/blog\/category\/gubatron\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":16,"url":"https:\/\/www.gubatron.com\/blog\/c-serializando-una-lista-de-objetos-en-un-stream\/","url_meta":{"origin":520,"position":3},"title":"C++ Serializando una Lista de Objetos en un Stream","author":"gubatron","date":"October 24, 2004","format":false,"excerpt":"En la nueva implementacion de Filenger 2, fue necesario implementar serializacion de una lista. Para guardar todos los mensajes en un archivo. La idea es hacer algo asi: QValueList<Message> listaDeMensajes; ... stream << listaDeMensajes; \/\/Escribe en el stream cada mensajes. Pero las cosas no son tan sencillas, eso da un\u2026","rel":"","context":"In &quot;Gubatron&quot;","block_context":{"text":"Gubatron","link":"https:\/\/www.gubatron.com\/blog\/category\/gubatron\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":85,"url":"https:\/\/www.gubatron.com\/blog\/2-programitas-utiles-mientras-desarrollas-en-linux\/","url_meta":{"origin":520,"position":4},"title":"2 programitas utiles mientras desarrollas en Linux","author":"gubatron","date":"December 29, 2004","format":false,"excerpt":"Para los desarrolladores que utilizan lenguajes de programacion como Perl, o PHP, a continuacion, un programita bien util. Supon que tienes un archivo .php donde tienes definidas un monton de funciones. Y no te acuerdas que funciones estaban ahi, lo mas probable es que tengas que abrir el archivo y\u2026","rel":"","context":"In &quot;Gubatron&quot;","block_context":{"text":"Gubatron","link":"https:\/\/www.gubatron.com\/blog\/category\/gubatron\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":360,"url":"https:\/\/www.gubatron.com\/blog\/como-matar-varios-procesos-cuando-killall-no-es-una-opcion\/","url_meta":{"origin":520,"position":5},"title":"Como matar varios procesos cuando killall no es una opcion.","author":"gubatron","date":"August 15, 2006","format":false,"excerpt":"A veces tienes un cronjob que se queda pegado por mucho rato, cuando haces Code: ps aux | grep miPrograma tienes un monton de instancias pegadas!! Intentas hacer killall miPrograma pero no funciona porque quizas es un programa que estas arrancando con un interprete, como python, o php, o perl.\u2026","rel":"","context":"In &quot;Geeklife&quot;","block_context":{"text":"Geeklife","link":"https:\/\/www.gubatron.com\/blog\/category\/geeklife\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/posts\/520","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/comments?post=520"}],"version-history":[{"count":0,"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/posts\/520\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/media?parent=520"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/categories?post=520"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.gubatron.com\/blog\/wp-json\/wp\/v2\/tags?post=520"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}