Estrutura de Dados - Classificação de Dados

Classificação de Dados

Classificação de dados é o processo pelo qual é determinada a ordem na qual devem se apresentar as entradas de uma tabela, de modo que obedeçam à seqüência ditada por um ou mais de seus campos (chave). Estes campos são chamados de chave de classificação ou de ordenação.

Classificação Interna e Externa

O processo de classificação interna de um conjunto de dados se dá quando este conjunto é inteiramente contido na memória principal. Já a classificação dos dados não armazenada inteiramente na memória é chamada de classificação externa.

Métodos de Classificação Interna

• Classificação por Inserção
• Classificação por Troca
• Classificação por Seleção
• Classificação por Intercalação
• Classificação por Distribuição

Classificação por Inserção

A principal característica desses métodos é que eles executam a ordenação pela inserção de cada uma das chaves em sua posição correta na tabela.

Inserção Direta

É o mais simples dos métodos de classificação por inserção. O seu uso somente se justifica quando se trata de pequenos conjuntos de dados, em razão de seu baixo desempenho.

Algoritmo Inserção Direta

proc inserção_direta(inteiro c[N])

inicio

   inteiro i, j, k, ch

   para i de 2 até N faça

      inicio

         k = 1

         j = i-1

        ch = c[i]

         enquanto (j≥1) e (k=1) faça

            se ch < c[ j] então

               inicio

                  c[j+1] = c[j]

                  j = j -1

               fim

            senão

               k = j+1

         c[k] = ch

      fim

fim

Classificação por Troca

Estes métodos se caracterizam por realizarem a classificação por comparação sucessiva de pares de elementos, trocando-os de posição caso estejam fora da ordem de classificação.

Método da Bolha (Bubble Sort)

É dos mais simples dos métodos de classificação por troca. A cada passo, cada chave é comparada com seu sucessor, havendo a troca de posição entre as duas caso estejam fora de ordem de ordenação. São executados passos sucessivos até que não ocorram mais trocas, neste caso, os elementos estarão ordenados.

Algoritmo Bolha

proc bolha(inteiro c[N])

inicio

   inteiro i, k, m, ch

   lógico troca

   troca = v

   m = N-1

   enquanto troca = v faça

      inicio

         troca = f

         para i de 1 até  m faça[pic 1]

            se c[i] > c[i+1] então

               inicio

                  ch = c[i]

                  c[i] = c[i+1]

                  c[i+1] = ch

                  k = i

                  troca = v

              fim

         m = k

      fim

fim      

 Método de Partição e Troca (Quicksort)    

É o método que oferece melhor desempenho, pois comparado com os outros, é o que apresenta um menor número de operações de iteração. Por isto foi denominado de Quicksort ou Ordenação Rápida.

Vetor inicial

           1                                                                                                          N                        

Vetor particionado (3 segmentos)

  1                                         k -1  k    k+1                                              N

S2 comprimento 1 e conterá a chave particionadora.

S1 comprimento  0 conterá todas as chaves   a chave particionadora.

S3 comprimento   0 conterá todas as chaves   que a chave particionadora.

Exemplo:

9 25 10 18 5 7 15 3     CP = 9

i                             f  

_ 25 10 18 5 7 15 3    (esq)

i                             f  

3 25 10 18 5 7 15 _    (dir)

    i                        f  

3 _ 10 18 5 7 15 25    (esq)

    i                        f  

3 _ 10 18 5 7 15 25    (esq)

    i                   f  

3 _ 10 18 5 7 15 25    (esq)

    i              f  

3 7 10 18 5 _ 15 25    (dir)

        i           f  

3 7  _ 18 5 10 15 25  (esq)

        i       f  

3 7  5 18 _ 10 15 25  (dir)

            i   f  

3 7  5  _ 18 10 15 25  (esq)

          i=f  

   S1  S2         S3

3 7  5 9 18 10 15 25  

         i=f  

Algoritmos

proc quick(inteiro c [N], inteiro i, f)

inicio

   se f > i então

      inicio

         partição(c, i, f, k) {posição da chave particionadora}

...