¿Cómo ordenar los elementos de un conjunto?

Question

Supongamos que tengo un conjunto $S=\{1,\ldots,n\}$ que no está necesariamente indexado. Como los conjuntos son intrínsecamente desordenados, me gustaría hacer una secuencia $a=(a_1,\ldots,a_n)$ de los elementos en $S$ tal que $a_1<\cdots<a_n$ .

Supongo que tengo que asignar los valores de alguna manera, pero ¿cómo hacerlo? Ten en cuenta que aquí escribo secuencia en lugar de tupla ya que todos los elementos de $S$ son números enteros, por si hay alguna diferencia. Tal vez haya otras formas mejores que la propuesta arriba.

Answer 1

Después de ver los comentarios, me parece que estás preguntando por algoritmos de clasificación ( Wikipedia ), que son ciertamente una parte de las matemáticas, en el área de la informática teórica (hay un sitio separado de Stack Exchange para ello sin embargo; aquí está la lista de preguntas sobre la clasificación ).

Los algoritmos de ordenación suelen discutirse en términos de análisis asintótico (a medida que crece el tamaño de la lista de cosas a ordenar, cómo crece la cantidad de tiempo que se tarda en ordenar), su eficiencia en algún aspecto (por ejemplo, si comparar dos elementos del conjunto va a llevar mucho tiempo, es posible que se quiera elegir un algoritmo que haga pocas comparaciones), o su idoneidad dadas las suposiciones sobre los datos (por ejemplo, si los datos ya estarán "mayoritariamente" ordenados).

Para ver un ejemplo sencillo de un algoritmo de ordenación, mire selección de ordenación ( Wikipedia ): dado el conjunto $S$ ,

• Dejemos que $a_1=\min(S)$

• Dejemos que $a_2 = \min(S\setminus\{a_1\})$

• Dejemos que $a_3 = \min(S\setminus\{a_1,a_2\})$

• ...