De acordo com a Wikipedia:

A ordenação por inserção itera, consumindo um elemento de entrada a cada repetição, e crescendo uma lista ordenada de saída. Em cada iteração, a ordenação por inserção remove um elemento dos dados de entrada, encontra a posição correta dentro da lista ordenada e o insere lá. Repete até que nenhum elemento de entrada restante.

A ordenação por heap divide sua entrada em uma região ordenada e uma não ordenada, e itera para reduzir a região não ordenada extraindo o maior elemento e movendo-o para a região ordenada. Envolve o uso de uma estrutura de dados de heap em vez de uma busca em tempo linear para encontrar o máximo.

Agora, dada a sequência inicial de inteiros, juntamente com uma sequência que é o resultado de várias iterações de algum método de ordenação, você pode dizer qual método de ordenação estamos usando?

Especificação de Entrada:

Cada arquivo de entrada contém um caso de teste. Para cada caso, a primeira linha fornece um inteiro positivo N (≤). Em seguida, na próxima linha, N inteiros são dados como a sequência inicial. A última linha contém a sequência parcialmente ordenada dos N números. Assume-se que a sequência de destino é sempre ascendente. Todos os números em uma linha são separados por um espaço.

Especificação de Saída:

Para cada caso de teste, imprima na primeira linha "Insertion Sort" ou "Heap Sort" para indicar o método usado para obter o resultado parcial. Em seguida, execute este método por mais uma iteração e imprima na segunda linha a sequência resultente. Garante-se que a resposta é única para cada caso de teste. Todos os números em uma linha devem ser separados por um espaço, e não deve haver espaço extra no final da linha.

Exemplo de Entrada 1:

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

Exemplo de Saída 1:

Insertion Sort
1 2 3 5 7 8 9 4 6 0

Exemplo de Entrada 2:

10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9

Exemplo de Saída 2:

Heap Sort
5 4 3 1 0 2 6 7 8 9

#include <stdio.h>
#include <stdlib.h>

#define MAX_TAMANHO 110

void trocar_elementos(int arr[], int pos_a, int pos_b) {
    int temporario = arr[pos_a];
    arr[pos_a] = arr[pos_b];
    arr[pos_b] = temporario;
}

void imprimir_sequencia(int dados[], int tamanho) {
    for (int i = 0; i < tamanho - 1; i++) {
        printf("%d ", dados[i]);
    }
    printf("%d\n", dados[tamanho - 1]);
}

int eh_heap_raiz_maximo(int arr[], int tamanho) {
    if (tamanho < 3) {
        return arr[0] >= arr[1];
    }
    return arr[0] >= arr[1] && arr[0] >= arr[2];
}

void percolar_para_baixo(int heap[], int tamanho_heap, int posicao_raiz) {
    int elemento = heap[posicao_raiz];
    int filho, pai;
    for (pai = posicao_raiz; (pai * 2 + 1) <= tamanho_heap; pai = filho) {
        filho = pai * 2 + 1;
        if (filho != tamanho_heap && heap[filho] < heap[filho + 1]) {
            filho++;
        }
        if (elemento >= heap[filho]) {
            break;
        } else {
            heap[pai] = heap[filho];
        }
    }
    heap[pai] = elemento;
}

void construir_heap_maximo(int arr[], int tamanho) {
    for (int i = (tamanho - 2) / 2; i >= 0; i--) {
        percolar_para_baixo(arr, tamanho - 1, i);
    }
}

void heapsort_completo(int arr[], int tamanho) {
    construir_heap_maximo(arr, tamanho);
    for (int i = tamanho - 1; i > 0; i--) {
        trocar_elementos(arr, 0, i);
        percolar_para_baixo(arr, i - 1, 0);
    }
}

void realizar_passo_insercao(int dados[], int tamanho, int inicio_ordenado) {
    int chave = dados[inicio_ordenado];
    int j;
    for (j = inicio_ordenado; j > 0 && dados[j - 1] > chave; j--) {
        dados[j] = dados[j - 1];
    }
    dados[j] = chave;
}

int encontrar_fim_heap(const int original[], const int parcial[], int tamanho) {
    int posicao = tamanho - 1;
    while (posicao >= 0 && original[posicao] == parcial[posicao]) {
        posicao--;
    }
    return posicao;
}

void executar_um_passo_heapsort(int arr[], int tamanho) {
    int posicao_heap = encontrar_fim_heap(arr, arr, tamanho); // Simplificação para exemplo
    trocar_elementos(arr, 0, posicao_heap);
    percolar_para_baixo(arr, posicao_heap - 1, 0);
}

int main() {
    int n_elementos;
    int sequencia_original[MAX_TAMANHO];
    int sequencia_parcial[MAX_TAMANHO];

    scanf("%d", &n_elementos);

    for (int i = 0; i < n_elementos; i++) {
        scanf("%d", &sequencia_original[i]);
    }

    for (int i = 0; i < n_elementos; i++) {
        scanf("%d", &sequencia_parcial[i]);
    }

    int tipo_ordenacao = eh_heap_raiz_maximo(sequencia_parcial, n_elementos);

    if (tipo_ordenacao) {
        printf("Heap Sort\n");
        executar_um_passo_heapsort(sequencia_parcial, n_elementos);
    } else {
        printf("Insertion Sort\n");
        int posicao_inicio = 0;
        while (posicao_inicio < n_elementos - 1 && sequencia_parcial[posicao_inicio] <= sequencia_parcial[posicao_inicio + 1]) {
            posicao_inicio++;
        }
        realizar_passo_insercao(sequencia_parcial, n_elementos, posicao_inicio + 1);
    }

    imprimir_sequencia(sequencia_parcial, n_elementos);

    return 0;
}