Seleção do k-ésimo menor elemento

Encontrar o elemento mínimo ou máximo em um conjunto de números é uma tarefa computacional
básica que aprendemos resolver na primeira disciplina de programação de um curso
superior da área da Computação. Nesta atividade, devemos solucionar uma generalização desse
problema, conforme estudamos nas aulas:
Problema da seleção do k-ésimo menor elemento: dados um conjunto A com n números
inteiros e um número inteiro k, onde 1  k  n, encontrar o elemento x em A
que é maior ou igual a exatamente k ? 1 elementos de A.
Você deverá implementar quatro estratégias para solucionar tal problema, conforme descrição
a seguir. Além disso, você deve medir os tempos de execução desses algoritmos e compará-los.
Para realizar essa tarefa, será necessário gerar conjuntos de dados para realização de experimentos
dessas estratégias.
Você deve implementar as seguintes estratégias para resolver o problema da seleção do k-
ésimo menor elemento em um vetor A:
1. Ordene o vetor A e devolva o elemento na posição k. Este é o k-ésimo menor elemento do
vetor A;
2. Construa uma lista de min-prioridades no vetor A. Remova os k primeiros elementos dessa
lista de min-prioridades, imprimindo o valor do último elemento removido. Esse elemento
é o k-ésimo menor elemento de A;
3. Faça a seleção aleatorizada. Isto é, execute o algoritmo randomized-select para encontrar
o k-ésimo menor elemento de a;
4. Faça a seleção (de tempo de execução pior caso linear). Ou seja, execute o algoritmo SELECT
para encontrar o k-ésimo menor elemento de A.
Observe que você pode escolher qualquer algoritmo de ordenação por comparação que estudamos
para implementar a estratégia 1.

