Flashcards de Quicksort (ordenação rápida)
Quicksort (Ordenação Rápida): Guia Completo para Estudantes
Toque para virar · Deslize para navegar
Algoritmo Quicksort
51 cartões
Cartão 1
Pergunta: Qual é a descrição lógica da função `quicksort`?
Resposta: A função `quicksort(array, inicio, fim)` verifica se `inicio < fim`. Se sim, ela chama `particionar(array, inicio, fim)` para obter o `indice_pivo` e
Cartão 2
Pergunta: Como funciona a função `particionar` no Quicksort, escolhendo o último elemento como pivô?
Resposta: A função `particionar(array, inicio, fim)` escolhe o `array[fim]` como pivô. Ela inicializa `i` como `inicio - 1`. Percorre `j` de `inicio` até `fim -
Cartão 3
Pergunta: Qual o impacto da escolha do pivô no desempenho do Quicksort?
Resposta: A escolha do pivô tem um impacto significativo no desempenho, podendo levar ao pior caso se o particionamento for desequilibrado (pivô fixo em array q
Cartão 4
Pergunta: Quais são as desvantagens de usar um pivô fixo (primeiro ou último elemento) no Quicksort?
Resposta: Usar um pivô fixo é simples de implementar, mas pode levar ao pior caso de desempenho se o array já estiver quase ordenado ou inversamente ordenado, r
Cartão 5
Pergunta: Por que a escolha de um pivô aleatório é benéfica para o Quicksort?
Resposta: Escolher um pivô aleatoriamente ajuda a evitar o pior caso de forma consistente, pois a probabilidade de sempre escolher um pivô ruim é muito baixa, t
Cartão 6
Pergunta: O que é a estratégia da 'mediana de três' na escolha do pivô e por que ela melhora o desempenho do Quicksort?
Resposta: A 'mediana de três' escolhe a mediana entre o primeiro, o último e o elemento do meio do sub-array como pivô. Esta estratégia geralmente produz um piv
Cartão 7
Pergunta: Qual é a complexidade de tempo do Quicksort no caso médio?
Resposta: A complexidade de tempo do Quicksort no caso médio é O(n log n).
Cartão 8
Pergunta: Quando ocorre o caso médio de complexidade O(n log n) no Quicksort?
Resposta: Ocorre quando o pivô escolhido divide o array em sub-arrays de tamanhos aproximadamente iguais, com aproximadamente `log n` níveis de recursão, onde c
Cartão 9
Pergunta: Qual é a complexidade de tempo do Quicksort no pior caso?
Resposta: A complexidade de tempo do Quicksort no pior caso é O(n²).
Cartão 10
Pergunta: Quando ocorre o pior caso de complexidade O(n²) no Quicksort?
Resposta: Ocorre quando a escolha do pivô resulta em particionamentos extremamente desequilibrados (pivô sempre o menor ou o maior elemento), levando a um sub-a