Discusión:Algoritmo de ordenamiento

Merge ¿apareamiento o intercalación?[editar]

Hice una corrección de la traducción, dado que, antes, algunas frases no tenían sentido.

Con respecto a los términos en inglés: En mi cátedra de algoritmos no es una práctica común traducir el nombre. Excepto por burbuja y burbuja refinada el resto, por ej: quicksort no tienen traducción, eran presentados por su nombre original en inglés.

Lamentablemente la bibliografía que poseo también está en inglés, motivo por el cual, si es que existe una nomenclatura estándar (aceptada mayoritariamente) para estos algoritmos, utilizada en universidades de habla hispana por favor que lo diga. De otra manera, por favor dejar los términos en inglés.

Una sugerencia es que cuando se creen los artículos sobre cada uno de los algoritmos listados, se agregue una imagen del diagrama o en su defecto un enlace a algún sitio que contenga dicho material.

Moriel 17:08 2 may, 2004 (CEST)

no pa tas ekibokao'

No me queda claro lo de "frases que no tenían sentido". Yo puse

En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista en un cierto orden. Para números habitualmente se usa el orden numérico y para caracteres el orden lexicográfico.

y tú tradujiste en forma más o menos literal

En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista en un cierto orden. generalmente lexícográfico.

Como traducción la tuya está mejor, pero de lo que se trata es tener un buen artículo, y los números nunca se ordenan en orden lexicográfico. Por otra parte, no me queda nada de claro lo que es el apareo. Fui a leer el original en inglés y vi que era merge. Antes yo había sacado merge de la traducción porque pensé que no aportaba, y ahora sigo pensándolo con más razón, ya que "apareo" no se entiende.

Ordenar eficientemente es importante para posteriormente usar en forma eficiente otros algoritmos como los de búsqueda y apareo

Si se da un ejemplo o se dan dos, debería dar más o menos lo mismo. Pero si el segundo ejemplo no se entiende, entonces se puede sacar.

Con respecto a no traducir quicksort, radix sort, etc., estamos de acuerdo.

Pablo.cl 05:14 10 may, 2004 (CEST)

Pablo.cl:

Sin intención de ofenderte, la verdad es que no sé cuánto entendés de matemáticas y computación. Decir que los números normalmente se ordenan numéricamente es un tanto trivial (por no decir otra cosa). Si tenés en claro el concepto de orden matemático te das cuenta que el punto en cuestión es que la relación entre ciertos elementos abstractos debe cumplir con ciertas propiedades. Si se trata de animales, palabras, números o asteroides no es el punto central. Un orden lexicográfico es simplemente un ejemplo de orden matemático útil para el campo de la informática. Y por este motivo es que dice generalmente lexicográfico. El punto central es que debe tratarse de un buen orden (matematicamente hablando: que todo subconjunto posible del conjunto sobre el que está definida la relación binaria debe tener primer elemento).

En cuanto a merge, la traducción que mis profesores de algoritmos utilizaban es apareo y en ocasiones lo he visto como apareamiento. Si crees que el tema w:en:Merge algorithm no aporta nada, de nuevo me asombras, porque ordenamiento, búsqueda y apareamiento son temas centrales de un curso básico de algoritmos.

Otra cosa: ando bastante ocupada y no tengo tiempo para revisar lo que modificas así que te haces responsable de la desinformación que hayas agregado (y/o pienses agregar) en el artículo. Moriel 07:03 12 may, 2004 (CEST)

Moriel:

a.1 >Un orden lexicográfico es simplemente un ejemplo de orden matemático útil para el campo de la informática.

Y el orden numérico es de hecho más importante. El orden numérico ordena 2, 3, 10, 125, 230. El orden lexicográfico ordena 10, 125, 2, 230, 3. Decir que generalmente se usa el orden lexicográfico me parece una exageración.

a.2 >Si crees que el tema w:en:Merge algorithm no aporta nada, de nuevo me asombras

Yo dije otra cosa

Ordenar eficientemente es importante para posteriormente usar en forma eficiente otros algoritmos como los de búsqueda y apareo

Si se da un ejemplo o se dan dos, debería dar más o menos lo mismo. Pero si el segundo ejemplo no se entiende, entonces se puede sacar.

a.3 Siendo más detallista, vemos que es falso que Ordenar eficientemente es importante para posteriormente usar en forma eficiente otros algoritmos como los de [...] apareo. La mezcla de listas ordenadas es usada para ordenar, y no al revés.

a.4 ¿Por qué borraste el orden por inserción que yo había puesto?

