%cabeçalho para todos os capítulos
%\input{cabecalho}

%\begin{document}

%Opções para o pacote listings
%\input{listingOptions}

\chapter{Busca e ordenação}
\label{cap:busca-ordenacao}

\begin{center}
\shabox{
  \begin{Bitemize}
    \item[]\textbf{Quais novidades veremos nesta aula?}
    \item Busca em array 
    \item Ordenação em arrays
  \end{Bitemize}
} % \shabox
\end{center}
\bigskip

\section{Busca}

Como já vimos, arrays podem guardar muita informação embaixo de uma
única variável. Uma das operações mais comuns que podemos fazer em um
array é buscar um elemento nele. Isso pode ser útil para saber se um
elemento já está lá para recuperar outras informações dos objetos
armazenados. Lembrando do nosso EP, pense na busca de um CD pelo título.
Sabendo onde o CD está podemos recuperar outras informações, como as
faixas que o compõe, sua duração, etc.

Mas como podemos buscar algo? Vamos primeiro aprender a forma mais
simples de busca: a busca seqüencial. Neste caso, ``varre-se'' o array do
início ao fim até encontrarmos o elemento desejado. Isso pode ser feito
usando um simples laço \texttt{while}. Considere que \texttt{biblioteca} é um array de
objetos da classe \texttt{Livro}. O array está cheio de livros válidos (ou seja
tem elementos de 0 a \texttt{bilbioteca.length} - 1. Considere ainda que esses
objetos disponibilizam um método \texttt{pegaNome} que retorna o nome do livro.
Veja abaixo um exemplo de código para buscar um livro de nome ``Amor em
tempos de cólera''.

\begin{lstlisting}
int i = 0;
while((i < biblioteca.length) && 
      (biblioteca[i].pegaNome().equals("Amor em tempos de cólera") == false))
  i = i + 1;
\end{lstlisting}

Ao final, tempos duas possibilidades:

\begin{itemize}
  \item \texttt{i < bibliotecas.length}:  Neste caso o livro está na posição \texttt{i}
      do array. De posse desse índice podemos manipular o livro
      encontrado como quisermos.
  \item \texttt{i == bibliotecas.length}: Já aqui, o livro não foi encontrado
      pois passamos do final do vetor.
\end{itemize}

Por fim, devemos destacar que há uma certa sutileza no código acima.
Note que no segundo caso não poderíamos acessar no vetor na posição \texttt{i}.
Isso não ocorre devido a ordem das condições do \texttt{while}. Como a primeira
condição é falsa, o computador não precisa testar a segunda para saber
que a expressão é falsa, já que a condição é um ``e-lógico''.


\section{Pondo ordem na casa}

Uma das tarefas mais comuns em programas é ordenar coisas. Muitas vezes
é mais fácil trabalhar com os elementos de um vetor ordenados. Um bom
exemplo é a busca. Caso o vetor esteja ordenado pela ``chave'' de busca é
possível fazer algo bem mais eficiente do que a busca seqüencial descrita
acima.

Mas como podemos ordenar os elementos de um vetor?

Para fazer isso vamos nos lembrar de algo que universitários fazem
muito: jogar baralho. Quando temos várias cartas na mão, muitas vezes
acabamos por ordená-las. Pensem e discutam um pouco como vocês fazem
isso. Existe alguma lógica por trás da maneira que você move as cartas
para lá e para cá? Será que você poderia descrever um algoritmo para
ordenar as cartas?

Agora vamos fazer a brincadeira ficar um pouco mais complicada. Agora,
seja qual for o algoritmo que você descreveu acima, tente pensar como
adaptá-lo para incoporar duas restrições. Primeiro considere que você não
pode olhar todas as cartas de uma vez, no máximo duas cartas podem ficar
visíveis ao mesmo tempo. Vale, porém, anotar a posição onde uma carta do
seu interesse está. Segundo considere que você não pode simplesmente
mover as cartas de um lugar para outro, mas somente pode trocar duas
cartas de posição.

Aposto que a solução imaginada poderia ser descrita em Java por um dos
algoritmos abaixo. Neles deseja-se ordenar os elementos de 0 até \texttt{final}
no vetor de inteiros \texttt{numeros}. Cada algoritmo é escrito como um método.

\begin{enumerate}
  
\item \textbf{Seleção direta}.  Neste algoritmo, a cada passo buscamos o menor
  elemento no vetor e o levamos para o início. No passo seguinte buscamos o
  segundo menor elemento e assim por diante.

\begin{lstlisting}
void selecaoDireta(int []numeros)
{ 
  int i, j, indiceDoMinimo, temp;
  int fim = numeros.length;

  for (i = 0; i < fim - 1; i++)
  {
    // Inicialmente o menor elemento já visto é o primeiro elemento. 
    indiceDoMinimo = i;
    for (j = i + 1; j < fim; j++)
    {
      if (numeros[j] < numeros[indiceDoMinimo])
        indiceDoMinimo = j;
    }
    // Coloca o menor elemento no inicio do sub-vetor atual. Para isso, troca
    // de lugar os elementos nos índices i e indiceDoMinimo.
    temp = numeros[i];
    numeros[i] = numeros[indiceDoMinimo];
    numeros[indiceDoMinimo] = temp;
  }
}
\end{lstlisting}

\item \textbf{Inserção direta}. A cada passo aumenta a porção ordenada do vetor
  de uma posição, inserindo um novo elemento na posição correta.

\begin{lstlisting}
void insercaoDireta(int []numeros, int fim)
{
  int i, j, numeroAInserir;
  
  // Cada passo considera que o vetor à esquerda de i está ordenado.
  for (i = 1; i < fim; i++)
  {
    // Tenta inserir mais um número na porção incial do vetor que
    // já está ordenada empurrando para direita todos os elementos
    // maiores do que numeroAInserir.
    numeroAInserir = numeros[i];
    j = i;
    while((j > 0) && (numeros[j-1] > numeroAInserir))
    {
      numeros[j] = numeros[j-1];
      j--;
    }
    numeros[j] = numeroAInserir;
  }
}
\end{lstlisting}

\item \textbf{Método da bolha}. Esse método testa se a seqüência está
  ordenada e troca o par de elementos que gerou o problema. Pense no vetor
  como um tubo de ensaio vertical onde os elementos mais leves sobem à
  superfície como bolhas.

\begin{lstlisting}      
void bolha(int []numeros, int fim)
{
  int i, j, temp;
  
  for(i = fim - 1; i > 0; i--)
    // Varre o vetor desdo início procurando erros de ordenação.
    // Como a cada passagem o maior elemento sobe até sua 
    // posição correta, não há necessidade de ir até o final.
    for (j = 1; j <= i; j++)
      // Se a ordem está errada para o par j-1 e j
      if (numeros[j-1] > numeros[j])
      {
        // Troca os dois de lugar
        temp = numeros[j-1];
        numeros[j-1] = numeros[j];
        numeros[j] = temp;
      }
}
\end{lstlisting}

\end{enumerate}

\emph{Obs:} Sempre que pedimos para o \texttt{System.out.print} ou 
\texttt{System.out.println} imprimirem um array ou outro objeto qualquer de uma 
classe definidas por nós ele imprime apenas um número estranho (que representa o 
lugar onde o objeto está armazenado na memória). Deste modo é interessante escrever
um método \texttt{imprimeVetor} para que o computador mostre todos os elementos
válidos de seu vetor. Esse método é fácil, basta varrer o vetor e pedir
a cada passo que o computador imprima o elemento atual (ou a parte dele
que nos interessa ver).

\section{Exercícios}

\begin{enumerate}
\item Vamos descobrir como os algoritmos acima descritos se comportam à medida
  que aumentamos o tamanho do vetor a ser ordenado? Para cada um dos
  algoritmos acima execute o algoritmo utilizando como entrada vetores de
  diferentes tamanhos. O tempo gasto para realizar a ordenação cresce
  linearmente com o tamanho do vetor?

\end{enumerate}

