Slides sobre Ordenação e Pesquisa em Memória Primária e Secundária

Start presentation

1 - Pesquisa e ordenação em memória primária e secundária

• Autor: Marcelo Akira Inuzuka
• http://akira.sistemasabertos.com.br
• Créditos nas referências, veja último slide.
• Licença: Creative Commons - BY-SA - disponível em http://creativecommons.org/licenses/by-sa/2.5/br/deed.pt

2 - Mapa Conceitual: Ordenação

3 - O que é Ordenação

• É um processo de rearranjo de um conjunto de objetos em ordem ascendente ou descendente;
• Tem como objetivo facilitar a pesquisa de informações;
• Cada objeto é representado por um registro;
• Leva em conta uma (informação) chave que faz parte do registro;

4 - Chave de registro

• Uma chave de registro é uma informação;
• A informação pode ser:
  • numérica
  • alfabética
  • simbólica
  • propriedade (cor)
• A informação pode seguir uma regra de comparação
  • que estabelece uma ordem entre chaves duas a duas;
• Exemplos:
  • 1 < 5 < 7 < 90
  • a < b < c < d... < z < A < B < C < ... < Z
  • paus < ouros < copas < espadas
  • verde < amarelo < vermelho

5 - Métodos de ordenação

• Baseado no tipo de memória utilizada:
  • Método de ordenação externa
  • Método de ordenação interna
• Baseado em comparação ou não
  • Método baseado em comparação
  • Método baseado em distribuição
• Baseado na quantidade de elementos ordenados
  • Método de ordenação parcial
  • Método de ordenação clássica

6 - Método de Ordenação Externa/Interna

• Método de Ordenação Externa
  • utiliza intensivamente a memória principal;
  • carrega os registros em memória volátil (Ex. RAM);
  • geralmente a memória principal (Ex. RAM) tem desempenho melhor;
• Método de Ordenação Interna
  • utiliza intensivamente a memória secundária;
  • geralmente a memória secundária é mais abundante;

7 - Método baseado em distribuição/comparação

• Método baseado em comparação
  • É o método mais comum;
  • Baseia-se na comparação de chaves;
  • Exemplo: ordenação de cartas de baralho (Insertion sort)
• Método baseado em distribuição
  • É o método menos comum;
  • Baseia-se na distribuição dos registros;
  • Exemplo:
    • distribuir cartas em 13 montes na ordem: A < 2 < 3 < ... < J < Q < K;
    • distribuir e retornar cada monte em ordem: paus, ouros, copas e espadas;
    • recolher em uma pilha única na ordem: A < 2 < 3 < ... < J < Q < K;

8 - Método de Ordenação Parcial/Clássico

• Método de ordenação clássico
  • É o método mais comum (clássico);
  • Todos (k) elementos de um arranjo de (n) elementos serão retornados ordenados (k=n);
  • Exemplo: ordenação de todos elementos de um vetor de números;
• Método de ordenação parcial
  • É o método menos comum;
  • Somente alguns (k) elementos de um arranjo de (n) elementos serão retornados ordenados (k<n);
  • Exemplo: retorno dos 20 links melhor classificados de uma busca de páginas da Internet (milhares de páginas);

9 - Mapa conceitual: Métodos de ordenação interna

10 - Métodos de ordenação interna

• Geralmente cria um sub-arranjo ordenado que vai se acumulando iterativamente;
  • Selection Sort
  • Insertion Sort
• Pode utilizar uma abordagem dividir-e-conquistar:
  • Dividir-e-conquistar: dividir o arranjo em sub-arranjos recursivamente, ordenar cada um e combiná-los;
  • Exemplos:
    • Quick sort
    • Merge sort

11 - Selection sort

• Baseia-se em criar interativamente um sub-arranjo ordenado:
  1. Seleção do i-ésimo menor elemento;
  2. Troca de posição do elemento menor com o i-ésimo posição;
• Exemplo:

• Implementação em linguagem C:

void selection_sort(int num[], int tam) { 
        int i, j, min;
        for (i = 0; i < (tam-1); i++) {
                min = i;
                for (j = (i+1); j < tam; j++) {
                        if(num[j] < num[min]) {
                                min = j;
                        }
                }
                if (i != min) {
                        int swap = num[i];
                        num[i] = num[min];
                        num[min] = swap;
                }
        }
}