a.5 Con respecto a la palabra apareo yo lo he visto como traducción de matching. No veo qué apareo puede haber en Merge({5, 12, 43, 86}, {7, 93}) = {5, 7, 12, 43, 86, 93}

aparear es, según la Real Academia

1. tr. Arreglar o ajustar una cosa con otra, de forma que queden iguales.

2. tr. Unir o juntar una cosa con otra, formando par. U. t. c. prnl.

merge es, según The American Heritage Dictionary

v. tr.

To cause to be absorbed, especially in gradual stages.

To combine or unite: merging two sets of data.

v. intr.

To blend together, especially in gradual stages.

To become combined or united. See Synonyms at mix.

En otras palabras, merge es mezclar, no aparear.

En Google -site:wikipedia.org

apareo merge-sort = 0 / apareamiento merge-sort = 2 / mezcla merge-sort = 114
apareo-de-archivos-ordenados = 0 / apareamiento-de-archivos-ordenados = 0 / mezcla-de-archivos-ordenados = 10
apareo-de-ficheros-ordenados = 0 / apareamiento-de-ficheros-ordenados = 0 / mezcla-de-ficheros-ordenados = 4
algoritmo-de-apareo = 2 / algoritmo de apareamiento = 0 / algoritmo-de-mezcla = 45

a.6 >Otra cosa: ando bastante ocupada y no tengo tiempo para revisar lo que modificas así que te haces responsable de la desinformación que hayas agregado (y/o pienses agregar) en el artículo

Estas palabras son algo contradictorias con lo que pusiste al principio: "Sin intención de ofenderte". Pero veo que esta frase se aplicaba sólo al primer párrafo. Por mi parte, estoy seguro que no he agregado desinformación, y en cambio tú estás poniendo ejemplos poco claros (y que no se ajustan totalmente a la verdad) y usando nomenclatura poco común.

Pablo.cl 00:59 16 may, 2004 (CEST)

Merge Algorithm != Merge Sort

Merge Algorithm == Merge Sort + otros Merge Algorithms

Merge Sort == Algoritmo de Ordenamiento por Fusion o por Mezcla o por Apareo (todos sinonimos, igualmente poco comunes en google, en comparacion con Merge Sort)

Algoritmo de Apareo = Merge Algorithm

Sauron 22:01 16 may, 2004 (CEST)

Pablo.cl:

1- Bueno, veo que al menos has quitado tu frase graciosa: los números normalmente se ordenan numéricamente.

2- Como Sauron acota w:en:Merge algorithm y w:en:Merge sort no son lo mismo. O sea que lo que decís en el punto 3 es falso.

3- Mientras que no me opongo a que se haga una descripción elemental del algoritmo, por ejemplo utilizando un mazo de cartas, no tiene sentido hablar de la complejidad computacional usando ese ejemplo, ¿o es que acaso la complejidad la deducís mirando el mazo de cartas? Créase o no, la complejidad computacional tiene fundamentos matemáticos bastante complejos y no se deducen mirando el mazo de cartas o consultando a la RAE. En definitiva, una de las dos: el ejemplo explicado seriamente (quizás utilizando pseudocódigo o diagrama) o tratado elementalmente de principio a fin. Moriel 22:35 16 may, 2004 (CEST)

Sauron:

No creo que Algoritmo de Apareo = Merge Algorithm

Apareo tiene mucho más que ver con matching que con merge.

Mi cita (no sé si sea una página muy confiable, pero ahí está).

SPANISH TECHNICAL TERMS

pattern patrón

pattern matching apareamiento de patrones

Espero tu cita donde se use apareo o apareamiento en el sentido de merge

Pablo.cl 04:59 18 may, 2004 (CEST)

El punto es que algoritmos de merge, asi como los de busqueda, necesitan de listas ordenadas para operar. Lo que me parecio fue que confundiste algoritmos de merge (una clase de algoritmos) con merge-sort (un ejemplo de la clase de algoritmos de merge) y todo el divague y googling que sigue no tiene nada que ver con el punto en cuestion.

Sauron 05:53 18 may, 2004 (CEST)

Yo hablo de una cosa y tú contestas de otra. En esta sección sólo me concentré en el tema de las palabras "apareo" y "apareamiento" que yo dije que no se entendían. Es muy fácil atacar el tema de la nomenclatura, que ya estaba superado, sin abordar el problema de lógica.

El otro tema lo abordé en el punto a.3 y b.2 y en él el googling no tiene nada que ver. Para "descontaminar" el tema de fondo del de la nomenclatura, te contesto al final, reescribiendo mis argumentos del punto b.2.

Pablo.cl 05:19 19 may, 2004 (CEST)

Moriel.

