Algoritmos de ordenación en Arduino

En esta entrada voy a dejar una serie de algoritmos de ordenación para usar en nuestros programas, me he ayudado de IA para generarla, pero he comprobado su funcionamiento y es correcto, además de haber comprobado que los algoritmos están bien en funcionamiento.

No voy a explicar nada, puesto que son cosas que ya casí ni se estudian dado que hay librerías en los lenguajes de programación que ya los traen.

Algoritmo	Complejidad	Memoria Extra	Estable	Comentarios para AVR/Arduino
QuickSort	O(n log n) medio O(n²) peor caso	O(log n) por recursión	No	Rápido, pero cuidado con recursión en AVR; elegir pivote aleatorio ayuda
Bubble Sort	O(n²)	O(1)	Sí	Muy simple, solo útil en arrays muy pequeños (<50)
Selection Sort	O(n²)	O(1)	No	Pocos swaps, mejor que bubble en algunos casos
Insertion Sort	O(n²)	O(1)	Sí	Muy rápido en arrays casi ordenados, excelente para <100 elementos
Merge Sort	O(n log n)	O(n)	Sí	Muy eficiente, pero usa RAM extra (buffer temporal)
Heap Sort	O(n log n)	O(1)	No	In-place, siempre O(n log n), buena opción para arrays medianos/grandes
Shell Sort	O(n^1.2) aprox	O(1)	No	In-place, muy rápido en arrays medianos, simple
Comb Sort	O(n²) worst, O(n^1.3) avg	O(1)	No	Variante mejorada de Bubble, muy rápida, fácil de implementar
Intro Sort	O(n log n)	O(log n) aprox	No	QuickSort + HeapSort + Insertion Sort; log2(n) calculado con enteros (ilog2)

Quicksort

#ifndef _quicksort_h_
#define _quicksort_h_

// Función genérica para intercambiar dos elementos
template <typename T>
void swap(T &a, T &b) {
  T temp = a;
  a = b;
  b = temp;
}

// Partición genérica
template <typename T>
int partition(T arr[], int low, int high) {
  T pivot = arr[high];  // pivote
  int i = low - 1;

  for (int j = low; j <= high - 1; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i + 1], arr[high]);
  return (i + 1);
}

// Quicksort genérico
template <typename T>
void quicksort(T arr[], int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    quicksort(arr, low, pi - 1);
    quicksort(arr, pi + 1, high);
  }
}


#endif

Bubblesort

#ifndef _bubblesort_h_
#define _bubblesort_h_

template<typename T>
void bubbleSort(T* arr, size_t n) {
  bool swapped;
  for (size_t i = 0; i < n - 1; i++) {
    swapped = false;
    for (size_t j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        T temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }
    if (!swapped) {
      break;  // ya está ordenado
    }
  }
}

#endif

Selection sort

#ifndef _selectionsort_h_
#define _selectionsort_h_

