Ordenamiento por selección

7.1 Definición del ordenamiento por selección

Ordenamiento por selección (Selection Sort) es un algoritmo de ordenamiento que encuentra el elemento más pequeño de la parte no ordenada del array y lo intercambia con el primer elemento de esa parte. El proceso se repite para los elementos restantes hasta que todo el array esté ordenado.

Principio de funcionamiento:

1. Comenzamos con el primer elemento del array.
2. Encontramos el elemento más pequeño en la parte no ordenada restante del array.
3. Intercambiamos el elemento más pequeño con el primer elemento de la parte no ordenada.
4. Repetimos el proceso para el siguiente elemento hasta que todo el array esté ordenado.

Proceso paso a paso

1. Encontramos el elemento más pequeño en el array y lo intercambiamos con el primer elemento.
2. Repetimos el proceso para el resto del array (comenzando con el segundo elemento).
3. Continuamos el proceso hasta que todo el array esté ordenado.

Complejidad temporal y espacial del ordenamiento por selección

Complejidad temporal:

• En el peor de los casos: O(n^2) — sucede cuando los elementos están inicialmente en orden inverso o aleatorio.
• En el caso promedio: O(n^2) — ocurre para una disposición aleatoria de los elementos.
• En el mejor de los casos: O(n^2) — incluso si el array ya está ordenado, el algoritmo realiza las mismas comparaciones.

Complejidad espacial:

O(1) — ya que el algoritmo utiliza una cantidad constante de memoria adicional (solo algunas variables para almacenar valores temporales).

7.2 Implementación del algoritmo de ordenamiento por selección

La implementación del algoritmo es muy sencilla:

Paso 1: encontramos el elemento mínimo entre todos los elementos e intercambiamos su lugar con el primero.

Paso 2: encontramos el elemento mínimo entre todos los elementos, excepto el primero, e intercambiamos su lugar con el segundo.

Paso 3: encontramos el elemento mínimo entre todos los elementos, excepto el primero y el segundo, e intercambiamos su lugar con el tercero.

Implementación en Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Encontramos el mínimo en la parte no ordenada del array min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j
        # Intercambiamos el elemento mínimo encontrado con el primero de la parte no ordenada arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr  # Devolvemos el array ordenado

# Ejemplo de uso:
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Array ordenado:", sorted_arr)
# Salida: Array ordenado: [11, 12, 22, 25, 64]

Ejemplo del funcionamiento del algoritmo:

1. Primer pasaje (i = 0):
   1. Encontramos el elemento mínimo (11) en la parte no ordenada del array [64, 25, 12, 22, 11].
   2. Intercambiamos 11 con 64.
   3. Array: [11, 25, 12, 22, 64]
2. Segundo pasaje (i = 1):
   1. Encontramos el elemento mínimo (12) en la parte no ordenada del array [25, 12, 22, 64].
   2. Intercambiamos 12 con 25.
   3. Array: [11, 12, 25, 22, 64]
3. Tercer pasaje (i = 2):
   1. Encontramos el elemento mínimo (22) en la parte no ordenada del array [25, 22, 64].
   2. Intercambiamos 22 con 25.
   3. Array: [11, 12, 22, 25, 64]
4. Cuarto pasaje (i = 3):
   1. Encontramos el elemento mínimo (25) en la parte no ordenada del array [25, 64].
   2. 25 ya está en su lugar, no se requiere intercambio.
   3. Array: [11, 12, 22, 25, 64]

El algoritmo se completa ya que todos los elementos están ordenados.