8OUTROS MÉTODOS

Neste capítulo serão abordados alguns métodos computacionais que são úteis em diversasaplicações distintas, mas que não se enquadram nos assuntos discutidos nos capítulos anteri-ores.

CLASSIFICAÇÃO (sorting)Em muitas situações, o programador está de posse de um conjunto de objetos de dados que

não possui uma organização ou ordenamento evidente. Neste caso, com frequência é necessárioou desejável organizar esses dados a partir de algum critério definido. Por exemplo, dado umvetor contendo quantidades numéricas que se distribuem de forma aleatória ou de uma formanão pré-determinada ao longo do vetor, deseja-se então organizar esses dados em ordem cres-cente ou decrescente. Este processo de organização de objetos de dados de acordo com algumcritério é denominado classificação (sorting).

Existem diversos algoritmos para implementar sorting. Dado um conjunto de N objetos dedados, os algoritmos mais eficientes que realizam sorting irão demandar um número máximoda ordem de N log2 N operações de ponto flutuante para realizar a classificação dos dados. Doisdos algoritmos mais eficientes conhecidos são o quicksort e o heapsort. Aqui será discutido oalgoritmo de inserção direta (straight insertion), o qual é o mais simples de ser implementado,mas pode demandar até N2 operações para a sua realização.

INSERÇÃO DIRETA (straight insertion)O algoritmo de inserção direta, como mencionado, pode demandar até N2 operações para

realizar o sorting, mas, em compensação, é o mais simples de ser implementado.Imagine um baralho de cartas embaralhadas. Para organizar as cartas em ordem crescente,

por exemplo, primeiro organiza-se as mesmas em uma linha; então compara-se a segunda coma primeira e organiza-se as mesmas na ordem escolhida. Depois compara-se a terceira comas duas primeiras e realiza-se novamente a organização entre as três. Este processo é entãorepetido até o final do baralho.

A figura 8.1 exemplifica a aplicação do algoritmo para um vetor contendo números inteirospositivos. Neste exemplo, um conjunto de 7 números inteiros necessitou de um total de 11permutações para a classificação, mas poderiam ser necessárias até 72 = 49 permutações.

O algoritmo 8.1 apresenta uma implementação da inserção direta para organizar um vetorem ordem crescente. Os dados são de algum tipo numérico ou de algum outro tipo para o qualpossam ser definidas as expressões relacionais.1 O algoritmo permite a classificação de umaseção do vetor ou do vetor inteiro, sendo que inf (A) e sup (A) são, respectivamente, os limitesinferior e superior do vetor A.

A sub-rotina sort_pick (programa 8.1) implementa o algoritmo 8.1 em Fortran para classificartodo o vetor real arr em ordem crescente. Na saída, o vetor é retornado à unidade invocadoracom os elementos de arr classificados.

1Isto é, para o qual expressões como a > b (a, b ∈ A) façam sentido.

125

126

-∞ -∞ -∞ -∞ -∞ -∞ -∞1 51 38 38 38 27 27 27

2 38 51 51 51 38 38 38

3 89 89 89 75 51 44 444 75 75 75 89 75 51 515 27 27 27 27 89 75 686 44 44 44 44 44 89 757 68 68 68 68 68 68 89

i= 2 i= 3 i= 4 i= 5 i= 6 i= 7 done

Figura 8.1: Aplicação do algoritmo de inserção direta para organizar um vetor de números inteiros em ordemcrescente.

Algoritmo 8.1 Método da inserção direta para classificar um vetor de números em ordem cres-cente.

Entrada: Vetor A; inteiros p e r, tais que inf (A) 6 p 6 r 6 sup (A).Saída: Vetor A, com os elementos da seção A (p : r) classificados. Os demais elementos de Anão são alterados.Para i = p+ 1, p+ 2, . . . , r faça

temp = A (i)j = iEnquanto que (j > p e A (j − 1) > temp) faça

A (j) = A (j − 1)j = j − 1

FimA (j) = temp

Fim Laço

Listing 8.1: Sub-rotina sort_pick: recebe como entrada um vetor real arr e usa inserção direta para classificaro vetor em ordem crescente. Na saída, o vetor arr é retornado com seus elementos classificados.

subroutine straight_sort ( arr )impl ic i t nonereal , dimension ( : ) , intent ( inout ) : : arrinteger : : i , j , nreal : : an= size ( arr )do j= 2, n

a= arr ( j )do i= j − 1, 1 , −1

i f ( arr ( i ) <= a ) ex i tarr ( i + 1)= arr ( i )

end doarr ( i + 1)= a

end doreturnend subroutine straight_sort

Autor: Rudi Gaelzer – IF/UFRGS Início: 10/2019 Impresso: 28 DE OUTUBRO DE 2019