template<typename T>
void selectionSort(T* arr, size_t n) {
  for (size_t i = 0; i < n - 1; i++) {

    size_t minIndex = i;

    // Buscar el mínimo en el resto del arreglo
    for (size_t j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Intercambiar solo si hace falta
    if (minIndex != i) {
      T temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
}

#endif

Insertionsort

#ifndef _insertionsort_h_
#define _insertionsort_h_

template<typename T>
void insertionSort(T* arr, size_t n) {
  for (size_t i = 1; i < n; i++) {

    T key = arr[i];
    size_t j = i;

    // Desplazamos elementos mayores que key hacia la derecha
    while (j > 0 && arr[j - 1] > key) {
      arr[j] = arr[j - 1];
      j--;
    }

    // Insertamos la clave en su posición
    arr[j] = key;
  }
}

#endif

Mergesort

#ifndef _mergesort_h_
#define _mergesort_h_

template<typename T>
void merge(T* arr, T* temp, size_t left, size_t mid, size_t right) {
    size_t i = left;     // índice de la primera mitad
    size_t j = mid + 1;  // índice de la segunda mitad
    size_t k = left;     // índice del buffer temporal

    // Mezclar ambas mitades ordenadas
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // Copiar lo que reste de la primera mitad
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    // Copiar lo que reste de la segunda mitad
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // Copiar de vuelta al arreglo original
    for (size_t t = left; t <= right; t++) {
        arr[t] = temp[t];
    }
}

template<typename T>
void mergesortImpl(T* arr, T* temp, size_t left, size_t right) {
    if (left < right) {
        size_t mid = left + (right - left) / 2;

        mergesortImpl(arr, temp, left, mid);
        mergesortImpl(arr, temp, mid + 1, right);

        merge(arr, temp, left, mid, right);
    }
}

template<typename T>
void mergesort(T* arr, size_t n) {
    // Buffer temporal (puede estar estático o global si quieres ahorrar stack)
    T* temp = new T[n];
    mergesortImpl(arr, temp, 0, n - 1);
    delete[] temp;
}


#endif

Heapsort

#ifndef _heapsort_h_
#define _heapsort_h_

template<typename T>
void heapify(T* arr, size_t n, size_t i) {
    while (true) {
        size_t largest = i;
        size_t left  = 2 * i + 1;
        size_t right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest])
            largest = left;

        if (right < n && arr[right] > arr[largest])
            largest = right;

        if (largest == i)
            break;

        T temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        i = largest;
    }
}

template<typename T>
void heapsort(T* arr, size_t n) {
    // 1. Construir el heap (max-heap)
    for (int i = (int)n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 2. Extraer elementos uno por uno
    for (size_t i = n - 1; i > 0; i--) {
        // mover la raíz (máximo) al final
        T temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // restaurar el heap para el resto
        heapify(arr, i, 0);
    }
}

#endif

Shellsort

#ifndef _shellsort_h_
#define _shellsort_h_

template<typename T>
void shellSort(T* arr, size_t n) {
  // Secuencia de incrementos clásica: n/2, n/4, ..., 1
  for (size_t gap = n / 2; gap > 0; gap /= 2) {

    // Insertion sort con ese "gap"
    for (size_t i = gap; i < n; i++) {
      T temp = arr[i];
      size_t j = i;

      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }

      arr[j] = temp;
    }
  }
}


#endif

Combsort

#ifndef _combsort_h_
#define _combsort_h_

template<typename T>
void combsort(T* arr, size_t n) {
  const float shrink = 1.3f; // factor de reducción del gap
  size_t gap = n;
  bool sorted = false;

  while (!sorted) {
    gap = size_t(gap / shrink);
    if (gap < 1) gap = 1;

    sorted = true;

    for (size_t i = 0; i + gap < n; i++) {
      if (arr[i] > arr[i + gap]) {
        T temp = arr[i];
        arr[i] = arr[i + gap];
        arr[i + gap] = temp;

        sorted = false;
      }
    }
  }
}

#endif

Introsort

#ifndef _introsort_h_
#define _introsort_h_

unsigned int ilog2(unsigned int n) {
  unsigned int res = 0;
  while (n > 1) {
    n >>= 1;  // divide entre 2
    res++;
  }
  return res;
}

template<typename T>
void insertionSort(T* arr, size_t left, size_t right) {
  for (size_t i = left + 1; i <= right; i++) {
    T key = arr[i];
    size_t j = i;
    while (j > left && arr[j - 1] > key) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = key;
  }
}

template<typename T>
void heapify(T* arr, size_t n, size_t i) {
  while (true) {
    size_t largest = i;
    size_t left = 2 * i + 1;
    size_t right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;

    if (largest == i) break;

    T temp = arr[i];
    arr[i] = arr[largest];
    arr[largest] = temp;

    i = largest;
  }
}

template<typename T>
void heapSort(T* arr, size_t n) {
  for (int i = (int)n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
  for (size_t i = n - 1; i > 0; i--) {
    T temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapify(arr, i, 0);
  }
}

template<typename T>
size_t partition(T* arr, size_t low, size_t high) {
  T pivot = arr[high];
  size_t i = low;

  for (size_t j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      T temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
      i++;
    }
  }

  T temp = arr[i];
  arr[i] = arr[high];
  arr[high] = temp;

  return i;
}

template<typename T>
void introSortImpl(T* arr, size_t low, size_t high, size_t depthLimit) {
  while (high > low) {
    size_t size = high - low + 1;

    if (size <= 16) {
      insertionSort(arr, low, high);
      return;
    }

    if (depthLimit == 0) {
      heapSort(arr + low, size);
      return;
    }

    size_t p = partition(arr, low, high);

    if (p > 0) introSortImpl(arr, p + 1, high, depthLimit - 1);
    high = p - 1;
    depthLimit--;
  }
}

template<typename T>
void introsort(T* arr, size_t n) {
  size_t depthLimit = 2 * (size_t)ilog2(n);
  if (n > 0) introSortImpl(arr, 0, n - 1, depthLimit);
}


#endif

Referencias

Algoritmo de ordenamiento