Física Computacional - FSC-5705

só um divisor

Ordenamento de dados

Em computação e matemáticas um algoritmo de ordenamento é um algoritmo que põe elementos de um vetor em uma sequência dada por uma relação de ordem, isto é, o resultado de saída tem de ser uma permutação --ou reordenamento-- da entrada que satisfaça a relação de ordem dada. As relações de ordem mais usadas são a ordem numérico e a ordem lexicográfico. Ordenamentos eficientes são importantes para optimizar o uso de outros algoritmos (como os de busca e fusão) que requerem listas ordenadas para uma execução rápida. Também é útil para pôr dados em forma canônica e para gerar resultados legíveis por humanos.

Neste momento estaremos interessados em trabalhar com algoritmos de ordenação numérica.

De entre os algoritmos conhecidos podemos citar alguns: ordenação por bolhas, ordenação por seleção linear, ordenação por camadas, ordenação por inserção linear, etc

Cada um desses algoritmos tem suas qualidades e desvantagens dependendo do problema a se atacado, por exemplo com o advento da programação nas placas de vídeo, um dos algoritmos que mais tem sido utilizado, dada suas caraterísticas compatíveis com a arquitetura das placas de vídeo é o algoritmo conhecido com ordenamento Radix

A continuação descreveremos dois dos algoritmos simples que permitem o ordenamento de um conjunto de dados:

Algoritmo por bolhas

Pase 50 segundos o vídeo para ir direto ao método

É o mais simples de todos (e o mais ineficiente também). A ideia do algoritmo de bolhas é comparar a pares os elementos contíguos e se eles estão desordenados é simplesmente trocar eles de lugar. Assim, suponhamos que iniciamos no elemento $i = 1$, comparamos este elemento com o elemento $2$ e caso o elemento $1$ for menor do que o elemento $2$ este permanece no seu lugar. Se elemento $1$ for maior do que o elemento $2$ este elementos trocam de lugar e a comparação agora se da entre o novo elemento $2$ e o elemento $3$ e será continuada até atingir ou um elemento maior do que ele ou o fim dos índices do vetor.

ENTRADA: $n$, $vec = \{x_0, x_1, x_2, \ldots , x_{n-1}\}$

Para $i = 0, \ldots , n-1$ faça
Para $j = 0, \ldots , n-2$ faça
Se $x_{j+1} \le x_j$ então
$\displaystyle{ \begin{array}{lcl} t & \leftarrow & x_{j+1} \\ x_{j+1} & \leftarrow & x_j\\ x_j & \leftarrow & t \\ \end{array} }$
fim do Se
fim do faça
fim do faça

SAÍDA: $vec = \{x_0, x_1, x_2, \ldots , x_n\}$ permutado

Como pode ver-se, o algoritmo é extremadamente obvio, o primeiro laço garante que pelo menos todos os $N$ elementos sejam checados uma vez. O núcleo do algoritmo está no segundo laço:

  1. Escolhe-se um elemento $j$
  2. Compara-se o elemento $j$ com o elemento $j+1$
    • Se $x_{j+1}$ for menor do que $x_j$ realizamos a troca. Para isso colocamos o valor de $x_{j+1}$ é armazenado em uma variável temporal $t$ a fim de poder utilizar a posição $j+1$; copiamos o valor de $x_{j}$ na posição $j+1$ e finalmente copiamos o valor armazenado na variável temporal na posição $j$
    • Se $x_{j+1}$ for maior do que $x_j$ não é feito nada e passamos para o próximo $j$.

Algoritmo por inserção

Ordenando um baralho

É um algoritmo que é eficiente quando aplicado a um pequeno conjunto de dados. Em termos gerais ele percorre o vetor, onde os dados estão armazenados, do índice menor para o índice maior e à medida que avança vai deixando os elemento à esquerda mais ordenados.

Especificamente, o algoritmo funciona de forma muito parecida a como muitas pessoas ordenam as cartas num jogo. Iniciamos com todas as cartas em uma mão, suponhamos que seja a esquerda. Inicialmente, consideramos que a carta mais a esquerda, por exemplo, está ordenada. Olhamos a segunda e comparamos com a primeira, se a segunda é menor colocamos a segunda na posição da primeira e a primeira na posição da segunda, assim podemos ver que temos dos subconjunto do conjunto de cartas, um que já esta ordenado (à esquerda) e outro que ainda não está. Acontinuação tomamos a terceira carta, se ela esta ordenada em relação ao conjunto ordenado, então passamos para a quarta; se essa terceira carta não não estiver ordenada, em relação ao conjunto ordenando, retiramos ela da terceira posição e colocamos na posição que deveria estar colocada, suponhamos que das três essa última seja a menor, assim ela deve ir para a primeira posição, a primeira vai para a segunda posição e a segunda vai para a terceira posição. Notem, novamente, que o conjunto à esquerda continua ordenado. Assim repetimos esse método com todas as outras baralhas que estão no conjunto à direita até não ficar nenhuma carta do lado direito.

Podemos escrever esse algoritmo em pseudo-código da seguinte forma:

ENTRADA: $n$, $vec = \{x_0, x_1, x_2, \ldots , x_{n-1}\}$

Para $i = 1, \ldots , n-1$ faça
$t \leftarrow x_i$
$j \leftarrow i$
faça
$j = j-1$
Se $x_j < t$ ou $j<=1$ Sai do laço
$x_{j+1} \leftarrow x_j $
fim do faça
$x_{j+1} \leftarrow t$
fim do faça

SAÍDA: $vec = \{x_0, x_1, x_2, \ldots , x_n\}$ permutado

O algoritmo que implementa esse método de ordenamento faz o seguinte:

  1. Pega um elemento $i$, maior do que $i=0$.
  2. Armazena numa variável temporária, $t$, o valor desse elemento $i$, ou seja, $x_i$
  3. Escolhe um outro elemento $j$ tal que $j <= i-1$
  4. Neste ponto temos duas opções
    • Se $x_j$ for maior do que $t$ (lembre que $t$ armazena o valor original de $x_i$) então $x_j$ passa para posição $x_{j+1}$, deixando um lugar na posição $j$ (Note que como $x_i$ foi inicialmente armazenado na variável temporal $t$, a posição $j+1$, que corresponde a $i$, está vacante). A continuação, escolhemos o seguinte elemento (no caso $j-1=i-2$) para realizar novamente o teste.
    • Caso $x_j$ seja menor do que $t$ (lembre que $t$ armazena o valor original de $x_i$), então não é feita a troca com nenhum elemento $j < i-1$ (a lista à esquerda está ordenada) e recolocamos a variavel temporaria na posição $i=j+1$.

Python

O python possui o método .sort() que ordena os dados de menor para maior. Se colocada a opção reverse=True:.sort(reverse=True) os dados seram ordenados de maior para menor.

A função sorted também faz a mesma função mas ele devolve os dados ordenados e assim podem ser armazenados em outra variável.

Tarefa

Implemente e teste ambos algoritmos utilizando os seguintes dados