Algoritmos y Estructuras de Datos

Ordenamiento por selección

El algoritmo de ordenamiento por selección es uno de los más intuitivos. Repetidamente, encuentra el elemento mínimo del arreglo y lo mueve al frente. Luego continúa buscando el elemento mínimo en la parte restante del arreglo y repite este procedimiento hasta llegar al final.
a = [...]
for i in range(len(a)):                  # Deberíamos colocar el mínimo de a[i:] en a[i]
    min_idx = i                          # Índice del elemento mínimo
    for j in range(i + 1, len(a)):       # Busca el índice del elemento mínimo
        if a[j] < a[min_idx]:            # Si encontramos un elemento más pequeño
            min_idx = j                  # Actualiza el índice del elemento mínimo
    a[i], a[min_idx] = a[min_idx], a[i]  # Intercambia a[i] y a[min_idx]
print(a)
En cada iteración, tomamos el elemento mínimo de la parte restante del arreglo y usamos sus índices para intercambiar el elemento actual con ese mínimo. En caso de que el actual ya sea el mínimo, no ocurrirá ningún cambio, pues se intercambiaría consigo mismo, dejando el arreglo igual.
 
El algoritmo de ordenamiento por selección localiza el elemento mínimo en el arreglo y luego intercambia la posición actual con dicho mínimo. Esto significa que en cada iteración se recorre la porción restante del arreglo para hallar ese elemento mínimo (la función min recorre el arreglo elemento por elemento para encontrar el valor más bajo). Por lo tanto, el tiempo total de ejecución del algoritmo corresponde a realizar n iteraciones que, a su vez, hacen alrededor de n recorridos ⇒ operaciones en total.
Veamos una simulación en varios arreglos:
[4, 1, -1, 0, 2, 8]
  1. i = 0 ⇒ val = -1 ⇒ idx = 2 ⇒ swap ⇒ [-1, 1, 4, 0, 2, 8]
  1. i = 1 ⇒ val = 0 ⇒ idx = 3 ⇒ swap ⇒ [-1, 0, 4, 1, 2, 8]
  1. i = 2 ⇒ val = 1 ⇒ idx = 3 ⇒ swap ⇒ [-1, 0, 1, 4, 2, 8]
  1. i = 3 ⇒ val = 2 ⇒ idx = 4 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
  1. i = 4 ⇒ val = 4 ⇒ idx = 4 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
  1. i = 5 ⇒ val = 8 ⇒ idx = 5 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
[10, 5, 1, -1, -2, -7]
  1. i = 0 ⇒ val = -7 ⇒ idx = 5 ⇒ swap ⇒ [-7, 5, 1, -1, -2, 10]
  1. i = 1 ⇒ val = -2 ⇒ idx = 4 ⇒ swap ⇒ [-7, -2, 1, -1, 5, 10]
  1. i = 2 ⇒ val = -1 ⇒ idx = 3 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 3 ⇒ val = 1 ⇒ idx = 3 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 5 ⇒ val = 10 ⇒ idx = 5 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
[1, 2, 3, 4, 5]
  1. i = 0 ⇒ val = 1 ⇒ idx = 0 ⇒ swap ⇒ [1, 2, 3, 4, 5]
  1. i = 1 ⇒ val = 2 ⇒ idx = 1 ⇒ swap ⇒ [1, 2, 3, 4, 5]
  1. i = 2 ⇒ val = 3 ⇒ idx = 2 ⇒ swap ⇒ [1, 2, 3, 4, 5]
  1. i = 3 ⇒ val = 4 ⇒ idx = 3 ⇒ swap ⇒ [1, 2, 3, 4, 5]
  1. i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ swap ⇒ [1, 2, 3, 4, 5]

Desafío

Dados n enteros, ordénalos en orden creciente utilizando el ordenamiento por selección.

Entrada

La primera línea de la entrada contiene un único número entero n (1 ≤ n ≤ 1000), que representa la cantidad de elementos en el arreglo.
La siguiente línea contiene n enteros separados por espacios: a1, a2, ... an (−10^9 ≤ ai ≤ 10^9).

Salida

El programa debe imprimir el arreglo proporcionado como entrada ordenado en forma creciente.

Ejemplos

Entrada
Salida
5 5 5 3 2 3
2 3 3 5 5

Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue