Assinale a alternativa a respeito dos algoritmos de ordenaçã...

A alternativa correta é a alternativa C: Bubble Sort e Quicksort têm um tempo de execução quadrático no pior caso.

Vamos entender por que essa é a resposta correta e analisar as alternativas incorretas.

Alternativa A: Quicksort tem um tempo de execução logarítmico no pior caso.

Esta alternativa está incorreta. O Quicksort tem um tempo de execução esperado de O(n log n) em média, mas no pior caso, seu tempo de execução é O(n²). Isso ocorre quando o pivô escolhido é sempre o menor ou maior elemento da lista, levando a partições desbalanceadas.

Alternativa B: Bubble Sort tem um tempo de execução logarítmico em média.

Esta alternativa também está incorreta. O Bubble Sort é um algoritmo de ordenação simples que tem um tempo de execução de O(n²) tanto no pior caso quanto na média. Ele compara e troca elementos adjacentes repetidamente até que a lista esteja ordenada.

Alternativa C: Bubble Sort e Quicksort têm um tempo de execução quadrático no pior caso.

Esta é a alternativa correta. Conforme mencionado, ambos os algoritmos têm um tempo de execução de O(n²) no pior caso. Para o Bubble Sort, isso ocorre em qualquer situação, enquanto para o Quicksort, isso acontece quando as partições são desbalanceadas.

Alternativa D: O algoritmo Quicksort efetua a ordenação da lista, realizando trocas de ordem sucessivas de elementos subsequentes.

Esta alternativa está incorreta. O Quicksort não realiza trocas de ordem sucessivas de elementos subsequentes. Ele escolhe um pivô e particiona a lista em elementos menores e maiores que o pivô, e então ordena essas sublistas recursivamente.

Alternativa E: Bubble Sort é um algoritmo recursivo que efetua, a cada passo, o particionamento da lista que será ordenada em duas sublistas: uma com os elementos maiores que um elemento escolhido como pivô, e a outra com os elementos maiores que este.

Esta alternativa está incorreta. A descrição dada pertence ao Quicksort, não ao Bubble Sort. O Bubble Sort não é recursivo e não faz partições; ele simplesmente compara e troca elementos adjacentes.

Para resolver questões sobre algoritmos de ordenação em concursos, é essencial conhecer não apenas os tempos de execução médios e no pior caso, mas também como cada algoritmo funciona. Esses conhecimentos permitem identificar rapidamente erros em descrições de algoritmos e entender suas características fundamentais.

Espero que essa explicação tenha sido clara e ajudado a entender o funcionamento e as complexidades dos algoritmos Bubble Sort e Quicksort. Se tiver mais dúvidas, sinta-se à vontade para perguntar!

===Letra A ===

Quicksort tem um tempo de execução logarítmico no pior caso. (ERRADO)

Quicksort possui complexidade O(n²) no pior caso e O(n log n) no caso médio;

===Letra B ===

Bubble Sort tem um tempo de execução logarítmico em média. (ERRADO)

Bubble Sort possui complexidade O(n²) para o pior caso e para o caso médio;

===Letra C ===

Bubble Sort e Quicksort têm um tempo de execução quadrático no pior caso. (CERTO)

===Letra D ===

O algoritmo Quicksort efetua a ordenação da lista, realizando trocas de ordem sucessivas de elementos subsequentes. (ERRADO)

Ordenação Rápida (Quicksort)

- O quicksort adota a estratégia de divisão e conquista.

- A estratégia consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves "maiores".

- Escolhe-se um elemento (pivô), em seguida a lista é organizada de forma a deixar os elementos menores à sua esquerda e os maiores à direita;

ü Possui complexidade O(n²) no pior caso e O(n log n) no caso médio;

===Letra E ===

Bubble Sort é um algoritmo recursivo que efetua, a cada passo, o particionamento da lista que será ordenada em duas sublistas: uma com os elementos maiores que um elemento escolhido como pivô, e a outra com os elementos maiores que este. (ERRADO)

Ordenação Bolha (Bubble Sort)

- Uma iteração se limita a percorrer a tabela do início ao fim, sem interrupção, trocando de posição dois elementos consecutivos sempre que estes se apresentem fora de ordem.

- A intenção do método é mover os elementos maiores em direção ao fim da tabela. 

- Ao terminar a primeira iteração pode-se garantir que as trocas realizadas posicionam o maior elemento na última posição. Na segunda iteração, o segundo maior elemento é posicionado, e assim sucessivamente

c-

Bubble sort has a worst-case and average complexity of О(n2), where n is the number of items being sorted. Most practical sorting algorithms have substantially better worst-case or average complexity, often O(n log n). Even other О(n2) sorting algorithms, such as insertion sort, generally run faster than bubble sort, and are no more complex. Therefore, bubble sort is not a practical sorting algorithm.

https://en.wikipedia.org/wiki/Bubble_sort

A = QUICKSORT é QUADRÁTICO NO PIOR CASO - O(n^2) 

B = BUBLLESORT é QUADRÁTICO NO MÉDIO CASO - O(n^2) 

D e E = estão invertidas

GABARITO C

Gabarito



Quadro resumo

Bubble Sort

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

Insertion Sort:

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

Selection Sort:

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

Quick Sort:

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

Shell Sort:

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

Merge Sort:

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

Heap Sort:

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