Quicksort en C

Particionar alrededor de un pivote y luego ordenar las dos mitades.

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

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

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

Cómo funciona

1. La partición de Lomuto lleva un índice que escanea y una frontera.
2. El pivote aterriza en su posición final en cada pasada.
3. La recursión se encarga de las partes a cada lado.

Palabras clave y builtins usados aquí

• for
• if
• int
• return
• static
• void

El intento, en números

Líneas

27

Caracteres a escribir

527

Tokens

185

Ritmo de tres estrellas

95 tpm

Al ritmo de tres estrellas de 95 tokens por minuto, este intento toma unos 117 segundos.

Escribe este fragmento

Paso 4 de 5 en Ordenamiento y búsqueda; paso 4 de 20 en Estructuras de datos y algoritmos.

← Anterior Siguiente →

Quicksort en otros lenguajes

• Python