Considere que uma rede de varejo resolva consolidar a base...

Considere que uma rede de varejo resolva consolidar a base de dados de suas M lojas, o que resulta em uma tabela X não ordenada com N registros de clientes, possivelmente repetidos. Devido à necessidade de se criar uma tabela Y contendo os clientes da tabela X com as repetições eliminadas, cogita-se utilizar dois possíveis algoritmos, os quais são apresentados a seguir.

Algoritmo A, que executa as seguintes ações:

1. Cria uma tabela Y inicialmente vazia;

2. Percorre a tabela X, cliente por cliente, verificando se cada um deles já está na tabela Y. Caso não esteja, insere na tabela Y o cliente que está faltando. Algoritmo B, que executa as seguintes ações:

1. Cria uma tabela Y inicialmente vazia;

2. Ordena a tabela X usando o algoritmo quicksort;

3. Insere, na tabela Y, o cliente da primeira posição da tabela X;

4. Percorre a tabela X, cliente por cliente, a partir do segundo cliente, verificando se cada cliente é igual ao anterior. Caso não seja, insere o cliente na tabela Y.

Como resultado das ações tanto do algoritmo A quanto do algoritmo B, a tabela Y gerada ao final conterá os clientes da tabela X com as repetições eliminadas.

A partir dessas informações, observe o código em linguagem C apresentado a seguir.

Com base nos dados apresentados, faça o que se pede nos itens a seguir.

a) Determine o número máximo de comparações executadas no passo 2 do algoritmo A. (valor: 2,0 pontos)

b) Determine o número máximo de comparações executadas no passo 4 do algoritmo B. (valor: 2,0 pontos)

c) Na implementação recursiva do programa apresentado, quais são os valores dos parâmetros a, b, c e d? (valor: 2,0 pontos)

d) Escreva o corpo da função particiona em linguagem C utilizando a função auxiliar troca, a qual foi definida anteriormente. (valor: 4,0 pontos)