algoritmose,eficientes

Prévia do material em texto

Algoritmos E�cientes de Ordenaçªo
Quick Sort
Merge Sort
Heap Sort
Utilizar informaçªo das chaves:
Counting Sort
Radix Sort
AED 2002/2003 – p.1/22
Quick Sort
int partition(Item a[], int l, int r)
{ int i = l-1, j = r; Item v = a[r];
for (;;)
{
while (less(a[++i], v)) ;
while (less(v, a[--j])) if (j == l) break;
if (i >= j) break;
exch(a[i], a[j]);
}
exch(a[i], a[r]);
return i;
}
void quicksort(Item a[], int l, int r)
{ int i;
if (r <= l) return;
i = partition(a, l, r);
quicksort(a, l, i-1);
quicksort(a, i+1, r);
}
AED 2002/2003 – p.2/22
Quick Sort – Complexidade
Complexidade depende das chaves
Para array jÆ ordenado, tempo de execuçªo Ø � � � ���
Normalmente, para qualquer partiçªo razoÆvel do
vector a cada passo do algoritmo, complexidade Ø
�
�
�
��
�
	
�
�
Nªo Ø estÆvel
AED 2002/2003 – p.3/22
Merge Sort
Item aux[maxN];
merge(Item a[], int l, int m, int r)
{ int i, j, k;
for (i = m+1; i > l; i--) aux[i-1] = a[i-1];
for (j = m; j < r; j++) aux[r+m-j] = a[j+1];
for (k = l; k <= r; k++)
if (less(aux[i], aux[j]))
a[k] = aux[i++]; else a[k] = aux[j--];
}
void mergesort(Item a[], int l, int r)
{ int m = (r+l)/2;
if (r <= l) return;
mergesort(a, l, m);
mergesort(a, m+1, r);
merge(a, l, m, r);
}
AED 2002/2003 – p.4/22
Merge Sort – Complexidade
Tempo de execuçªo:
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� 	
�
�
FÆcil de veri�car quando � Ø potŒncia de 2, e no caso
geral recorrendo a induçªo
Complexidade pior caso Ø � � � �� 	 ��
É estÆvel
AED 2002/2003 – p.5/22
Merge Sort – Bottom-Up
#define min(A, B) (A < B) ? A : B
void mergesortBU(Item a[], int l, int r)
{ int i, m;
for (m = 1; m < r-l; m = m+m)
for (i = l; i <= r-m; i += m+m)
merge(a, i, i+m-1, min(i+m+m-1, r));
}
AED 2002/2003 – p.6/22
Merge Sort com Listas
link merge(link a, link b)
{ struct node head; link c = &head;
while ((a != NULL) && (b != NULL))
if (less(a->item, b->item))
{ c->next = a; c = a; a = a->next; }
else
{ c->next = b; c = b; b = b->next; }
c->next = (a == NULL) ? b : a;
return head.next;
}
link mergesort(link c)
{ link a, b;
if (c->next == NULL) return c;
a = c; b = c->next;
while ((b != NULL) && (b->next != NULL))
{ c = c->next; b = b->next->next; }
b = c->next; c->next = NULL;
return merge(mergesort(a), mergesort(b));
}
AED 2002/2003 – p.7/22
Heap Sort
#define pq(A) a[l-1+A]
void heapsort(Item a[], int l, int r)
{ int k, N = r-l+1;
for (k = N/2; k >= 1; k--)
fixDown(&pq(0), k, N);
while (N > 1)
{ exch(pq(1), pq(N));
fixDown(&pq(0), 1, --N); }
}
AED 2002/2003 – p.8/22
Heap Sort – Complexidade
Construçªo do amontoado (ciclo for):
�
�
�
��
�
	
�
�
no pior caso
É possível assegurar � � ��
Colocaçªo das chaves (ciclo while):
�
�
�
��
�
	
�
�
no pior caso
Complexidade pior caso Ø � � � �� 	 ��
Nªo Ø estÆvel
AED 2002/2003 – p.9/22
Avaliaçªo Experimental
N Quick Merge Heap
12500 2 5 3
25000 7 11 8
50000 13 24 18
100000 27 52 42
200000 58 111 100
400000 122 238 232
800000 261 520 542
AED 2002/2003 – p.10/22
Ordenaçªo por Comparaçªo
Algoritmos de ordenaçªo baseados em comparaçıes
sªo
�
��
�
��
�
	
