Uno de los problemas más famosos e importantes en programación consiste en ordenar los elementos de una arreglo.
Escribe un programa que lee N números y los ordena en orden no decreciente (es decir, de menor a mayor).
La idea de este problema es que implementes un algoritmo de sort desde cero (o todavía mejor, ¡que implementes varios!). Para obtener 100 puntos, tu algoritmo debe tener complejidad de tiempo O(n2) (ó menor). Los algoritmos clásicos con complejidad O(n2) son bubble sort, insertion sort y selection sort.
Aunque en la práctica es raro implementar un algoritmo de sort desde cero (normalmente usas la implementación que ya existe en tu lenguaje), es fundamental conocerlos y entenderlos porque sus ideas pueden aplicarse a problemas más complejos.
La entrada contiene varias líneas:
N, el número de números que hay que ordenar.N enteros Ai para 0 ≤ i < N, los elementos a ordenar. Estos números están separados por espacios. Está garantizado que Ai satisface -109 ≤ Ai ≤ 109.La salida debe tener exactamente una línea con los mismos números de la entrada pero ordenados en orden no decreciente. Los números deben estar separados por espacios.
6
3 2 1 0 -1 0
-1 0 0 1 2 3
1 ≤ N ≤ 1000. Este tamaño de N está diseñado para que algoritmos con complejidad O(n2) como el bubble sort, selection sort ó insertion sort obtengan 100 puntos.