Ordenamiento por selección

1. Algoritmo de ordenamiento por selección
2. Ejemplo de ordenamiento por selección
3. Implementación del algoritmo de ordenamiento por selección
4. Complejidad del algoritmo de Ordenamiento por selección

La ordenamiento por selección es un algoritmo de ordenación simple. Funciona dividiendo el array en dos partes: un subarray ordenado y otro sin ordenar. La ordenamiento por selección encuentra el elemento más pequeño dentro del subarray sin ordenar y lo mueve al último índice del subarray ordenado. Se utiliza cuando las operaciones de intercambio son muy costosas porque, como máximo, sólo se requieren n intercambios.

Algoritmo de ordenamiento por selección

Supongamos que tenemos un array A[] sin ordenar que contiene n elementos.

Ejemplo de ordenamiento por selección

Supongamos que tenemos el array (5,3,4,2,1,6). Vamos a ordenarlo utilizando el algoritmo de ordenamiento por selección.

• Primera Iteración

Elemento mínimo: A[4] = 1

Intercambio (A[4], A[0]). El array se convierte en: (1) (3,4,2,5,6).

• Segunda Iteración

Elemento mínimo: A[3] = 2

Intercambio (A[3], A[1]). El array se convierte en: (1,2) (4,3,5,6)

• Tercera Iteración

Elemento mínimo: A[3] = 3

Intercambio (A[3], A[2]). El array se convierte en: (1,2,3) (4,5,6).

• Cuarta Iteración

Elemento mínimo: A[3] = 4

Intercambio (A[3], A[3]). El array se convierte en: (1,2,3,4) (5,6).

• Quinta Iteración

Elemento mínimo: A[4] = 5

Intercambio (A[4], A[4]). El array se convierte en: (1,2,3,4,5) (6)

El último elemento ya está ordenado. Obtenemos el array ordenado como : (1,2,3,4,5,6)

Implementación del algoritmo de ordenamiento por selección

#include <bits/stdc++.h>
using namespace std;

void selectionSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    // Find the minimum element for index i
    int min = i;
    for (int j = i + 1; j < n; j++)
      if (arr[j] < arr[min]) min = j;
    // Put element in sorted position
    swap(arr[min], arr[i]);
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  selectionSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complejidad del algoritmo de Ordenamiento por selección

Complejidad de tiempo

• Caso medio

En promedio, se realizan n-i comparaciones en la quinta pasada de la ordenación por inserción. Por tanto, si hay n iteraciones, la complejidad temporal media puede ser la siguiente:

(n-1) + (n-2) + (n-3) + ... + 1 = n*(n-1)/2

Por lo tanto, la complejidad de tiempo es del orden de [Big Theta]: O(n²). También se puede calcular contando el número de bucles. Hay un total de dos bucles de n iteraciones haciendo la complejidad : n*n = n²

• El peor caso

La complejidad temporal en el peor caso es [Big O] O(n²).

• El mejor caso

La complejidad temporal en el mejor de los casos es [Big Omega]: O(n²). Es lo mismo que la complejidad temporal en el peor de los casos.

Complejidad espacial

La complejidad espacial del algoritmo de ordenamiento por selección es O(1) porque no se necesita más memoria que una variable temporal.