SóProvas


ID
3305374
Banca
AOCP
Órgão
SUSIPE-PA
Ano
2018
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

Assinale a alternativa correta a respeito dos principais algoritmos de ordenação.

Alternativas
Comentários
  • O Quicksort é o algoritmo mais eficiente na ordenação por comparação. Nele se escolhe um elemento chamado de pivô, a partir disto é organizada a lista para que todos os números anteriores a ele sejam menores que ele, e todos os números posteriores a ele sejam maiores que ele.

    fonte:

  • Heapsort: utiliza uma estrutura de dados chamada heap binário para ordenar os elementos a medida que os insere na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada.

    Ordenação por Inserção  

    Sua complexidade é equivalente à da ordenação bolha. A ordenação da tabela pode ser estendida até o (i + 1)-ésimo elemento por meio de comparações sucessivas deste com os elementos anteriores, isto é, com o iésimo elemento, com o (i – 1)-ésimo elemento, procurando sua posição correta na parte da tabela que já está ordenada.

     Ordenação Rápida (Quicksort)

    A ordenação rápida é um dos mais eficientes dentre os conhecidos.

    Dois pontos são decisivos para o bom desempenho do algoritmo: a escolha do pivô e o particionamento da tabela.

    Alternativa: A

  • QuickSort é um algoritmo de divisão e conquista. Ele seleciona um elemento como pivô e particiona o array fornecido ao redor do pivô selecionado. Existem muitas versões diferentes do quickSort que selecionam o pivô de maneiras diferentes.

    Sempre escolha o primeiro elemento como pivô.

    Sempre escolha o último elemento como pivô (implementado abaixo)

    Escolha um elemento aleatório como pivô.

    Escolha a mediana como pivô.

    O principal processo no quickSort é a partição (). O objetivo das partições é, dado uma matriz e um elemento x da matriz como pivô, colocar x em sua posição correta na matriz classificada e colocar todos os elementos menores (menores que x) antes de x, e colocar todos os elementos maiores (maiores que x) depois x. Tudo isso deve ser feito em tempo linear.

    Inserção é um algoritmo de classificação simples que funciona de maneira semelhante à maneira como você classifica as cartas de baralho em suas mãos. O array é virtualmente dividido em uma parte ordenada e outra não ordenada. Os valores da parte não ordenada são selecionados e colocados na posição correta na parte ordenada.

    Algoritmo:

    Para ordenar uma matriz de tamanho n em ordem crescente:

    1: Itere de arr [1] para arr [n] na matriz.

    2: Compare o elemento atual (chave) com seu predecessor.

    3: Se o elemento-chave for menor do que seu predecessor, compare-o com os elementos anteriores. Mova os elementos maiores uma posição para cima para liberar espaço para o elemento trocado.

    Heapsort é uma técnica de classificação baseada em comparação baseada na estrutura de dados Binary Heap. É semelhante à classificação por seleção, onde primeiro encontramos o elemento mínimo e colocamos o elemento mínimo no início. Repetimos o mesmo processo para os elementos restantes.

    1. Construa um heap máximo a partir dos dados de entrada.

    2. Nesse ponto, o maior item é armazenado na raiz do heap. Substitua-o pelo último item do heap seguido pela redução do tamanho do heap em 1. Finalmente, monte a raiz da árvore.

    3. Repita a etapa 2 enquanto o tamanho do heap for maior que 1.

    shellSort é um algoritmo de classificação que primeiro classifica os elementos distantes uns dos outros e reduz sucessivamente o intervalo entre os elementos a serem classificados. É uma versão generalizada do insertionSort.

    No shellSort, os elementos em um intervalo específico são classificados. O intervalo entre os elementos é diminuído gradualmente com base na sequência usada. O desempenho da classificação de shell depende do tipo de sequência usada para um determinado array de entrada.

    O selectionSort classifica uma matriz encontrando repetidamente o elemento mínimo (considerando a ordem crescente) da parte não classificada e colocando-o no início. O algoritmo mantém dois subarrays em um determinado array.

  • Força Guerreiro!!!!!!

  • GABARITO A

    Quick Sort: Neste método, a lista é dividida em parte esquerda e parte direita, sendo que os elementos da parte esquerda são todos menores do que os elementos da parte direita. Em seguida, as duas partes são ordenadas recursivamente.

    • Ordenação rápida e eficiente;
    • Adota a estratégia de divisão-e-conquista;

        A estratégia consiste em rearranjar as chaves de modo que os menores precedem os maiores.

        Pivô: O primeiro da lista;

    • Melhor caso: O(n log n)
    • Médio caso: O(n log n)
    • Pior caso: O(n²)