If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

Curso: Computer science theory > Unidade 1

Lição 9: Quick sort
Computação
Computer science theory
Algoritmos
Quick sort
© 2024 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies

Visão geral do quicksort

Google Sala de Aula
Assim como o merge sort, o quicksort usa divisão e conquista, portanto ele é um algoritmo recursivo. O modo como o quicksort usa divisão e conquista é um pouco diferente de como o merge sort faz. No merge sort, o passo da divisão não faz muita coisa, e todo o trabalho acontece na etapa de combinar. No quicksort é o oposto: todo o trabalho acontece na etapa da divisão. Na verdade, o passo de combinar no quicksort não faz absolutamente nada.
O quicksort tem algumas outras diferenças em relação ao merge sort. O quicksort funciona a partir da posição e seu tempo de execução no pior caso é tão ruim quanto o selection sort e o insertion sort: Θ(n2). Mas o seu tempo de execução médio é tão bom quanto o do merge sort: Θ(nlog2⁡n).
Então, por que pensar no quicksort quando o merge sort é no mínimo tão bom quanto ele? Isso é porque o fator constante oculto na notação big-Θ para o quicksort é muito bom. Na prática, o quicksort supera o merge sort e supera significativamente o selection sort e o insertion sort.
É desta forma que o quicksort usa divisão e conquista. Assim como o merge sort, pense na ordenação de um subarray array[p..r], onde inicialmente o subarray é array[0..n-1].
  1. Divida escolhendo qualquer elemento no subarray array[p..r]. Chame esse elemento de pivô.
    Reorganize os elementos em array[p..r] para que todos os elementos em array[p..r] que são menores ou iguais ao pivô fiquem à esquerda e todos os elementos que são maiores que o pivô fiquem à sua direita. Chamamos esse procedimento de particionamento. Neste ponto, não importa em que ordem os elementos à esquerda do pivô estão uns em relação aos outros, e o mesmo vale para os elementos à direita do pivô. Nós nos preocupamos apenas com o fato de que cada elemento deve estar no lado correto do pivô.
    Por uma questão de prática, nós iremos sempre escolher o elemento mais à direita da subarray, array[r], como o pivô. Então, por exemplo, se a subarray consiste de [9, 7, 5, 11, 12, 2, 14, 3, 10, 6], então nós escolhemos o 6 como pivô. Depois de particionarmos, a subarray pode parecer [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. Deixe q ser o indice de onde o pivô termina.
  2. Conquista ordenando recursivamente as subarrays array[p..q-1] (todos os elementos à esquerda do pivô, que devem ser menor ou igual ao pivô) e array[q+1..r] (todos os elementos à direita do pivô, que devem ser maiores que o pivô).
  3. Combinar sem fazer nada. Uma vez que o conquer step organize recursivamente, nós estaremos prontos. Por que? Todos os elementos à esquerda do pivô, na array[p..q-1], são menores ou iguais ao pivô e são organizados, e todos os elementos à direita do pivô, na array[q+1..r], são maiores que o pivô e são organizados. Os elementos na array[p..r] não podem ajudar mas são classificados!
    Pense no nosso exemplo. Depois de organizar recursivamente as subarrays à esquerda e à direita do pivô, a subarray à esquerda do pivô [2, 3, 5], e a subarray à direita do pivô é [7, 9, 10, 11, 12, 14]. Então a subarray tem [2, 3, 5], seguida por 6, seguida por [7, 9, 10, 11, 12, 14]. A subarray está organizada.
Os casos base são subarrays com menos de dois elementos, assim como no merge sort. No merge sort, você nunca vê um subarray sem elementos, mas no quicksort isso é possível, se os outros elementos no subarray são todos menores do que o pivô ou todos maiores do que o pivô.
Vamos voltar à etapa da conquista e analisar a ordenação recursiva dos subarrays. Depois da primeira partição, temos dois subarrays [5, 2, 3] e [12, 7, 14, 9, 10, 11], com o 6 como pivô.
Para ordenar o subarray [5, 2, 3], escolhemos 3 como o pivô. Depois do particionamento, temos [2, 3, 5]. O subarray [2], à esquerda do pivô, é um caso base quando fazemos a recursão, assim como o subarray[5], à direita do pivô.
Para ordenar o subarray [12, 7, 14, 9, 10, 11], escolhemos 11 como pivô. Depois de particionar, temos [7, 9, 10] à esquerda do pivô e [14, 12] à direita. Em seguida, os subarrays são ordenados, resultando em [7, 9, 10], seguido de 11, seguido de [12, 14].
É assim que o algoritmo completo do quicksort funciona. Localizações em azul no array foram pivôs em chamadas recursivas anteriores, e então os valores nessas localizações não serão examinados ou movidos novamente:
Um diagrama que mostra cinco etapas de ordenação de um array usando quicksort.
  1. O array começa com os elementos [9, 7, 5, 11, 12, 2, 14, 3, 10, 6], com o índice p apontando para o primeiro elemento e o índice r apontando para o último elemento.
  2. Os elementos do array agora estão ordenados como [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. O array agora tem um índice q apontando para o quarto elemento, que contém o valor 6.
  3. Os elementos do array agora estão ordenados como [2, 3, 5, 6, 7, 9, 10, 11, 14, 12]. O array agora tem vários índices denominados p, q e r. O primeiro p aponta para o primeiro elemento, o primeiro q aponta para o segundo elemento, o primeiro r aponta para o terceiro elemento. O segundo p aponta para o quinto elemento, o segundo q aponta para o oitavo elemento e o segundo p aponta para o elemento final.
  4. Os elementos do array agora estão ordenados como [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]. O primeiro par p e r aponta para o primeiro elemento, o segundo par p e r aponta para o terceiro elemento. O terceiro p aponta para o quinto elemento, um q e o terceiro r apontam para o sétimo elemento. O quarto p e um q apontam para o nono elemento, e o quarto r aponta para o último elemento.
  5. Os elementos do array ainda estão ordenados como [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]. O primeiro p aponta para o quinto elemento, o primeiro q e o primeiro r apontam para o sexto elemento. Um par p e r aponta para o último elemento.
  6. Os elementos do array ainda estão ordenados como [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]. Um único par p e r aponta para o quinto elemento.
Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.

Quer participar da conversa?

Entrar
Nenhuma postagem por enquanto.
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.