Assim como o merge sort, o quicksort usa divisão e conquista, portanto ele é um algoritmo recursido como o quicvo. O moksort 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. Quicksort funciona localmente. E seu tempo de execução no pior caso é tão ruim quanto o das ordenações por seleção e por inserção: \Theta(n^2)Θ(n2). Mas seu tempo de execução médio é tão bom quanto o merge sort: \Theta(n \lg n)Θ(nlgn). Então por que pensar em quicksort quando o merge sort é, pelo menos, igualmente bom? Porque o fator constante oculto na notação grande-Θ do quicksort é muito bom. Na prática, o quicksort tem desempenho melhor que o merge sort, e é significativamente melhor do que os algoritmos de seleção e de inserção.
É 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].
Divida por qualquer elemento escolhido na 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 a esquerda e que todos os elementos em array[p..r] fiquem a direita do pivô. Nós chamamos esse procedimento de particionamento. Nesse ponto, não importa a orderm que os elementos a esquerda do pivô estão em relação entre eles, e o mesmo vale para os elementos a direita do pivô. Nós apenas nos preocupamos que cada elemento esteja do 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.
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ô).
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 6 como o 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ô, resultando em [7, 9, 10] à esquerda do pivô e [14, 12] à direita. Depois que estes subarrays são ordenados, temos [7,9,10], seguidos por 11, seguidos por [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: