Exercicio-ordenacao1

Prévia do material em texto

File: Unsaved Document 1 Page 1 of 1
Ilustre como fica a ordenação do arranjo A = {3, 8, 1, 9, 2, 4, 10, 6, 5, 7} para cada um dos algoritmos 
abaixo. Após isso, faça a análise assintótica de cada um deles fornecendo sua classe assintótica.
a)
INSERTIONSORT(A, n)
 for i ← 1 to n do
 j ← i;
 while j > 0 and A[j-1] > A[j]
 swap A[j] and A[j-1];
 j ← j - 1;
 end while
 end for
b)
MERGE-SORT(A, p, r)
 if p < r then
 q ← (p+r)/2; // inteiro
 MERGE-SORT(A,p,q);
 MERGE-SORT(A,q+1,r);
 MERGE(A,p,q,r);
 end if
MERGE(A, p, q, r )
 n1 ← q − p + 1
 n2 ← r − q
 Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
 for i ← 1 to n1 do
 L[i] ← A[p + i − 1]
 end for
 for j ← 1 to n2 do
 R[j] ← A[q + j ]
 end for
 L[n1 + 1] ← ∞
 R[n2 + 1] ← ∞
 i ← 1
 j ← 1
 for k ← p to r do
 if L[i] ≤ R[j]
 A[k] ← L[i]
 i ← i + 1
 else
 A[k] ← R[j]
 j ← j + 1
 end if
 end for
c)
BUBBLESORT(A)
 n ← length(A)
 for i ← n to 2 do
 for j ← 0 to j < i do
 if A[i-1] > A[i] then
 swap( A[i-1], A[i] )
 end if
 end for
 end for