• Análise:
  • Comparações: C(n) = (n^2)/2 - n/2
  • Movimentações: M(n) = 3 (n - 1)
• Complexidade geral: O(n^2)

12 - Insertion Sort

• Método popularmente utilizado para ordenar "cartas de baralho"
• Baseia-se em:
  1. A partir de i=2;
  2. Inserir o i-ésimo elemento na posição apropriada no sub-arranjo ordenado;

13 - Exemplo de Insertion Sort

14 - Implementação de Insertion Sort em linguagem C:

void insertionSort(int vec[], int vecSize) {
        int i, j;
        int key;
        
        for (j = 1; j < vecSize; ++j) {
                key = vec[j];
                i = j - 1;
                while (vec[i] > key && i >= 0) {
                        vec[i+1] = vec[i];
                        --i;
                }
                
                vec[i+1] = key;
        }
}

15 - Análise do Insertion Sort

• Comparações:
  • melhor caso: C(n) = (1 + 1 + ... + 1) = n-1
  • pior caso: C(n) = ( 2 + 3 + ... + n) = (n^2)/2 + n/2 - 1
  • caso médio: C(n) = (3 + 4 + ... + n + 1)/2 = (n^2)/4 + 3n/4 - 1
• Movimentações:
  • melhor caso: M(n) = (3 + 3 + ... + 3) = 3(n-1)
  • pior caso: M(n) = ( 4 + 5 + ... + n + 2) = (n^2)/2 + 5n/2 - 3
  • caso médio: M(n) = (5 + 6 + ... + n + 3)/2 = (n^2)/4 + 11n/4 - 3
• Complexidade geral: O(n^2)

16 - Quicksort

• Mais rápido para uma ampla variedade de situações;
• Criado por Hoare (1960), em visita a Universidade de Moscou como estudante;
• Publicado em 1962, após vários refinamentos;
• Utiliza uma abordagem dividir-e-conquistar (recursivo);
• Possui complexidade Ω( n lg(n) ), considerada ótima para algoritmos baseados em comparação (vide Cormen (2002), Teorema 8.1, p. 134);

17 - Explicação geral do Quicksort

• 1. Faz uso de um item arbitrário chamado pivô;
• 2. Em uma iteração:
  • 2.1. o pivô é utilizado para comparações e trocas entre elementos à esquerda e à direita do mesmo;
• 3. No final de uma iteração:
  • 3.1. São formados dois sub-arranjos: um à esquerda, com elementos menores que o pivô; e outro à direita, com elementos maiores que o pivô;
• 4. Aplica-se recursivamente o mesmo procedimento a partir de 1, no sub-arranjo à esquerda e no sub-arranjo à direita;

18 - Algoritmo do Quicksort

1. Escolha de um pivô arbitrário e armazená-lo em x;
2. Percorrer o vetor a partir da esquerda até que um item A[i] >= x é encontrado; da mesma forma: percorrer o vetor a partir da direita até que um item A[j] <= x é encontrado;
3. Troca os elementos A[i] e A[j];
4. Continuar o processo, a partir do passo 2, até que i e j se cruzem;

19 - Exemplo do Quicksort - 1/2

20 - Exemplo do Quicksort - 2/2

Fonte: Shahbazkia, Hamid - disponível em http://w3.ualg.pt/~hshah/ped/Aula%2014/Quick_final.html

21 - Implementações do Quicksort

void quick_S (int v[], int p, int r) {
        int c, i, j, t;
        if (p < r) {      
                c = v[(p+r)/2];
                i = p, j = r;
                while (i <= j) {
                        while (v[i] < c) ++i;
                        while (c < v[j]) --j;
                        if (i <= j) {
                                t = v[i], v[i] = v[j], v[j] = t;
                                ++i, --j;
                        }
                }
                quick_S (v, p, j);
                quick_S (v, i, r);
        }
}

22 - Análise do Quicksort