b.1 En primer lugar, es lamentable que no puedas controlar tu agresividad. Lo que debió ser un simple intercambio de opiniones se transformó en una serie de descalificaciones de tu parte, que en todo caso creo que perjudican más tu imagen que la mía.

b.2 Con respecto a mi punto 3 anterior, tú afirmas y yo niego que

Ordenar eficientemente es importante para posteriormente usar en forma eficiente otros algoritmos como los de merge.

Lo primero, hay que tomar en cuenta tu acotación y la de Sauron que w:en:Merge algorithm y w:en:Merge sort no son lo mismo. Yo no sólo estaba consciente de esto sino que además me había preocupado de leer w:en:Merge algorithm.

Merge algorithms are a family of algorithms that run sequentially over multiple sorted lists, typically producing more sorted lists as output.

Tendrán que concederme que merge (A, B, C, D) produce una lista ordenada, y que por lo tanto el algoritmo de merge se usa para ordenar (pero no es el merge sort).

Veamos ahora como queda la frase

Ordenar eficientemente es importante para posteriormente tomar listas ordenadas en forma secuencial y producir una lista ordenada en la salida.

Si quiero hacer un algoritmo de búsqueda, necesito ordenar eficientemente.
Si quiero hacer un algoritmo de canonicalización, necesito ordenar eficientemente.
Si quiero hacer un algoritmo de merge ¿necesito ordenar eficientemente? No, porque las listas ya vienen ordenadas.

b.3 Con respecto a tu punto 3, lamento tu actitud descalificatoria. En vez de hacer una colaboración (la esencia de la Wikipedia), tú lo transformas en una competencia de quién tiene la razón. Y por lo tanto, si caigo en tu juego, en vez de tratar de hacer un mejor artículo voy a tratar de convencerte de que estás equivocada.

>no tiene sentido hablar de la complejidad computacional usando ese ejemplo

Aunque yo creo que sí tiene sentido, de hecho no lo hice. Lo único que hice fue poner

Aunque este algoritmo es más eficiente que el orden de la burbuja, es muy ineficiente al compararlo con los algoritmos como quicksort

El original decía

Although this algorithm is more efficient than the Bubble sort, it is still inefficient compared to many other sort algorithms since it, and bubble sort, move elements only one position at a time.

b.4 Estoy en desacuerdo con no modificar merge hasta encontrar un consenso serio. Si tú dices que el ejemplo es relevante y yo digo que no, debería omitirse hasta que haya un consenso serio de que el ejemplo corresponde. Por lo demás se trata sólo de un ejemplo, y la referencia a merge igual va a estar en el capítulo de merge sort.

b.5
>1- Bueno, veo que al menos has quitado tu frase graciosa: los números normalmente se ordenan numéricamente.

En vez de hacer algo colaborativo tú lo haces burlesco. Quizás mi frase era graciosa pero real. La manera más obvia de ordenar es numéricamente. El orden lexicográfico no es algo natural.

Pablo.cl 05:33 18 may, 2004 (CEST)

Bueno, ya somos dos que pensamos que estás divagando. Lo peor de todo es que cada vez agregás más divagues para tratar de justificar tus ediciones. Si no valorás tu tiempo, lo lamento por ti pero yo me reservo el derecho de dar por terminada esta discusión. Moriel 08:18 18 may, 2004 (CEST)

Sauron

Veamos aquí el problema de fondo.

Yo dije

Si quiero hacer un algoritmo de merge ¿necesito ordenar eficientemente? No, porque las listas ya vienen ordenadas.

Y tú contestaste

El punto es que algoritmos de merge, asi como los de busqueda, necesitan de listas ordenadas para operar. Lo que me parecio fue que confundiste algoritmos de merge (una clase de algoritmos) con merge-sort (un ejemplo de la clase de algoritmos de merge)

El punto es levemente diferente. Obviamente el algoritmo de merge necesita de listas ordenadas para operar, pero la frase

Ordenar eficientemente es importante para hacer un algoritmo de merge en forma eficiente

es un argumento circular. Los algoritmos de merge son lineales, y ellos en sí no ordenan. Si tengo un ordenamiento n² y otro n log n, mi algoritmo de merge no va a mejorar en nada.

Ordenamiento cuadrático + búsquedas lineales = cuadrático

Ordenamiento n log n + búsquedas lineales = n log n

Ordenamiento cuadrático + merge lineal = ...

¿Pero para qué queremos el merge? Para ordenar. El razonamiento es circular.

Pablo.cl 05:20 19 may, 2004 (CEST)

NO. No queremos el merge para ordenar. El merge-sort si, pero los algoritmos de merge en general NO.

