Recursive heapsort in C

Question

I have a heapsort, and would like to implement it recursive. What I need to change in my algorithm?

void criarHeap(int v[], int inicio, int final){
    int aux = v[inicio];//v[pai]//inicio=pai
    int filho = (inicio * 2)+1;//i=filho
while(filho<=final){
    if(filho<final && (filho+1)<final){
        if(v[filho]<v[filho+1]){//pai tem 2 filhos ? se sim, qual o maior
            filho++;
        }
    }
    if(aux<v[filho]){//troca o filho com o pai se o filho for maior
        v[inicio]=v[filho];
        inicio=filho;
        filho=(2*inicio)+1;
    }
    else{
        filho=final+1;
    }
}
    v[inicio] = aux;//pai troca com filho mais profundo mais a direita
}

void heapSort(int v[], int tam){
    int i;
    int aux;
    for(i=(tam-1)/2;i>=0;i--){// cria heap
        criarHeap(v,i,tam-1);
    }
    for(i=tam-1;i>=1;i--){//pega o maior elemento e coloca na posicao o array
        aux = v[0];
        v[0]=v[i];
        v[i]=aux;
        criarHeap(v,0,i-1);//cria o heap sem o maior elemento anterior
    }
}

Answer 1

First, I created a test for your algorithm:

int main(void) {
    int teste[] = {8, 4, 2, 9, 5, 0, 10, 7, 1, 3, 6};
    heapSort(teste, 11);
    for (int i = 0; i <= 10; i++) {
        printf("%i ", teste[i]);
    }
    return 0;
}

The output was the expected: 0 1 2 3 4 5 6 7 8 9 10. See here working on ideone.

So now we can move your code. The first step is to transform the while of function criarHeap in a recursion.

We see that while changes the variable filho which will be used after the end of this loop. Thus, the recursive function that will replace this while can return the value of this variable. The variables that are used in this while and that are received externally are v, inicio, aux, filho and final, then these become the parameters for the recursive function.

The code goes like this:

int criarHeapRecursao(int v[], int inicio, int aux, int filho, int final) {
    if (filho > final) return inicio;

    // Pai tem 2 filhos? Se sim, qual é o maior?
    if (filho < final && filho + 1 < final && v[filho] < v[filho + 1]) {
        filho++;
    }

    // Troca o filho com o pai se o filho for maior.
    if (aux < v[filho]) {
        v[inicio] = v[filho];
        inicio = filho;
        filho = 2 * inicio + 1;
    } else {
        filho = final + 1;
    }
    return criarHeapRecursao(v, inicio, aux, filho, final);
}

void criarHeap(int v[], int inicio, int final) {
    int aux = v[inicio];
    int filho = inicio * 2 + 1;
    inicio = criarHeapRecursao(v, inicio, aux, filho, final);
    v[inicio] = aux; // Pai troca com filho mais profundo mais a direita.
}

Note that the recursion is at the end of the function criarHeapRecursao and what was the stopping condition of the while became a if at the beginning of the function.

Done that, now we have the function heapSort that has two loops. Each loop will turn a recursive function to part. The stop condition is placed as one if at the beginning of the function and the counter becomes one of the parameters of each of these recursive functions. The other variables used in the loops (v and tam) also become parameters. The recursive call is placed at the end of each fution. The result is this:

void heapSort1(int v[], int i, int tam) {
    if (i < 0) return;
    criarHeap(v, i, tam - 1);
    heapSort1(v, i - 1, tam);
}

void heapSort2(int v[], int i, int tam) {
    if (i <= 0) return;
    int aux = v[0];
    v[0] = v[i];
    v[i] = aux;
    criarHeap(v, 0, i - 1); // Cria o heap sem o maior elemento anterior.
    heapSort2(v, i - 1, tam);
}

void heapSort(int v[], int tam) {
    heapSort1(v, (tam - 1) / 2, tam);
    heapSort2(v, tam - 1, tam);
}

In this way, the links of the function heapSort were converted into recursive functions heapSort1 and heapSort2.

The variable aux had a scope where it was used only within the second loop, but its value was not used between one iteration and another, made no sense before the first iteration and was not used after the last iteration. For this reason, it has become a local variable of heapSort2.

Output remains the expected, 0 1 2 3 4 5 6 7 8 9 10. See here working on ideone.