Organização de Arquivos - Conceitos Básicos sobre Estrutura de Arquivos (Parte 3)

Prévia do material em texto

Introduc¸a˜o a` Organizac¸a˜o de Arquivos: Me´todos de Ordenac¸a˜o
Departamento de Cieˆncia da Computac¸a˜o
Instituto de Cieˆncias Exatas
Universidade de Bras´ılia
1 / 43
Suma´rio
Conceitos Ba´sicos sobre Estrutura de Arquivos
1 Bubblesort
2 Selection Sort
3 Insertion Sort
4 Shellsort
5 Quicksort
6 Mergesort
7 Heapsort
2 / 43
Bubblesort
Este me´todo consiste em ler
todo o vetor, comparando os
elementos vizinhos entre si.
Caso estejam fora da ordem
(determinada pela classificac¸a˜o
em questa˜o), os mesmos
trocam de posic¸a˜o entre si.
3 / 43
Bubblesort
O vetor esta´ agora mais
pro´ximo de uma ordenac¸a˜o,
mas ainda na˜o da ordenac¸a˜o
desejada.
Isso indica que devemos repetir
o processo mais vezes ate´ que
o vetor esteja ordenado.
Executando mais uma vez o
trecho de algoritmo. . .
4 / 43
Bubblesort
1 vo id b o l h a ( i n t ∗ v , i n t n ){
2 i n t i , j , temp ;
3 /∗ P io r caso : r e p e t i r n−1 vezes , de n−1 a 1 ∗/
4 f o r ( i=n−1; i >0; i−−){
5 f o r ( j =0; j<i ; j ++){
6 i f ( v [ j ]>v [ j +1]) { /∗ t r o c a ∗/
7 temp = v [ j ] ;
8 v [ j ] = v [ j +1] ;
9 v [ j +1] = temp ;
10 }
11 }
12 }
13 }
Co´digo 1: Implementac¸a˜o em C
5 / 43
Bubblesort
O nu´mero ma´ximo de execuc¸o˜es do trecho do algoritmo para que o vetor fique
ordenado e´ N − 1 vezes, onde N e´ o nu´mero de elementos do vetor.
E´ sempre necessa´rio repetir N − 1 vezes?
No exemplo apresentado em apenas duas execuc¸o˜es do algoritmo o vetor ja´ estava
ordenado!
No exemplo apresentado em apenas duas execuc¸o˜es do algoritmo o vetor ja´ estava
ordenado!
Como controlar o nu´mero de vezes?
Se o vetor ja´ estiver ordenado, na˜o precisa repetir o passo mais uma vez.
Se na˜o houve trocas entre os elementos do vetor ao executar o trecho do algoritmo,
enta˜o ele esta´ ordenado.
6 / 43
Bubblesort
1 vo id b o l h a 2 ( i n t ∗ v , i n t n ){
2
3 i n t i , j , temp , t r o c a = 1 ;
4 i = n−1;
5 wh i l e ( t r o c a && i > 0){
6 t r o c a = 0 ;
7 f o r ( j =0; j<i ; j ++){
8 i f ( v [ j ]>v [ j +1]){ /∗ t r o c a ∗/
9 temp = v [ j ] ;
10 v [ j ] = v [ j +1] ;
11 v [ j +1] = temp ;
12 t r o c a = 1 ;
13 }
14 }
15 i = i −1;
16 }
17 }
Co´digo 2: Implementac¸a˜o em C
7 / 43
Bubblesort
1 vo id b o l h a r e c ( i n t ∗ v , i n t n ){
2 i n t j , temp , t r o c a = 0 ;
3
4 f o r ( j =0; j<n−1; j ++)
5 i f ( v [ j ]>v [ j +1]) { /∗ t r o c a ∗/
6 temp = v [ j ] ;
7 v [ j ] = v [ j +1] ;
8 v [ j +1] = temp ;
9 t r o c a = 1 ;
10 }
11 }
12 i f ( t r o c a != 0){ /∗ houve t r o c a ∗/
13 b o l h a r e c ( v , n−1);
14 }
15 }
Co´digo 3: Implementac¸a˜o Recursiva
em C
8 / 43
Bubblesort
Pior Caso
Eficieˆncia do Bubblesort (pior caso):
T (n) =
n−1∑
i=1
i =
n(n− 1)
2
=
n2
2
− n
2
= O(n2)
9 / 43
Bubblesort
10 / 43
Bubblesort
10 / 43
Bubblesort
Caso Me´dio
A eficieˆncia do Bubblesort no caso me´dio e´ dada por:
T (n) =
(n− 1)(n− 1) + (n− 2)(n− 2) + . . . + 2 · 2 + 1 Total de comprac¸o˜es
n− 1 Total de eventos poss´ıveis
Ou seja:
T (n) =
1
n− 1
n−1∑
i=1
i2 =
n
6
(2n− 1) = n
2
3
− n
6
= O(n2)
11 / 43
SelectionSort
SelectionSort
Identificamos o menor (ou maior) elemento no segmento do vetor que conte´m os
elementos ainda na˜o selecionados.
Trocamos o elemento identificado com o primeiro elemento do segmento.
Atualizamos o tamanho do segmento (diminu´ımos uma posic¸a˜o).
Interrompemos o processo quando o segmento contiver apenas um elemento.
Eficieˆncia:
Pior caso O(n2).
Caso me´dio O(n2).
Na pra´tica, para n na˜o muito grande, o Selection sort normalmente e´ melhor que o
Bubblesort (fazer a deduc¸a˜o do caso me´dio), pore´m e´ normalmente pior que o
Insertion sort.
12 / 43
SelectionSort
13 / 43
SelectionSort
Algoritmo 1 SelectionSort em pseudo-co´digo
for k ← 0 to N − 2 do
posMenor ← k
for i← k + 1 to N − 1 do {Percorre todo o vetor}
if numero[i] < numero[posMenor] then
posMenor ← i
end if
end for
if posMenor 6= k then
aux← numero[posMenor]
numero[posMenor]← numero[k]
numero[k]← aux
end if
end for
14 / 43
Insertion Sort
A ordenac¸a˜o por inserc¸a˜o funciona da maneira parecida como muitas pessoas
ordenam as cartas em um jogo
15 / 43
Insertion Sort
Insertion Sort
Iniciaremos com a ma˜o esquerda vazia e as cartas viradas com a face para baixo na
mesa.
Em seguida, removeremos uma carta de cada vez da mesa.
Vamos compara´-la a cada uma das cartas que ja´ esta˜o na ma˜o, da direita para a
esquerda, inserindo-a na posic¸a˜o correta na ma˜o esquerda.
Ou seja, percorremos um vetor da esquerda para a direita e a` medida que
avanc¸amos, deixamos os elementos mais a` esquerda ordenados.
Eficieˆncia:
Pior caso: O(n2).
Caso me´dio: O(n2).
16 / 43
Insertion Sort
Figura: Passo a passo do Insertion Sort
17 / 43
Shell Sort
Shell Sort
Generalizac¸a˜o do Insertion Sort
Divide-se o vetor original em subvetores que conteˆm todo h-e´simo elemento do vetor
original.
Exemplo para h = 5:
Subvetor 1: V[0], V[5], V[10], ...
Subvetor 2: V[1], V[6], V[11], ...
Subvetor 3: V[2], V[7], V[12], ...
Subvetor 4: V[3], V[8], V[13], ...
Subvetor 5: V[4], V[9], V[14], ...
Dado um incremento h, o i-e´simo elemento do j-e´simo subvetor, e´ dado por:
V [(i− 1) · h + j − 1]
Por exemplo: Exemplo: i = 3, j = 3, V [(3− 1) ∗ 5 + 3− 1] = V [12] .
18 / 43
Shell Sort 1
Os subvetores sa˜o classificados utilizando-se o InsertionSort.
O processo e´ repetido para um valor de h menor, ate´ que h = 1.
Definic¸a˜o dos valores de h, proposta por T. N. Hibbard, demonstrada por A. A.
Papernov e G. V. Stasevic em 1965:
hs = 2
s − 1, 1 ≤ s ≤ t = blog2 nc
Eficieˆncia de pior caso de O(n3/2) = O(n
√
n)
19 / 43
Shell Sort 2
Os subvetores sa˜o classificados utilizando-se o InsertionSort.
O processo e´ repetido para um valor de h menor, ate´ h− 1.
Definic¸a˜o dos valores de h, proposta de Vaughan Pratt em 1969 :
hs = 2p3q < n
Eficieˆncia no pior caso: O(n log22 n)
20 / 43
Shell Sort 3
Shell Sort: generalizac¸a˜o do InsertionSort.
Os subvetores sa˜o classificados utilizando-se o InsertionSort.
O processo e´ repetido para um valor de h menor, ate´ O processo e´ repetido para um
valor de h menor, ate´ h = 1.
Definic¸a˜o dos valores de h, proposta Robert Sedgewick em 1982:
hs = 1, . . . , 4
j+1 + 3 · 2j + 1 < n
Eficieˆncia de pior caso de O(n
4
3 ).
21 / 43
Shell Sort 4
Os subvetores sa˜o classificados utilizando-se o InsertionSort.
O processo e´ repetido para um valor de h menor, ate´ h = 1.
Definic¸a˜o dos valores de h. Experimentalmente definidos por Peterson and David
L. Russel em 1971:{
h1 = 1
hs+1 = 3hs + 1, parar com ht, quando ht+2 ≥ N
Eficieˆncia de 1.66 · n1.25, 100 ≤ n ≤ 60000.
22 / 43
Shell Sort 4
Exemplo: h = {4, 3, 1}
Para h = 4.
A comparac¸a˜o entre 25 e 12 e´ realizada. Os elementos sa˜o trocados.
23 / 43
Shell Sort 4
Exemplo: h = {4, 3, 1}
Para h = 4.
A comparac¸a˜o entre 25 e 12 e´ realizada. Os elementos sa˜o trocados.
23 / 43
Shell Sort 4
Exemplo: h = {4, 3, 1}
Para h = 4.
A comparac¸a˜o entre 57 e 92 e´ realizada. Os elementos na˜o sa˜o trocados.
23 / 43
Shell Sort 4
Exemplo: h = {4, 3, 1}
Para h = 4.
A comparac¸a˜o entre 48 e 86 e´ realizada. Os elementos na˜o sa˜o trocados.
23 / 43
Shell Sort 4
Exemplo: h = {4, 3, 1}
Para h = 4.
A comparac¸a˜o entre 33 e 37 e´ realizada. Os elementos sa˜o trocados.
23 / 43
Shell Sort 4
Exemplo: h = {4, 3, 1}
Para h = 4.
A comparac¸a˜o entre 33 e 37 e´ realizada. Os elementos na˜o sa˜o trocados.
23 / 43
Shell Sort 4
Exemplo: h = {4, 3, 1}
Parah = 3.
InsertionSort no subvetor [12, 33, 86]. Na˜o sa˜o realizadas trocas.
23 / 43
Shell Sort 4
Exemplo: h = {4, 3, 1}
Para h = 3.
InsertionSort no subvetor [57, 25, 37]. Sa˜o realizadas duas trocas.
23 / 43
Shell Sort 4
Exemplo: h = {4, 3, 1}
Para h = 3.
InsertionSort no subvetor [25, 37, 57]. Sa˜o realizadas duas trocas.
23 / 43
Shell Sort 4
Exemplo: h = {4, 3, 1}
Para h = 1.
InsertionSort no vetor todo.
23 / 43
Shell Sort 4
Exemplo: h = {4, 3, 1}
Para h = 1.
InsertionSort no vetor todo.
23 / 43
Quicksort
Quicksort
Este me´todo parte do princ´ıpio de que e´ mais ra´pido ordenar dois vetores com n
2
elementos cada um, do que um com n elementos (conceito de dividir para
conquistar).
O primeiro passo e´ dividir o vetor original.
Esse procedimento e´ denominado particionamento.
Deve-se escolher umas das das posic¸o˜es do vetor a qual e´ denominada de pivoˆ:
V [i]
24 / 43
Quicksort
Quicksort
Uma vez escolhido o pivoˆ, os elementos do vetor sa˜o movimentados de forma que:
O subvetor a` esquerda do pivoˆ contenha somente os elementos cujos valores sa˜o
menores que o pivoˆ.
O subvetor da direita contenha valores maiores que o valor do pivoˆ.
V [0], ..., V [i− 1] V [i] V [i + 1], ..., V [n− 1]
O procedimento e´ repetido ate´ que o vetor esteja ordenado.
Existem va´rias formas de se escolher o pivoˆ. Vamos escolher o valor do meio do
(sub)vetor.
25 / 43
Quicksort: Algoritmo
1) Pivoˆ e´ escolhido no meio do vetor. O elemento e´ colocado numa varia´vel auxiliar pivo;
2) Sa˜o iniciadas duas varia´veis auxiliares i = inicio e j = fim;
3) O vetor e´ percorrido do inicio ate´ que se encontre um V [i] ≥ pivo (i e´ incrementado
no processo).
4) O vetor e´ percorrido a partir do fim ate´ que se encontre um V [j] ≤ pivo (j e´
decrementado no processo).
5) V [i] e V [j] sa˜o trocados; i e´ incrementado de 1 e j e´ decrementado de 1.
6) O processo e´ repetido ate´ que i e j se cruzem em algum ponto do vetor (i > j).
7) Quando sa˜o obtidos os dois segmentos do vetor por meio do processo de partic¸a˜o,
realiza-se a ordenac¸a˜o de cada um deles de forma recursiva.
Eficieˆncia no pior caso: O(n2)
Eficieˆncia no caso me´dio: O(n log2 n)
26 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort: Exemplo
27 / 43
Quicksort:Implementac¸a˜o em C
1 vo id q u i c k s o r t ( i n t vec [ ] , i n t i n i c i o , i n t f im ) {
2 i n t p i v o = vec [ ( i n t ) ( i n i c i o+f im )/2 ] ;
3 i n t i = i n i c i o , j = fim , temp ;
4 wh i l e ( i < j ) {
5 wh i l e ( p i v o > vec [ i ] ) i ++;
6 wh i l e ( p i v o < vec [ j ] ) j−−;
7 i f ( i<=j ) {
8 temp = vec [ i ] ;
9 vec [ i ] = vec [ j ] ;
10 vec [ j ] = temp ;
11 i ++;
12 j−−;
13 }
14 }
15 i f ( j > i n i c i o )
16 q u i c k s o r t ( vec , i n i c i o , j ) ;
17 i f ( i < f im )
18 q u i c k s o r t ( vec , i , f im ) ;
19 }
Co´digo 4: Implementac¸a˜o do
Quicksort em C
28 / 43
Mergesort
Mergesort
A ide´ia ba´sica e´ criar uma sequeˆncia ordenada a partir da mescla de duas outras
tambe´m ordenadas.
Usamos um procedimento auxiliar MERGE(V, i, j, k) onde V e´ um vetor e i,j, e k
sa˜o ı´ndices de elementos do vetor, tais que i ≤ j ≤ k.
O procedimento pressupo˜e que os sub-arranjos V [i..j] e V [j + 1..k] esta˜o ordenados.
Eficeˆncia
Pior caso: O(n2).
Caso me´dio: O(n log2 n)
.
29 / 43
Mergesort: Exemplo do Procedimento MERGE
30 / 43
Mergesort: Exemplo do Procedimento MERGE
30 / 43
Mergesort: Exemplo do Procedimento MERGE
30 / 43
Mergesort: Exemplo do Procedimento MERGE
30 / 43
Mergesort: Exemplo do Procedimento MERGE
30 / 43
Mergesort: Exemplo do Procedimento MERGE
30 / 43
Mergesort: Exemplo do Procedimento MERGE
30 / 43
Mergesort: Exemplo do Procedimento MERGE
30 / 43
Mergesort: Implementac¸a˜o
1 vo id MERGESORT( i n t V [ ] , i n t i , i n t k ){
2 i n t j ;
3 i f ( i < k ){
4 j = ( i+k )/2
5 MERGESORT(V, i , j )
6 MERGESORT(V, j + 1 , k )
7 MERGE(V, i , j , k )
8 }
9 }
Co´digo 5: Visa˜o alto n´ıvel do
Mergesort em C
31 / 43
Mergesort
Figura: Visa˜o geral do Mergesort
32 / 43
Heapsort
Heapsort
Constro´i-se uma a´rvore bina´ria quase completa com todos os elementos do vetor.
Transforma-se a a´rvore em uma heap: os pais sa˜o maiores ou iguais a seus filhos.
Ordena-se a heap:
Troca-se o valor da raiz com o valor da posic¸a˜o de maior ı´ndice na a´rvore.
A posic¸a˜o de maior ı´ndice e´ retirada da a´rvore.
Se a propriedade heap na˜o foi mantida, “heapifica-se” a a´rvore novamente e o
processo e´ repetido ate´ restar apenas um u´nico no´.
Eficieˆncia:
Pior caso: O(n log2 n)
Caso me´dio: O(n log2 n)
33 / 43
Heapsort
Heapsort
A func¸a˜o HEAPIFY (V, p): suas entradas sa˜o um vetor V e um ı´ndice p para o
vetor.
Quando e´ chamada, supomos que as a´rvores bina´rias com ra´ızes em left(p) e
right(p) sa˜o heaps, mas que V [p] pode ser menor que seus filhos, violando assim a
propriedade de heap.
A func¸a˜o de HEAPIFY e´ deixar que o valor em V [p] ”flutue para baixo”, de tal
forma que a suba´rvore com raiz no ı´ndice p se torne um heap.
34 / 43
Heapsort: HEAPIFY
1 HEAPIFY( i n t V [ ] , i n t p ){
2 i n t L = l e f t ( p ) ;
3 i n t R = r i g h t ( p ) ;
4 i f ( L != NULL e V [ L ] > V [ p ] ){
5 maior = L ;
6 }
7 e l s e {
8 maior = p ;
9 }
10 i f (R != NULL e V [ R ] > V [ maior ] ){
11 maior = R ;
12 }
13 i f ( maior != p ) {
14 t r o c a (V [ p ] , V [ maior ] )
15 HEAPIPY(V, maior )
16 }
17 }
Co´digo 6: Visa˜o alto n´ıvel da func¸a˜o
HEAPIFY
35 / 43
Heapsort: HEAPIFY
36 / 43
Heapsort: HEAPIFY
36 / 43
Heapsort: HEAPIFY
36 / 43
Heapsort: HEAPIFY
36 / 43
Heapsort: HEAPIFY
36 / 43
Heapsort: BUILD HEAP
A func¸a˜o BUILD HEAP (V ) e´ usada de baixo para cima, afim de converter um
vetor V em um heap.
1 vo id BUILD HEAP (V){
2 f o r ( p = f l o o r ( l e n g t h (V ) / 2 ) ; p>=1; p−−){
3 HEAPIFY(V, p )
4 }
5 }
Co´digo 7: Visa˜o geral do
procedimento BUILD HEAP
37 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort: BUILD HEAP
38 / 43
Heapsort
1 vo id HEAPSORT(V){
2 BUILD HEAP(V ) ;
3 f o r ( p = l e n g t h (V ) ; p>=2; p−−){
4 t r o c a (V [ 1 ] , V [ p ] ) ;
5 tamanho de V = tamanho de V − 1 ;
6 HEAPIFY(V,1 ) ;
7 }
8 }
Co´digo 8: Visa˜o geral do Heapsort
39 / 43
Heapsort: Exemplo
40 / 43
Heapsort: Exemplo
40 / 43
Heapsort: Exemplo
40 / 43
Heapsort: Exemplo
40 / 43
Heapsort: Exemplo
40 / 43
Heapsort: Exemplo
40 / 43
Heapsort: Exemplo
40 / 43
Heapsort: Exemplo
40 / 43
Heapsort: Exemplo
40 / 43
Heapsort: Exemplo
40 / 43
Heapsort: Exemplo
40 / 43
Heapsort: Exemplo
40 / 43
Heapsort: Exemplo
40 / 43
Heapsort: Exemplo
40 / 43
Heapsort: Exemplo
40 / 43
Complexidade dos Algoritmos
Tabela: Complexidade dos algoritmos de ordenac¸a˜o
41 / 43
Complexidade dos Algoritmos
42 / 43
Complexidade dos Algoritmos
42 / 43
Complexidade dos Algoritmos
42 / 43
Complexidade dos Algoritmos
42 / 43
Complexidade dos Algoritmos
42 / 43
Complexidade dos Algoritmos: Shellsort
43 / 43
Complexidade dos Algoritmos: Shellsort
43 / 43
Complexidade dos Algoritmos: Shellsort
43 / 43
Complexidade dos Algoritmos: Shellsort
43 / 43
Complexidade dos Algoritmos: Shellsort
43 / 43
Complexidade dos Algoritmos: Shellsort
43 / 43