Ordenar arreglo con Quicksort en C: en este post voy a mostrarte cómo implementar el algoritmo de ordenamiento rápido o quicksort en ANSI C.

Este algoritmo destaca porque es uno de los más rápidos al momento de ordenar arreglos, además de que el mismo no ocupa arreglos temporales, simplemente intercambia variables y utiliza el método de divide y vencerás.

Al final podremos ordenar arreglos usando el algoritmo Quicksort en C.

Implementación de Quicksort en C

Para implementar este algoritmo vamos a usar el esquema de partición Hoare; el pivote siempre será el mismo (el primer elemento de la lista) y colocaremos los punteros en los extremos del arreglo.

Con “puntero” me refiero a índice del arreglo

Explicación básica de Quicksort

Nota: si quieres ir directo al código pasa al siguiente apartado.

Este algoritmo selecciona un pivote, y después establece dos apuntadores en los extremos del arreglo. Va acercando entre sí los índices (es decir, disminuye el de la derecha y aumenta el de la izquierda) hasta que encuentra un elemento que se puede intercambiar.

Un elemento intercambiable es aquel que es más pequeño que el pivote pero está a su derecha, o que es más grande que el pivote pero está a su izquierda. En otras palabras, un elemento que no está ordenado.

Si encuentra el elemento intercambiable, lo intercambia y sigue acercando los punteros hasta que los mismos se cruzan o izquierda es mayor o igual que derecha.

En caso de que los índices se crucen, se devuelve el índice de la derecha y ese se toma para dividir el arreglo y ahora aplicar lo mismo a las dos mitades, aplicando la recursión o recursividad hasta que finalmente todo el arreglo se ordenará.

Es decir, en otras palabras el algoritmo utiliza la técnica de divide y vencerás. Por cierto, la recursividad se cumple mientras izquierda sea menor que derecha.

Quicksort en C

Ahora sí a lo que venimos. Para implementar este algoritmo debemos tener una función que intercambie valores. No es estrictamente necesaria pero nos ahorra tres líneas de código además de que si la usamos aumenta la legibilidad.

Por lo tanto usaré una función que ya había explicado antes, que intercambia valores por referencia:

void intercambiar(int *a, int *b) {
  int temporal = *a;
  *a = *b;
  *b = temporal;
}

Después tenemos la función quicksort que recibe el arreglo y los índices inicio y fin, o izquierda y derecha. En este caso se usará recursividad así que se divide el arreglo y se invoca a quicksort 2 veces, así:

// Divide y vencerás
void quicksort(int arreglo[], int izquierda, int derecha) {
  if (izquierda < derecha) {
    int indiceParticion = particion(arreglo, izquierda, derecha);
    quicksort(arreglo, izquierda, indiceParticion);
    quicksort(arreglo, indiceParticion + 1, derecha);
  }
}

Si te fijas el algoritmo irá dividiendo el arreglo, pero usará el índice que devuelva el método particion; este método es el que realmente ordena el arreglo e intercambia valores. Queda así:

int particion(int arreglo[], int izquierda, int derecha) {
  // Elegimos el pivote, es el primero
  int pivote = arreglo[izquierda];
  // Ciclo infinito
  while (1) {
    // Mientras cada elemento desde la izquierda esté en orden (sea menor que el
    // pivote) continúa avanzando el índice
    while (arreglo[izquierda] < pivote) {
      izquierda++;
    }
    // Mientras cada elemento desde la derecha esté en orden (sea mayor que el
    // pivote) continúa disminuyendo el índice
    while (arreglo[derecha] > pivote) {
      derecha--;
    }
    /*
    Si la izquierda es mayor o igual que la derecha significa que no
    necesitamos hacer ningún intercambio
    de variables, pues los elementos ya están en orden (al menos en esta
    iteración)
    */
    if (izquierda >= derecha) {
      // Indicar "en dónde nos quedamos" para poder dividir el arreglo de nuevo
      // y ordenar los demás elementos
      return derecha;
    } else {//Nota: yo sé que el else no hace falta por el return de arriba, pero así el algoritmo es más claro
      /*
      Si las variables quedaron "lejos" (es decir, la izquierda no superó ni
      alcanzó a la derecha)
      significa que se detuvieron porque encontraron un valor que no estaba
      en orden, así que lo intercambiamos
      */
      intercambiar(&arreglo[izquierda], &arreglo[derecha]);
      /*
      Ya intercambiamos, pero seguimos avanzando los índices
      */
      izquierda++;
      derecha--;
    }
    // El while se repite hasta que izquierda >= derecha
  }
}

Eso es todo lo que necesitamos para usar este método de ordenamiento en C. A continuación veremos su uso.

Uso de quicksort en C

Vamos a ver un ejemplo, definimos en el método main un arreglo; también lo imprimimos para ver cómo es que se ve antes y cómo se ve después de ordenarlo usando quicksort.

int main(void) {
  // El arreglo
  int arreglo[] = {28, 11, 96, -5, 21, 18, 12, 22, 30, 97, -1, -40, -500};
  /*
  Calcular la longitud, puede ser definida por ti o calculada:
  
Longitud de un arreglo en C

  */
  int longitud = sizeof arreglo / sizeof arreglo[0];
  /*
  Imprimirlo antes de ordenarlo
  */
  printf("Imprimiendo arreglo antes de ordenar...\n");
  for (int x = 0; x < longitud; x++) {
    printf("%d ", arreglo[x]);
  }
  // Un salto de línea
  printf("\n");

  /*
  Invocar a quicksort indicando todo el arreglo, desde 0 hasta el índice final
  */
  quicksort(arreglo, 0, longitud - 1);
  /*
  Imprimirlo después de ordenarlo
  */
  printf("Imprimiendo arreglo despues de ordenar...\n");
  for (int x = 0; x < longitud; x++)
    printf("%d ", arreglo[x]);
  return 0;
}

El arreglo puede ser de cualquier tamaño y tener elementos de cualquier tipo. Al ejecutar el código aparece lo de la imagen del inicio del post:

Te invito a ver más sobre C o algoritmos en mi blog.