Programa, entrada e saída
Considere os seguintes parâmetros para execução dos experimentos, que são fornecidos como
entrada:
inc é o tamanho inicial de um vetor de entrada;
• fim é o tamanho final;
• stp é o intervalo entre dois tamanhos; e
• rpt é o número de repetições a serem realizadas.
Para realizar experimentos com esses algoritmos, você deve construir 4 tipos de conjuntos de
dados de entrada, conforme a descrição a seguir:
1. Vetor aleatório: cada conjunto de entrada A deve conter números inteiros não negativos
escolhidos (pseudo)aleatoriamente. Um tal conjunto de números A deve ter n números.
Os valores de n variam, para cada conjunto construído, de acordo com os parâmetros inc
(valor inicial), fim (valor final) e stp (intervalo entre dois tamanhos). Por exemplo, se inc =
100, fim = 1000 e stp = 10, então os tamanhos dos vetores de entrada A que devem ser
construídos são n = 100; 110; 120; : : : ; 990; 1000. Suponha que o valor máximo possível é
20000.
Em seguida, você deve sortear um número k no intervalo de 1 a n. Um conjunto A com n
elementos e um número k, com 1  k  n, assim gerados são chamados de caso de teste.
Para cada caso de teste, você deve executar os quatro algoritmos mencionados na seção 1
para selecionar o k-ésimo menor elemento desse conjunto A de n números inteiros. Para
cada n, você deve repetir o processo acima um determinado número rpt de vezes, obtendo
então a média dos tempos medidos.
A saída deste experimento consiste de uma primeira linha contendo o rótulo [[RANDOM]],
especificando o conjunto de dados sendo usado, uma segunda linha contendo os rótulos da
quantidade de elementos n e a identificação de cada um dos algoritmos. Cada linha a seguir
contém o valor da quantidade de elementos n de um caso de teste e as médias dos tempos
gastos da execução de cada algoritmo.
2. Vetor reverso: cada conjunto de entrada A deve conter números inteiros não negativos escolhidos
(pseudo)aleatoriamente e arranjados em ordem decrescente. Um tal conjunto de
números A deve ter n números. Os valores de n variam, para cada conjunto construído, de
acordo com os parâmetros inc (valor inicial), fim (valor final) e stp (intervalo entre dois
tamanhos). Por exemplo, se inc = 10, fim = 100 e stp = 5, então os tamanhos dos vetores
de entrada A que devem ser construídos são n = 10; 15; 20; : : : ; 95; 100. Suponha que o valor
máximo possível é 20000.
Em seguida, você deve sortear um número k no intervalo de 1 a n. Um conjunto A com n
elementos e um número k, com 1  k  n, assim gerados são chamados de caso de teste.
Para cada caso de teste, você deve executar os quatro algoritmos mencionados na seção 1
para selecionar o k-ésimo menor elemento desse conjunto A de n números inteiros. Para
cada n, você deve repetir o processo acima um determinado número rpt de vezes, obtendo
então a média dos tempos medidos.
A saída deste experimento consiste de uma primeira linha contendo o rótulo [[REVERSE]],
especificando o conjunto de dados sendo usado, uma segunda linha contendo os rótulos da
quantidade de elementos n e a identificação de cada um dos algoritmos. Cada linha a seguir
contém o valor da quantidade de elementos n de um caso de teste e os tempos gastos da
execução de cada algoritmo.
3. Vetor ordenado: cada conjunto de entrada A deve conter números inteiros não negativos
escolhidos (pseudo)aleatoriamente e arranjados em ordem crescente. Um tal conjunto de
números A deve ter n números. Os valores de n variam, para cada conjunto construído, de
acordo com os parâmetros inc (valor inicial), fim (valor final) e stp (intervalo entre dois
tamanhos). Por exemplo, se inc = 1000, fim = 10000 e stp = 1000, então os tamanhos dos
vetores de entrada A que devem ser construídos são n = 1000; 2000; 3000; : : : ; 9000; 10000.
Suponha que o valor máximo possível é 20000.
Em seguida, você deve sortear um número k no intervalo de 1 a n. Um conjunto A com n
elementos e um número k, com 1  k  n, assim gerados são chamados de caso de teste.
Para cada caso de teste, você deve executar os quatro algoritmos mencionados na seção 1
para selecionar o k-ésimo menor elemento desse conjunto A de n números inteiros. Para
cada n, você deve repetir o processo acima um determinado número rpt de vezes, obtendo
então a média dos tempos medidos.
A saída deste experimento consiste de uma primeira linha contendo um rótulo [[SORTED]],
especificando o conjunto de dados sendo usado, uma segunda linha contendo os rótulos da
quantidade de elementos n e a identificação de cada um dos algoritmos. Cada linha a seguir
contém o valor da quantidade de elementos n de um caso de teste e os tempos gastos da
execução de cada algoritmo.
4. Vetor quase ordenado: cada conjunto de entrada A deve conter números inteiros não negativos
escolhidos (pseudo)aleatoriamente e “quase” ordenado crescentemente. Para obter
um vetor dessa forma, você deve arranjar o vetor crescentemente, escolher 10% dos seus
elementos e então embaralhá-los. Um tal conjunto de números A deve ter n números. Os
valores de n variam, para cada conjunto construído, de acordo com os parâmetros inc (valor
inicial), fim (valor final) e stp (intervalo entre dois tamanhos). Por exemplo, se inc = 200,
fim = 20000 e stp = 200, então os tamanhos dos vetores de entrada A que devem ser
construídos são n = 200; 400; 600; : : : ; 19800; 20000. Suponha que o valor máximo possível é
20000.
Em seguida, você deve sortear um número k no intervalo de 1 a n. Um conjunto A com n
elementos e um número k, com 1  k  n, assim gerados são chamados de caso de teste.
Para cada caso de teste, você deve executar os quatro algoritmos mencionados na seção 1
para selecionar o k-ésimo menor elemento desse conjunto A de n números inteiros. Para
cada n, você deve repetir o processo acima um determinado número rpt de vezes, obtendo
então a média dos tempos medidos.
A saída deste experimento consiste de uma primeira linha contendo o rótulo [[nearly
sorted]], especificando o conjunto de dados sendo usado, uma segunda linha contendo
os rótulos da quantidade de elementos n e a identificação de cada um dos algoritmos. Cada
linha a seguir contém o valor da quantidade de elementos n de um caso de teste e os tempos gastos da execução de cada algoritmo.