Repito: LOS ALGORITMOS DE MERGE NO SON TODOS ALGORITMOS DE ORDENAMIENTO. UNO de los algoritmos de merge, es el merge-sort y este "lo queremos para ordenar".

OTROS algoritmos de merge hacen otras cosas que no es necesariamente ordenar. Por ejemplo, listar todos los registros que son comunes a 2 listas y otros que podes ver en http://en.wikipedia.org/wiki/Merge_algorithm

Sauron 06:04 19 may, 2004 (CEST)

Por fin estás razonando, pero igual te exasperas. No veo la razón de enojarse tanto en lugar de explicar calmadamente.

Pablo.cl 05:17 20 may, 2004 (CEST)

Razonar siempre lo hice. Lo que no tengo es paciencia para repetir lo mismo a alguien que no quiere escuchar lo que dicen los otros... Sauron 05:47 20 may, 2004 (CEST)

Lamento que digas que soy "alguien que no quiere escuchar lo que dicen los otros". El problema es que no nos estábamos entendiendo mutuamente, pero tú y Moriel inmediatamente supusieron mala fe de mi parte.

Tradicionalmente "merge algorithms" significa "las diferentes variaciones del algoritmo de intercalación de listas", pero la wikipedia en inglés además incluye lo que podríamos llamar algoritmos de apareo o algoritmos de comparación de listas. Si me dicen que el ordenamiento es necesario para el merge=apareo, yo me confundo. Si me dicen que el ordenamiento es necesario para la comparación de listas = apareo, estoy de acuerdo.

Pablo.cl 03:53 24 may, 2004 (CEST)

Exponencial y polinomial[editar]

Sauron:

Primero un detalle. Tú dijiste

(=Clasificación= es confuso decir que la peor complejidad posible es O^2 y mencionar un ejemplo que es O^3)

La verdad es que yo no dije la peor complejidad posible sino los algoritmos más simples. La frase la peor complejidad posible no tiene sentido. Siempre es posible calcular el n^ésimo primo de Mersenne antes de hacer cualquier cosa.

Pablo.cl 06:09 26 may, 2004 (CEST)

Ahora quiero hablar de un par de conceptos que tú agregaste (en rojo)

complejidad computacional (peor caso, caso promedio y mejor caso) en términos de n, el tamaño de la lista. Para esto se usa el concepto de orden de una función y se usa la notación O(n). El mejor comportamiento para ordenar (si no se aprovecha la estructura de las claves) es O(n log n), o sea logarítmicos. Los algoritmos más simples son exponenciales, como O(n²).

Lo habitual es llamarle logarítmico a log n, no a n log n. Por otra parte, exponencial se refiere a 2ⁿ. n² es llamado habitualmente polinomial o más específicamente, cuadrático.

Busqué en Google exponencial n-log-n y las dos primeras páginas resultaron ser las siguientes.

http://w3.mor.itesm.mx/~optimiza/opti9901/capa2/complejidad.html

En la actualidad hay un acuerdo general entre los investigadores de que un algoritmo es de utilidad práctica cuando su complejidad computacional crece polinomialmente con respecto del tamaño de la entrada, por ejemplo, algoritmos de complejidad O(n) o O(n³). Naturalmente, algoritmos para los cuales la complejidad asintótica no es un polinomio en sí pero puede ser acotada por un polinomio también están incluidos (n^2.5, n log n)
[...]
Se le da el nombre de algoritmo exponencial a todo aquel que viola todo acotamiento polinomial para instancias suficientemente grandes.

http://sai.azc.uam.mx/apoyodidactico/pa/Unidad7/pauni7.html

La función f(n) puede ser de varios tipos, algunos frecuentes son:

f(n)=1. Constante.

f(n)=n. Lineal.

f(n)=n². Cuadrático.

f(n)=n^m. Polinomial de grado m.

f(n)=log n. Logarítmico.

f(n)=n log n.

f(n)=2ⁿ. Exponencial de base 2.

f(n)=mⁿ. Exponencial de base m.

Pablo.cl 06:09 26 may, 2004 (CEST)

Comentario

Creo que el diálogo-discusión que tuvieron fue de mucho provecho para mí, no fue una pérdida de tiempo, porque yo también soy de los que creen que cada cosa se debe llamar como tal, para ponernos de acuerdo. Doy las gracias a Pablo y Moriel principalmente, debido a que su discusión fue objeto de mi interés y a la vez el de aclarar conceptos.

Guillermo.ec 2-10-2004

DarkSpawn