• Pior caso: O(n^2) - quando o vetor está totalmente ordenado e o pivô escolhido está em um dos extremos;
  • Sugestão de Ziviani (2005): escolha de 3 elementos aleatórios, usar a mediana dos três como pivô;
• Caso médio:
  • C(n) = n lg(n) - n + 1
  • ou seja, a complexidade de operações do Quicksort segue O(n lg n).

23 - Heap sort

• Utiliza a estrutura de dados Heap;
• Heap é uma arvore binária praticamente completa - Cormen(2002, p.103);
• Pode ser implementado por meio de um arranjo (A);
• Possui as seguintes propriedades:
  • PARENT( i ) = i / 2 (divisão de inteiros, piso da divisão;
  • LEFT( i ) = 2 * i
  • RIGHT( i ) = 2 * i + 1
• Há dois tipos de heaps:
  • Heap máximo: A[ PARENT( i ) ] >= A[ i ]
  • Heap mínimo: A[ PARENT( i ) ] <= A[ i ]
• Para o Heap máximo, o nó pai sempre é maior que os nós filhos;
  • Exemplo de heap máximo representado em um vetor:

24 - Heap Sort: algoritmo

• Se baseia na função BUILD_HEAP, que se baseia na função MAX-HEAPIFY (ou HEAPIFY)
• MAX-HEAPIFY(A, i) faz com que todos a subárvore de raiz de índice i respeite as propriedades de Heap:

• Exemplo:
• Algoritmo BUILD-HEAP:
• Exemplo:

25 - Heapsort: implementação

#include<stdio.h>
#include<conio.h>
#include<math.h>


void swap(int *p, int *q);
void HEAPSORT(int heap[100], int n);
int BUILD_HEAP(int heap[100],int n);
void HEAPIFY(int heap[100], int i, int heap_size);

int PARENT(int i);
int LEFT(int i);
int RIGHT(int i);

//int heap_size;

void main()
{
        int i,j,n;
        int heap[110];
        
        while(1)
        {
                printf("Enter the number of element (0 to exit): ");
                scanf("%d",&n);
                if(n==0)
                break;
                for(i=1;i<=n;++i)
                scanf("%d",&heap[i]);
                HEAPSORT(heap,n);
                printf("The sorted List is:\n");
                for(i=1;i<=n;++i)
                printf("%d ",heap[i]);
        }
}

void HEAPSORT(int heap[100], int n)
{
        int i,heap_size;
        heap_size = BUILD_HEAP(heap,n);
        for(i=n;i>=2;--i)
        {
                swap(&heap[1],&heap[i]);
                --heap_size;
                HEAPIFY(heap,1,heap_size);
        }
        
}

void swap(int *p, int *q)
{
        int t;
        t=*p;
        *p=*q;
        *q=t;
}

int BUILD_HEAP(int heap[100],int n)
{
        int i, heap_size;
        heap_size = n;
        for(i=floor(n/2);i>=1;--i)
        HEAPIFY(heap,i,heap_size);
        return heap_size;
}

void HEAPIFY(int heap[100], int i, int heap_size)
{
        int l,r,largest;
        l = LEFT(i);
        r = RIGHT(i);
        
        if(l <= heap_size && heap[l] > heap[i])
        largest = l;
        else
        largest = i;
        if(r <= heap_size && heap[r] > heap[largest])
        largest = r;
        if(largest != i)
        {
                swap(&heap[i],&heap[largest]);
                HEAPIFY(heap,largest,heap_size);
        }
        
}

int PARENT(int i)
{return (i/2);}
int LEFT(int i)
{return (2*i);}
int RIGHT(int i)
{return ((2*i)+1);}

Fonte: http://www.algorithm-code.com/wiki/Heapsort

26 - Exercício

• Crie aleatoriamente um vetor de números inteiros de 10 elementos;
• Aplique e mostre a execução passo-a-passo dos algoritmos no mesmo:
  • 1 - Selection sort ou Insertion sort;
  • 2 - Quicksort ou Heapsort;
• Peça para que algum colega faça a revisão da sua resposta;

27 - Referências:

• ZIVIANI, Nívio. Projeto de Algoritmos, com implementações em Pascal e C. 2a Ed. 2005.
• CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Algoritmos - Teoria e Prática. 2002