ATPS etapas 1 e 2 de Análise e Complexidade de Algoritmos

...

O diferencial desde método é que ele consiste em ordenar o arranjo utilizando um sub-arranjo ordenado localizado em seu início, a cada passo, um novo elemento é acrescentado a esse sub-arranjo até que atinja o último elemento do arranjo, fazendo o vetor no final do processamento estar organizado.

Exemplo:

Vetor: [P, S, E, F, M, B]

1 – [P, S, E, F, M, B]

2 – [E, P, S, F, M, B]

3 – [E, F, P, S, M, B]

4 – [E, F, M, P, S, B]

5 – [B, E, F, M, P, S] – Vetor organizado.

Algoritmo do método Ordenação por Inserção:

voidInsercao(VetorA,intn){

inti,j,x;

for(i=2;i

x=A[i];

j=i–1;

while(x

A[j+1]=A[j];

j--;

}

A[j+1]=x;

}

}

Crie um algoritmo de ordenação por inserção e um de ordenação por seleção para ordenar um vetor de tamanho n. Escreva a complexidade, linha a linha, de cada um dos algoritmos criados e em seguida explique o funcionamento, passo a passo, dos algoritmos criados.

Algoritmo de Inserção (Insertion Sort):

OBS: Linguagem usada – JAVA.

public static void main(String[] args){ ⇒ O(1)

int i, j, num_atual; ⇒ O(1)

int[] num_vet = {5, 3, 10, 1, 6}; ⇒ O(1)

for(i=1; ii++){ ⇒ O(n)

num_atual = num_vet[i]; ⇒ O(1)

j = i-1; ⇒ O(1)

while((j>=0) && (num_atual num_vet[j])){ ⇒ O(n)

num_vet[j+1] = num_vet[j]; ⇒ O(1)

j--; ⇒ O(1)

} ⇒ O(1)

num_vet[j+1] = num_atual; ⇒ O(1)

} ⇒ O(1)

for(i=0; ii++){ ⇒ O(n)

System.out.print(""+num_vet[i]+", "); ⇒ O(1)

} ⇒ O(1)

} ⇒ O(1)

Dado a análise assintótica do algoritmo acima, concluímos que a sua complexidade é de O(n²) pois possui dois laços de repetição aninhados que levarão mais tempo em sua execução.

Vetor sendo organizado passo a passo:

[5, 3, 10, 1, 6] ⇒ Vetor na formação inicial;

[3, 5, 10, 1, 6] ⇒ O número 3 é comparado com o sub-arranjo a sua esquerda (5), muda de posição.

[3, 5, 10, 1, 6] ⇒ O número 10 é comparado com o sub-arranjo a sua esquerda (3 e 5), permanece no mesmo lugar pois é maior que todos os elementos.

[3, 5, 1, 10, 6] ⇒ O número 1 é comparado com o sub-arranjo a sua esquerda (3, 5 e 10), troca de lugar com o 10 e é realizada uma nova comparação.

[3, 1, 5, 10, 6] ⇒ O número 1 é comparado com o sub-arranjo a sua esquerda (3, 5), troca de lugar com o 5 e é realizada uma nova comparação.

[1, 3, 5, 10, 6] ⇒ O número 1 é comparado com o sub-arranjo a sua esquerda (3), troca de lugar com o 3 e parte para o outro elemento.

[1, 3, 5, 6, 10] ⇒ O número 6 é comparado com o sub-arranjo a sua esquerda (1, 3, 5 e 10), troca de posição com o 10 deixando assim o vetor organizado.

Algoritmo de Seleção (Selection Sort):

OBS: Linguagem usada – JAVA.

public static void main(String[] args){ ⇒ O(1)

int menor, aux, i, j, n=9; ⇒ O(1)

int[] vetor = {3, 6, 5, 1, 2, 8, 7, 9, 4}; ⇒ O(1)

for(i=0; in-1; i++){ ⇒ O(n)

menor = i; ⇒ O(1)

for(j = i+1; jn; j++){ ⇒ O(n)

if(vetor[menor] > vetor[j]){ ⇒ O(1)

menor = j; ⇒ O(1)

} ⇒ O(1)

} ⇒ O(1)

if(i != menor){ ⇒ O(1)

aux = vetor[i]; ⇒ O(1)

vetor[i] = vetor[menor]; ⇒ O(1)

vetor[menor] = aux; ⇒ O(1)

} ⇒ O(1)

} ⇒ O(1)

for(i=0; ii++){ ⇒ O(n)

System.out.print(""+vetor[i]+" ,"); ⇒ O(1)

} ⇒ O(1)

} ⇒ O(1)

Dado a análise assintótica do algoritmo acima, concluímos que a sua complexidade é de O(n²) pois possui dois laços de repetição aninhados que levarão mais tempo em sua execução.

Vetor sendo organizado passo a passo:

[3, 6, 5, 1, 2, 8, 7, 9, 4] ⇒ Vetor na formação inicial

[1, 6, 5, 3, 2, 8, 7, 9, 4] ⇒ O menor valor do vetor (1) é selecionado e troca de posição com o primeiro item do vetor (3).

[1, 2, 5, 3, 6, 8, 7, 9, 4] ⇒ Número 2 troca de posição com o número 6.

[1, 2, 3, 5, 6, 8, 7, 9, 4] ⇒ Número 3 troca de posição com o número 5.