Completamente de acuerdo, la traducción para referirze a Mergesort es ordenamiento por mezcla, y eso se puede ver claramente al analizar la codificación y el analisis de la Recursividad del algoritmo en cuestión. Divide el arreglo o lista en sub arreglos y luego mediante la función merge mezcla las soluciones de los subarreglos ordenados formando el arreglo completo en el orden correcto , sean estos números, palabras,letras, etc. Su tiempo de ejecución es variable siendo su costo asintótico de O (nlogn).

Para más detalles de ver visualmente la ejecución, codigo fuente y analisis de numero de comparaciones y tiempo de ejecucion ver enlace http://miarroba.com/foros/ver.php?foroid=674005

Tomar en cuenta que es un buen algoritmo por su coste menor que el insertion sort y el burbuja (bubble sort), aunque existen mejores, como el Bucketsort, el Radix-sort o el Counting Sort que tienen tiempos asintoticos lineales O(n) o theta de n "donde esta menuda theta :S"

¿Ordenación no decreciente?[editar]

¿por qué una ordenación debe ser siempre de menor a mayor y no al revés?, me parece que decir que el resultado de una ordenación debe ser obligatoriamente una lista ordenada de menor a mayor y no al revés es poner una condición un poco absurda, más aún cuando en cualquier algoritmo de ordenación, hacer que éste te ordene de menor a mayor o al revés, es algo tan simple como cambiar un '<' por un '>' (o un '>' por un '<').

--Jesuja 18:54 10 oct 2007 (CEST)

Nombre del artículo[editar]

Sí, ya sé que ordenamiento existe, pero creo que no es correcto en este contexto ya que se refiere al campo jurídico. Creo que "Algoritmos de ordenación" es mucho más adecuado. Ñuño Martínez (discusión) 20:07 10 jun 2008 (UTC)[responder]

Coincido, ordenamiento es otra cosa, ¿algún usuario autoconfirmado lo puede cambiar?. —200.16.16.13 (discusión) 21:37 9 mar 2012 (UTC)[responder]

problema con un articulo[editar]

bueno es un poco confuso dejarle un mensaje a algun moderador, asi que espero que esto llegue a los ojos correctos.

En el articulo sobre algoritmos de ordenamiento -> merge_sort hay un error en el codigo que esta bajo el lenguaje "C":

el codigo esta erroneo pro que no ordena los elementos; el arreglo de prueba es {2,3,5,7,2,6,1,5,8,3,2}, y sin embargo, una vez que el codigo ha sido compilado, el programa devuelve el siguiente resultado: {2,3,5,7,2,6,1,5,8,3,2,8}

creo que es conveniente que se corrija este codigo. disculpa si "vandalize" wikipedia pero como no hay ningun boton de "contact us" o algo por el estilo crei que con dejar el mensaje ahi se entenderia.

de antemano gracias gustavo, ags, mex 189.166.158.10 (discusión) 19:39 5 jun 2010 (UTC)[responder]

Propuesta: Agregar sección "Algoritmos de ordenamiento populares"/ Dar una breve introducción sobre cada algoritmo[editar]

Hola! El artículo en inglés de Algoritmos de ordenamiento tiene una sección muy buena donde menciona los algoritmos de ordenamiento más populares. También da una breve introducción a cada uno y provee el enlace al artículo dedicado a ese algoritmo. Creo que sería bastante informativo agregar esta sección, o al menos los breves parrafos introductorios a los algoritmos. Me parece que le agregaría mucho valor educativo a la página, pues proveería una visión panorámica y resumida de cada uno de los algoritmos. Yo puedo realizar la traducción de los párrafos correspondientes. ¿Qué les parece?¡Saludos!--Escritor87 (discusión) 03:46 13 nov 2013 (UTC)[responder]

Enlaces externos modificados[editar]

Hola,

Acabo de modificar 1 enlaces externos en Algoritmo de ordenamiento. Por favor tomaos un momento para revisar mi edición. Si tenéis alguna pregunta o necesitáis que el bot ignore los enlaces o toda la página en su conjunto, por favor visitad esta simple guía para ver información adicional. He realizado los siguientes cambios:

Se añadió el archivo https://web.archive.org/web/20090214183034/http://xistral.ei.uvigo.es/MTPAlgoritmos/index.php?action=VisualizarAlgoritmos&tipo=Ordenacion a http://xistral.ei.uvigo.es/MTPAlgoritmos/index.php?action=VisualizarAlgoritmos&tipo=Ordenacion

Por favor acudid a la guía anteriormente enlazada para más información sobre cómo corregir los errores que el bot pueda cometer.

Saludos.—InternetArchiveBot (Reportar un error) 01:15 3 jun 2018 (UTC)[responder]