Ordenamiento por mezcla en C

Dividir, ordenar cada mitad y luego mezclar las dos corridas ordenadas.

static void merge(int *values, int *scratch, int low, int mid, int high) {
    int i = low;
    int j = mid + 1;
    int k = low;

    while (i <= mid && j <= high) {
        scratch[k++] = (values[i] <= values[j]) ? values[i++] : values[j++];
    }
    while (i <= mid) {
        scratch[k++] = values[i++];
    }
    while (j <= high) {
        scratch[k++] = values[j++];
    }
    for (int x = low; x <= high; x++) {
        values[x] = scratch[x];
    }
}

void mergesort(int *values, int *scratch, int low, int high) {
    if (low >= high) {
        return;
    }
    int mid = low + (high - low) / 2;
    mergesort(values, scratch, low, mid);
    mergesort(values, scratch, mid + 1, high);
    merge(values, scratch, low, mid, high);
}

Cómo funciona

1. La mezcla necesita espacio auxiliar del tamaño del rango.
2. Es estable, cosa que quicksort no es.
3. La profundidad de la recursión es logarítmica; el trabajo por nivel, lineal.

Palabras clave y builtins usados aquí

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

El intento, en números

Líneas

28

Caracteres a escribir

634

Tokens

243

Ritmo de tres estrellas

95 tpm

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

Escribe este fragmento

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

← Anterior Siguiente →