Estruturas de dados

Question 1

Algoritmos estáveis - valores iguais não sofrem alteração

Answer 1

Bubble Sort
Insertion
Merge

Question 2

Algoritmos instáveis

Answer 2

Selection
Quick
Heap
Shell

Question 3

Complexidade

Answer 3

Custo operacional para execução do algoritmo

Poder computacional - verifica o poder de processamento

Question 4

Bubble Sort

Answer 4

Posição ‘x’ comparado com a ‘x+1’
comparação com elementos adjacentes
Simples - arquivos pequenos

Percorre várias vezes - pouco eficiente

pior caso = O(n2)
médio = O(n2)
melhor = O(n)

Question 5

Selection Sort

Answer 5

Percorre o array e coloca o menor elemento na primeira posição -- lento PERCORRE TODOS ELEMENTOS ---> procura o mínimo 
Pouco eficiente
pior caso = O(n2)
médio = O(n2)
melhor = O(n2)

Question 6

Inserction Sort

Answer 6

Método preferido de jogador de carta – coloca ordenado
**Avança no array percorrendo vetor da esquerda pra direita ordenando os elementos posicionados à esquerda

Simples e eficiente -> ótimo para vetores parcialmente ordenados
Alto número de operações

pior caso = O(n2)
médio = O(n2)
melhor = O(n)

Question 7

Shell Sort

Answer 7

Otimização do INSERCTION - GAP - Permite comparação de elementos distantes
Desempenho depende do GAP
Melhor desempenho dos complexidade de O(n2)
Não trabalha paralelizado

pior caso = O(n2)
médio = O(n)
melhor = O(nlogN))

Question 8

Quick Sort

Answer 8

Dividir para conquistar - - PIVOT – eficiente quando tem muitos dados
Escolhe o PIVOT > partição > menores à esquerda e maiores à direita
*Ordenação recursiva dos valores
Mais utilizado - multithread
Precisa de muita memória

pior caso = O(n2)
médio = O(nlogN)
melhor = O(nlogN)

se não tiver pivot é o MERGE

Question 9

Merge Sort

Answer 9

Dividir para conquistar SEM PIVOT
ORDENAÇÃO E CONQUISTA
pior caso = O(nlogN)
médio = O(nlogN)
melhor =  O(nlogN)

Question 10

Heap Sort

Answer 10

Generalista - Utiliza estrutura de suporte TEMPORÁRIA para comparação
ELEMENTOS INSERIDOS NA ESTRUTURA E REMOVIDOS NA ORDEM DESEJADA
Mais eficiente

pior caso = O(nlogN)
médio = O(nlogN)
melhor = O(nlogN)