Se você está vendo esta mensagem, significa que estamos tendo problemas para carregar recursos externos em nosso website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Conteúdo principal

Visão geral do quicksort

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: Θ(nlog2n).
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:
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?

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.