Questão 55 — UNIRIO 2019 Cesgranrio

O programa Java a seguir ordena um array com 64 números inteiros gerados aleatoriamente. import java.util.Random; public class Main { static int cont=0; static int nRep=10000; static int tam=64; static int particao(int arr[], int inicio, int fim) { int pivot = arr[fim]; int i = (inicio-1); for (int j = inicio; j < fim; j++) { cont++; //PASSO 1 if (arr[j] <= pivot) { i++; int trocaTemp = arr[i]; arr[i] = arr[j]; arr[j] = trocaTemp; } } int trocaTemp = arr[i+1]; arr[i+1] = arr[fim]; arr[fim] = trocaTemp; return i+1; } static void quickSort(int arr[], int inicio, int fim) { if (inicio < fim) { int particaoIndex = particao(arr, inicio, fim); quickSort(arr, inicio, particaoIndex-1); quickSort(arr, particaoIndex+1, fim); } } public static void main(String[] args) { Random g=new Random(); for(int i=0;i<nRep;i++) { int vet[]=new int[tam]; for(int j=0;j<tam;j++) vet[j]=g.nextInt(100); quickSort(vet,0,tam-1); } System.out.println(cont/nRep); //PASSO 2 } } 16 No interior do comando for do método particao(), foi inserido um comando (cont++) que incrementa a variável estática cont de uma unidade a cada iteração do comando for. Após a execução do método quickSort(), a variável cont irá conter o número total de iterações realizadas para que o array fosse ordenado. A função de ordenação, de nome quickSort, é chamada 10000 vezes, com diferentes arrays de números inteiros, gerados aleatoriamente, em cada chamada. Sendo assim, o valor exibido pelo método println(), ao término do programa, será a média do número de iterações das 10000 vezes em que o array foi ordenado. Seja p o número exibido pelo método println() em consequência da execução do programa acima. Seja t o número obtido a partir da complexidade do caso médio do algoritmo quicksort aplicada ao array do programa acima. Seja m o valor absoluto da diferença entre t e p, isto é, m=|t-p| . Qual valor de p resulta no menor valor de m?

1. A361
2. B720
3. C1024
4. D2048
5. E4096

Gabarito oficial: A