CodeUtility
Haz que programar sea más fácil.
Algoritmos en C/C++

El ordenamiento rápido (quick sort) en C y C++

En esta lección vas a implementar el ordenamiento rápido particionando el arreglo alrededor de un elemento pivote.

Introducción

El ordenamiento rápido elige un elemento como pivote y reorganiza el arreglo para que los elementos menores que el pivote queden a su izquierda y los demás a su derecha. Así el pivote queda en su posición definitiva, y después el algoritmo ordena los dos lados con recursividad.

Puntos importantes

  • Prueba con una entrada vacía, un solo elemento, valores repetidos y datos ya ordenados.
  • Primero haz que el código sea correcto y después optimízalo.
  • En código real, usa preferentemente las funciones ya hechas de la biblioteca estándar.

Visualizador de El ordenamiento rápido (quick sort) en C y C++

O(n log n)

Usa Reproducir o Paso para seguir cada comparación y movimiento de datos.

Ejemplos de código C y C++

C
Ejecutar →
main.c
#include <stdio.h>

void swap(int *left, int *right) {
    int temporary = *left;
    *left = *right;
    *right = temporary;
}

int partition(int *values, int low, int high) {
    int pivot = values[high];
    int boundary = low;
    for (int scan = low; scan < high; ++scan) {
        if (values[scan] < pivot) {
            swap(&values[boundary++], &values[scan]);
        }
    }
    swap(&values[boundary], &values[high]);
    return boundary;
}

void quick_sort(int *values, int low, int high) {
    if (low >= high) return;
    int pivot = partition(values, low, high);
    quick_sort(values, low, pivot - 1);
    quick_sort(values, pivot + 1, high);
}

int main(void) {
    int values[] = {9, 4, 7, 3, 10, 5};
    quick_sort(values, 0, 5);
    for (int index = 0; index < 6; ++index) {
        printf("%d ", values[index]);
    }
}
Resultado de la ejecución
3 4 5 7 9 10
C++
Ejecutar →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

template<class Iterator>
void quick_sort(Iterator first, Iterator last) {
    if (last - first < 2) return;
    auto pivot = *(last - 1);
    auto middle = std::partition(first, last - 1,
        [pivot](int value) { return value < pivot; });
    std::iter_swap(middle, last - 1);
    quick_sort(first, middle);
    quick_sort(middle + 1, last);
}

int main() {
    std::vector values{9, 4, 7, 3, 10, 5};
    quick_sort(values.begin(), values.end());
    for (int value : values) {
        std::cout << value << ' ';
    }
}
Resultado de la ejecución
3 4 5 7 9 10

Comparación entre C y C++

La función partition en C elige el último elemento como pivote y usa la variable boundary para marcar el límite de la zona de elementos menores. Al final, el pivote se intercambia a la posición boundary. La versión de C++ usa std::partition para expresar la partición de forma más breve. La complejidad media es O(n log n), pero un pivote mal elegido puede subirla a O(n²).

C

Los bucles, los punteros, las longitudes y los búferes temporales se escriben de forma explícita.

C++

Los iteradores y los algoritmos estándar separan el procesamiento de la forma en que se guardan los datos.

Ejercicios de práctica

Ejecuta las dos versiones y después modifica el código para ver la diferencia de seguridad que aporta cada lenguaje.

  • Sigue cada comparación en papel.
  • Prueba con valores repetidos y con valores muy grandes y muy pequeños.
  • Mide el tiempo de ejecución de tu código y compáralo con la biblioteca estándar.

Practica con un reto

Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.

Todos los retos