Encontrando a posição de um elemento
Há diversas perguntas que podemos fazer para um array. Podemos perguntar:
Qual é o menor elemento?
Qual é o maior elemento?
Qual está no meio?
Para isto, vimos diversas técnicas para arranjar isto, seja para ordenar e assim responder diversas perguntas, ou simplesmente, para responder qual é o maior e menor.
Mas existem outras perguntas importantes que podemos querer fazer para um array... Por exemplo, se eu fiz uma prova e não fui tão bem. Tirei uma nota 7.
A nota 7 é boa ou ruim? Preciso observar as notas dos outros alunos e saber quais foram os resultados. Se todos tiraram uma nota abaixo de 7, a minha nota será um bom resultado. Porém, se todos tiverem tirado notas acima de 7, não será um bom resultado.
É importante comparar a minha nota com a pontuação dos demais ou seja qual a minha posição relativa às demais notas.
Para isso existe o algoritmo de posição relativa.
Implementando o encontra menores
Nós queremos descobrir quantas pessoas tiraram uma nota menor do que a minha.
Primeiro, vamos criar o método main(). Depois vou abrir o código e vou copiar as notas, e trabalhar com elas.
public static void main(String[] args) {
Nota[] notas = {
new Nota("andre", 4),
new Nota("carlos", 8.5),
new Nota("ana", 10),
new Nota("jonas", 3),
new Nota("juliana", 6.7),
new Nota("guilherme", 7),
new Nota("paulo", 9),
new Nota("mariana", 5),
new Nota("lucia", 9.3),
};
}
Estas são as notas que tínhamos no nosso sistema. Agora queremos encontrar todas as notas que tiraram uma nota menor do que a do Guilherme. Vamos extrair o Guilherme, considerando-o como uma única variável.
public static void main(String[] args) {
Nota guilherme = new Nota("guilherme", 7);
Nota[] notas = {
new Nota("andre", 4),
new Nota("carlos", 8.5),
new Nota("ana", 10),
new Nota("jonas", 3),
new Nota("juliana", 6.7),
guilherme,
new Nota("paulo", 9),
new Nota("mariana", 5),
new Nota("lucia", 9.3),
};
}
Especificaremos que queremos encontrar as pessoas com notas menores do que o Guilherme (encontraMenores(guilherme)).
encontraMenores(guilherme);
Para isto teremos que incluir também o array.
encontraMenores(guilherme, notas);
Vamos criar a função?
private static void encontraMenores(guilherme, Nota[] notas) {
}
Agora começou o nosso trabalho: iremos procurar quem tem a nota menor do que o Guilherme dentro do array. Qual foi o algoritmo que usamos mentalmente? Quando observamos todas as notas, analisamos cada uma por vez. Por isto, no nosso código precisamos criar um for.
for(int atual = 0; atual < notas.length; atual++) {
}
Analisaremos as notas, se elas forem menores do que a do Guilherme, teremos encontrado o elemento!
Nota nota = notas[atual];
Se (if) a nota (nota.getValor) for menor do que a do Guilherme (guilherme.getValor) daremos um "joinha, achei!"
if(nota.getValor() < guilherme.getValor()) {
// joinha, achei!
}
Quando calculamos mentalmente, o que faríamos em seguida? Somaríamos +1 na variável. Então, precisavamos em alguma parte, começar do 0. Vamos começar fora do laço.
int menores = 0;
E o trecho do código ficará assim:
private static void encontraMenores(Nota guilherme, Nota[] notas) {
int menores = 0;
for(int atual = 0; atual < notas.length; atual++) {
Nota nota = notas[atual];
Cada vez que encontrarmos um nota menor, iremos somar +1 na variável menores.
if(nota.getValor() < guilherme.getValor()) {
menores = menores + 1;
}
Que podemos traduzir para menores ++.
if(nota.getValor() < guilherme.getValor()) {
menores = menores++;
}
Ao somarmos um ao número de notas menores, o algoritmo irá passar para a próxima nota continuamente.
No fim, pediremos para ele retornar (return) o número de notas menores.
return menores;
Precisamos que o método retorne int:
private static int encontraMenores(guilherme, Nota[] notas) {
}
Iremos encontrar a quantidade de menores. Vamos acrescentar isto no código...
int menores = encontraMenores(Nota guilherme, notas);
E depois, imprimir o Número de menores é o valor de menores.
int menores = encontraMenores(guilherme, notas);
System.out.println("Número de menores: " + menores);
Será que o programa irá imprimir 4? Rodaremos o programa, clicamos no botão à direita, depois em Run As, em seguida, em Java Aplication. O resultado será:
Número de menores: 4
O que o algoritmo fez? Ele passou por cada elemento, verificando quantas notas menores do que a minha tinham entro do array.
Podemos alterar o nome da variável guilherme, para busca, porque nem sempre estou encontrando as menores baseadas no Guilherme. Iremos alterar a seguinte linha:
private static void encontraMenores(Nota guilherme, Nota[] notas) {
Que receberá o novo nome da variavel, busca.
private static void encontraMenores(Nota busca, Nota[] notas) {
Faremos o mesmo com a linha:
if(nota.getValor() < guilherme.getValor()) {
Com a alteração será:
if(nota.getValor() < busca.getValor()) {
Após as modificações, nosso código ficará assim:
private static void encontraMenores(Nota busca, Nota[] notas) {
int menores = 0;
for(int atual = 0; atual < notas.length; atual++) {
Nota nota = notas[atual];
if(nota.getValor() < busca.getValor()) {
menores = menores ++;
}
}
return menores;
}
}
A variável é a nota que estamos buscando, verificamos o valor dela e se é maior ou menor. Veremos que o nosso código está funcionando bem.
Então, vamos rever o que fizemos: tínhamos diversas notas e queríamos encontrar as que eram menores do que a do Guilherme. Sabemos que quando realizamos este tipo de ação, iremos analisar todos os itens. À medida que olhamos todos, contamos quatro notas menores. O algoritmo que implementamos determina quantas notas são menores do que a minha.
Agora vamos pensar no seguinte. Se o vetor estivesse ordenando qual seria a diferença para obter o total de alunos com nota menor do que a minha? Qual seria o custo deste algoritmo?
Particionando o conjunto com pivot ( particionador )
Agora que temos nosso array de elementos, em que estou posicionado no meio, queremos fazer a divisão do array em duas partes. Assim, quando eu for para a posição adequada, todos os demais que estiverem na minha esquerda terão notas menores. E todos que estiverem à direita terão notas maiores. Mesmo que cada parte não fique ordenada... O importante é que eu particione, que eu divida estes dois pedaços. Os menores irão para esquerda e os maiores, para a direita. Isto é, irei me deslocar para indicar quais são os menores e os maiores. Quem é maior ou menor, é irrelevante para mim. O importante é que eu esteja na posição que eu mereço.
Implementando minha posição
Queremos escrever um algoritmo que não apenas encontre o número de elementos menores, mas que também posicione o pivô (o último elemento) adequadamente. Assim poderemos separar as notas menores das maiores.
Criaremos uma nova classe, que se chamará TestaPivota, porque nós iremos pivotar. Dentro da classe, criaremos o método main(), onde colocaremos as notas dos alunos.
public static void main(String[] args) {
Nota guilherme = new Nota("guilherme", 7);
Nota[] notas = {
new Nota("andre", 4),
new Nota("carlos", 8.5),
new Nota("ana", 10),
new Nota("jonas", 3),
new Nota("juliana", 6.7),
guilherme,
new Nota("paulo", 9),
new Nota("mariana", 5),
new Nota("lucia", 9.3)
};
}
Nossa lista terá uma única diferença: o Guilherme não ficará mais no meio, porque nós definimos que o pivô sempre será o último elemento. Então ele trocou de lugar com a Lúcia. Vamos trocar os elementos de posição:
public static void main(String[] args) {
Nota guilherme = new Nota("guilherme", 7);
Nota[] notas = {
new Nota("andre", 4),
new Nota("carlos", 8.5),
new Nota("ana", 10),
new Nota("jonas", 3),
new Nota("juliana", 6.7),
new Nota("paulo", 9),
new Nota("mariana", 5),
new Nota("lucia", 9.3)
guilherme,
};
}
A nova ordem será: André, Carlos, Ana, Jonas, Juliana, Paulo, Mariana, Lúcia e Guilherme. Agora queremos que o nosso algoritmo quebre o array em duas partes (quebraNoPivo) e depois faça outras ações. Após dividir os elementos, as notas estarão disponíveis. Vamos especificar isto no código:
Nota[] notas = {
new Nota("andre", 4),
new Nota("carlos", 8.5),
new Nota("ana", 10),
new Nota("jonas", 3),
new Nota("juliana", 6.7),
new Nota("paulo", 9),
new Nota("mariana", 5),
new Nota("lucia", 9.3)
guilherme,
};
quebraNoPivo(notas);
}
Em seguida, iremos implementar o método quebraNoPivo. Como ele funciona? Nós já tínhamos encontrado uma forma de descobrir o menor elemento da lista. Primeiro, especificávamos quais elementos seriam analisados, para isto precisávamos saber o valor do iniciale do termino.
private static void quebraNoPivo(Nota[] notas, int inicial, int termino) {
}
Isto significa que iremos do 0 até notas.length.
quebraNoPivo(notas, 0, notas. length);
Este era o problema que queríamos resolver. E quem é o pivô? O elemento que está na última posição que iremos analisar. Como temos nove elementos, isto significa que ele estará na posição 8. Logo, ele será o item da posição termino - 1. Caso tivéssemos cinco elementos, o pivô estaria na posição 4. Se fossem dezessete elementos, ele estaria na posição 16. O último elemento sempre será o pivô.
private static void quebraNoPivo(Nota[] notas, int inicial, int termino) {
Nota pivo = notas[termino - 1];
}
Agora queremos varrer todo o array. Por isso, escreveremos o for:
for(int analisando = 0; analisando < termino; analisando++) {
}
Nosso código ficará assim:
private static void quebraNoPivo(Nota[] notas, int inicial, int termino) {
Nota pivo = notas[termino - 1];
for(int analisando = 0; analisando < termino; analisando++) {
}
}
Iremos varrer o array inteiro, porém não será preciso passar por todos os itens, afinal o Guilherme será o último elemento. Por isso, podemos ignorá-lo e não o analisaremos. Vamos alterar o nosso for e especificar que devemos analisar até o termino -1.
for(int analisando = 0; analisando < termino - 1; analisando++) {
}
Não precisamos comparar as demais notas com o pivô. O que faremos em seguida? Analisaremos a nota atual (notas[analisando]).
for(int analisando = 0; analisando < termino - 1; analisando++) {
Nota atual = notas[analisando];
}
Será que a nota atual é mais baixa? Se (if) a atual.getValor() for menor ou igual ao pivo.getValor(), ficará posicionado à esquerda. Para isto, usaremos a variável menoresEncontrados++
for(int analisando = 0; analisando < termino - 1; analisando++) {
Nota atual = notas[analisando];
if(atual.getValor() <= pivo.getValor()) {
menoresEncontrados++;
}
}
Agora precisaremos calcular os menoresEncontrados
private static void quebraNoPivo(Nota[] notas, int inicial, int termino) {
int menoresEncontrados = 0;
}
Vamos revisar o que estamos fazendo: menoresEncontrado começa com 0, depois vamos analisar todos os elementos com exceção do pivô que será ignorado, e contaremos quantos são menores do que o Guilherme. No fim, o que faremos? Já sabemos que o pivô ficará na posição menoresEncontrados. Isto significa que iremos trocar no array, o elemento que estiver na posição termino -1 com o que estiver na posição menoresEncontrados.
troca(notas, termino -1, menoresEncontrados);
Nosso objetivo é trocar os dois itens de posição no fim. Vamos implementar a função troca()? Nós queremos receber o de e o para. Então, nota1 será o notas[de] e o nota2será o notas[para].
private static void troca(Nota[] notas, int de, int para) {
Nota nota1 = notas[de];
Nota nota2 = notas[para];
notas[para] = nota1;
notas[de] = nota2;
}
Trocamos de lugar os elementos que estavam no de para a posição dos que estavam no para e vice-versa.
Depois que rodarmos a quebraNoPivo temos que verificar se o Guilherme caiu na casa correta, na posição 4. Faremos um for para cada uma das notas. Teremos a nota atual (notas[atual]) e iremos imprimir o aluno (nota.getAluno) e o valor (nota.getValor):
quebraNoPivo(notas,0, notas.length);
for(int atual = 0; atual < notas.length; atual++) {
Nota nota = notas[atual];
System.out.println(nota.getAluno() + " " + nota.getValor());
}
Vamos testar e ver se o código funciona? Clicamos em Run As, depois em Java Application, e o resultado será:
andre 4.0
carlos 8.5
ana 10.0
jonas 3.0
guilherme 7.0
lucia 9.3
paulo 9.0
mariana 5.0
juliana 6.7
O Guilherme ficou na posição adequada, porque nós contamos quantas pessoas eram menores do que o pivô e o colocamos na posição 4. Lembrando que o array começa com a posição 0. Assim, conseguimos colocar o Guilherme na posição certa.