5 - Selection Sort

Selection Sort ordena seleccionando el mínimo (o máximo) restante en cada pasada y colocándolo en su posición definitiva. Realiza pocos intercambios, lo que puede ser ventajoso cuando el costo de swap es alto.

5.1 Idea general del algoritmo

En cada iteración externa, se asume que la sección izquierda ya está ordenada. Se busca el elemento más pequeño en la parte no ordenada y se lo intercambia con el elemento en la posición actual.

5.2 Búsqueda del mínimo en el resto de la lista

El recorrido interno localiza el índice del mínimo desde la posición siguiente a la actual hasta el final del array.

5.3 Intercambio con la posición actual

Una vez identificado el mínimo, se lo intercambia con la posición actual. Si ya está en el lugar correcto, el swap no es necesario.

5.4 Recorrido externo y recorrido interno

El bucle externo avanza la frontera de la zona ordenada. El bucle interno recorre el segmento restante para encontrar el mínimo.

5.5 Implementación en C

Versión clásica para orden ascendente; utiliza la función swap ya definida.

void selection_sort(int *arr, int n) {
  for (int i = 0; i < n - 1; i++) {
    int indice_min = i;
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < arr[indice_min]) {
        indice_min = j;
      }
    }
    if (indice_min != i) {
      swap(&arr[i], &arr[indice_min]);
    }
  }
}

Explicación línea por línea:

• for (int i = 0; i < n - 1; i++): define la posición donde colocar el siguiente mínimo.
• int indice_min = i;: asume que el mínimo inicial está en la posición actual.
• for (int j = i + 1; j < n; j++): busca el mínimo real en el resto de la lista.
• if (arr[j] < arr[indice_min]) indice_min = j;: actualiza el índice del mínimo cuando encuentra un valor menor.
• if (indice_min != i) swap(&arr[i], &arr[indice_min]);: intercambia solo si el mínimo no está ya en su lugar.

5.6 Complejidad temporal y espacial

• Tiempo: O(n^2) en todos los casos; el número de comparaciones es constante para un tamaño dado.
• Memoria: O(1) adicional; trabaja in-place.
• Estabilidad: no es estable porque un swap puede cambiar el orden relativo de elementos iguales.

5.7 Ventajas y desventajas

• Ventajas: pocos intercambios (a lo sumo n - 1); implementación sencilla; rendimiento predecible.
• Desventajas: complejidad cuadrática incluso si la lista ya está ordenada; no es estable.

5.8 Casos donde Selection Sort es útil

• Cuando el costo del swap es alto pero comparar es barato.
• Listas pequeñas donde la simplicidad prima sobre el rendimiento asintótico.
• Escenarios educativos o de depuración para contrastar resultados con otros algoritmos.

5.9 Archivos para un proyecto en CLion

Para practicar Selection Sort, organiza el proyecto con estos archivos:

• swap.h y swap.c: función de intercambio compartida.
• utils.h y utils.c: impresión de arrays.
• selection_sort.c: implementación del algoritmo y su prototipo.
• main.c: prepara datos, llama a selection_sort y muestra resultados.

Códigos completos:

/* swap.h */
void swap(int *a, int *b);

/* swap.c */
#include "swap.h"

void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

/* utils.h */
void imprimir_array(const int *arr, int n);

/* utils.c */
#include <stdio.h>
#include "utils.h"

void imprimir_array(const int *arr, int n) {
  printf("[");
  for (int i = 0; i < n; i++) {
    printf("%d", arr[i]);
    if (i + 1 < n) {
      printf(", ");
    }
  }
  printf("]\n");
}

/* selection_sort.c */
#include "swap.h"

void selection_sort(int *arr, int n) {
  for (int i = 0; i < n - 1; i++) {
    int indice_min = i;
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < arr[indice_min]) {
        indice_min = j;
      }
    }
    if (indice_min != i) {
      swap(&arr[i], &arr[indice_min]);
    }
  }
}

/* main.c */
#include <stdio.h>
#include "swap.h"
#include "utils.h"

void selection_sort(int *arr, int n); /* prototipo */

int main(void) {
  int datos[] = {6, 1, 8, 3, 4};
  int n = sizeof(datos) / sizeof(datos[0]);

  printf("Antes: ");
  imprimir_array(datos, n);

  selection_sort(datos, n);

  printf("Despues: ");
  imprimir_array(datos, n);
  return 0;
}