�
�
Para � chaves existem � � ordenaçıes possíveis das
chaves
Algoritmo de ordenaçªo por comparaçªo utiliza
comparaçıes de pares de chaves para seleccionar
uma das � � ordenaçıes
Escolher uma folha em Ærvore com � � folhas
Altura da Ærvore Ø nªo inferior ��� 	 � � � � � � � � �� 	 � �
É possível obter algoritmos mais e�cientes desde que
nªo sejam baseados em comparaçıes:
Utilizar informaçªo quanto às chaves utilizadas
Counting Sort
Radix Sort
AED 2002/2003 – p.11/22
Counting Sort – Motivaçªo
Ordenar � � ��� ff � fi
Chaves podem tomar valor entre 0 e � fi
Se existem fl�ffi chaves com valor 0, entªo ocupam as
primeiras fl ffi posiçıes do array �nal, 0 a fl ffi � fi
Se existem fl ! chaves com valor 1, entªo ocupam as
posiçıes flffi a flffi � fl! � fi posiçıes do array �nal
...
NecessÆrio vectores auxiliares para guardar contagens
e para construir array ordenado
AED 2002/2003 – p.12/22
Counting Sort I
void distcount(int a[], int l, int r)
{ int i, j, cnt[M+1];
int b[maxN];
for (j = 0; j <= M; j++) cnt[j] = 0;
for (i = l; i <= r; i++) cnt[a[i]+1]++;
for (j = 1; j < M; j++) cnt[j] += cnt[j-1];
for (i = l; i <= r; i++) b[cnt[a[i]]++] = a[i];
for (i = l; i <= r; i++) a[i] = b[i];
}
AED 2002/2003 – p.13/22
Counting Sort – Complexidade
Dois ciclos relativos à dimensªo das chaves
TrŒs ciclos relativos às � chaves
Complexidade: � � � � �
AED 2002/2003 – p.14/22
Counting Sort II
void distcount(int a[], int l, int r)
{ int i, j, cnt[M];
int b[maxN];
for (j = 0; j < M; j++) cnt[j] = 0;
for (i = l; i <= r; i++) cnt[a[i]]++;
for (j = 1; j < M; j++) cnt[j] += cnt[j-1];
for (i = r; i >= l; i--) b[--cnt[a[i]]] = a[i];
for (i = l; i <= r; i++) a[i] = b[i];
}
Diferenças??
De�niçªo do valor cnt[j]
Estabilidade do algoritmo ??
AED 2002/2003 – p.15/22
Radix Sort – De�niçıes
#define bitsword 32
#define bitsbyte 8
#define bytesword 4
#define R (1 << bitsbyte)
#define digit(A, B) (((A) >> (bitsword-((B)+1)*bitsbyte)) & (R-1))
AED 2002/2003 – p.16/22
Radix Sort I
#define bin(A) l+count[A]
void radixMSD(Item a[], int l, int r, int w)
{ int i, j, count[R+1];
if (w > bytesword) return;
if (r-l <= M) { insertion(a, l, r); return; }
for (j = 0; j < R; j++) count[j] = 0;
for (i = l; i <= r; i++)
count[digit(a[i], w) + 1]++;
for (j = 1; j < R; j++)
count[j] += count[j-1];
for (i = l; i <= r; i++)
aux[l+count[digit(a[i], w)]++] = a[i];
for (i = l; i <= r; i++) a[i] = aux[i];
radixMSD(a, l, bin(0)-1, w+1);
for (j = 0; j < R-1; j++)
radixMSD(a, bin(j), bin(j+1)-1, w+1);
}
AED 2002/2003 – p.17/22
Radix Sort I – Operaçªo
Utilizar dígitos, do maior peso para o menor peso:
Colocar chaves em caixas
Ordenar elementos de cada caixa utilizando dígitos
subsequentes
Se nœmero de elementos nªo superior a , utilizar
insertion sort
AED 2002/2003 – p.18/22
Radix Sort II
void radixLSD(Item a[], int l, int r)
{
int i, j, w, count[R+1];
for (w = bytesword-1; w >= 0; w--)
{
for (j = 0; j < R; j++) count[j] = 0;
for (i = l; i <= r; i++)
count[digit(a[i], w) + 1]++;
for (j = 1; j < R; j++)
count[j] += count[j-1];
for (i = l; i <= r; i++)
aux[count[digit(a[i], w)]++] = a[i];
for (i = l; i <= r; i++) a[i] = aux[i];
}
}
AED 2002/2003 – p.19/22
Radix Sort II – Operaçªo
Utilizar dígitos, do menor peso para o maior peso:
Ordenar todo o vector utilizando counting sort
utilizando cada dígito
AED 2002/2003 – p.20/22
E�ciŒncia dos Radix Sorts
Radix Sort I
Tempo de execuçªo cresce com nœmero de bytes
dos elementos a ordenar
Radix Sort II
�
�
�#
"
$
%
��
�
	
&
�
, para chaves com $ bits
Espaço adicional: & contadores
AED 2002/2003 – p.21/22
Avaliaçªo Experimental
N Quick MSD LSD
12500 2 28 4
25000 5 29 8
50000 10 35 18
100000 21 47 39
200000 49 72 81
400000 102 581 169
800000 223 6064 328
AED 2002/2003 – p.22/22
	Algoritmos Eficientes de Ordenação
	Quick Sort
	Quick Sort -- Complexidade
	Merge Sort
	Merge Sort -- Complexidade
	Merge Sort -- Bottom-Up
	Merge Sort com Listas
	Heap Sort
	Heap Sort -- Complexidade
	Avaliação Experimental
	Ordenação por Comparação
	Counting Sort -- Motivação
	Counting Sort I
	Counting Sort -- Complexidade
	Counting Sort II
	Radix Sort -- Definições
	Radix Sort I
	Radix Sort I -- Operação
	Radix Sort II
	Radix Sort II -- Operação
	Eficiência dos Radix Sorts
	AvaliaçãoExperimental