New Version: https://www.ime.usp.br/~otuyama/tutorial/sort/quicksort/Quicksort.html
A seguir, uma simulação de execução do algoritmo de ordenação Quicksort. O pivot (bound) utilizado neste exemplo é baseado em média aritmética.
"The chosen key value will be called the bound. The aim is now to produce a situation in which the keys of all items below a certain dividing line are equal to or less than the bound, while the keys of all items above the dividing line are equal to or greater than the bound." [Hoare]
Os símbolos de maior ">" e menor "<" estão ao lado dos valores que precisam ser permutado, uma vez que estão na partição incorreta (comparado ao pivot). O local da divisão do ponto de partição só é determinado depois do algoritmo percorrer o array (em ambas direções: "D" e "U" - down to up / up to down) e determinar as permutas necessárias. Este processo é repetido de forma recursiva, dentro das sub-partições (à esquerda "L" e à direita "R" do ponto de partição).
O pivot está em ponto flutuante, porém pode-se utilizar pivot (e toda aritmética restante) em inteiros, uma restrição comum para época em que o algoritmo foi criado.
3 1 4 1 5 9 2 6 5 3 5 8 (sum=52 n=12 avg=4.3) [0:11] pivot=4.3 0 1 2 3 4 5 6 7 8 9 10 11 D 3 1 4 1 5> 9> 4.3 <2 6 5 <3 5 8 U 3 1 4 1 3 2 [5] 9 6 5 5 5 8 [0:11].L[0:5] pivot=2.3 0 1 2 3 4 5 6 7 8 9 10 11 D 3> 1 4> 2.3 <1 3 <2 U 9 6 5 5 5 8 2 1 1 [2] 4 3 3 9 6 5 5 5 8 [0:11].L[0:5].L[0:2] pivot=1.3 0 1 2 3 4 5 6 7 8 9 10 11 D 2> 1 1.3 <1 U 4 3 3 9 6 5 5 5 8 1 1 [1] 2 4 3 3 9 6 5 5 5 8 [0:11].L[0:5].L[0:2].L[0:1] pivot=1.0 0 1 2 3 4 5 6 7 8 9 10 11 D 1> 1.0 <1 U 2 4 3 3 9 6 5 5 5 8 1 [0] 1 2 4 3 3 9 6 5 5 5 8 [0:11].L[0:5].R[3:5] pivot=3.3 0 1 2 3 4 5 6 7 8 9 10 11 1 1 2 D 4> 3 3.3 <3 U 9 6 5 5 5 8 1 1 2 3 3 [4] 4 9 6 5 5 5 8 [0:11].L[0:5].R[3:5].L[3:4] pivot=3.0 0 1 2 3 4 5 6 7 8 9 10 11 1 1 2 D 3> 3.0 <3 U 4 9 6 5 5 5 8 1 1 2 3 [3] 3 4 9 6 5 5 5 8 [0:11].R[6:11] pivot=6.3 0 1 2 3 4 5 6 7 8 9 10 11 1 1 2 3 3 4 D 9> 6 5 5 6.3 <5 8 U 1 1 2 3 3 4 5 6 5 5 [9] 9 8 [0:11].R[6:11].L[6:9] pivot=5.2 0 1 2 3 4 5 6 7 8 9 10 11 1 1 2 3 3 4 D 5 6> 5 5.2 <5 U 9 8 1 1 2 3 3 4 5 5 5 [8] 6 9 8 [0:11].R[6:11].L[6:9].L[6:8] pivot=5.0 0 1 2 3 4 5 6 7 8 9 10 11 1 1 2 3 3 4 D 5> 5 5.0 <5 U 6 9 8 1 1 2 3 3 4 5 5 [7] 5 6 9 8 [0:11].R[6:11].L[6:9].L[6:8].L[6:7] pivot=5.0 0 1 2 3 4 5 6 7 8 9 10 11 1 1 2 3 3 4 D 5> 5.0 <5 U 5 6 9 8 1 1 2 3 3 4 5 [6] 5 5 6 9 8 [0:11].R[6:11].R[10:11] pivot=8.5 0 1 2 3 4 5 6 7 8 9 10 11 1 1 2 3 3 4 5 5 5 6 D 9> 8.5 <8 U 1 1 2 3 3 4 5 5 5 6 8 [10] 9 1 1 2 3 3 4 5 5 5 6 8 9
Para se calcular a primeira média aritmética é necessário percorrer todo o array ao menos uma vez. Porém, após isto, as médias aritméticas posteriores podem ser calculadas (de forma eficiente) durante a própria execução do algoritmo Quicksort.
A seguir, outra simulação de execução do algoritmo Quicksort, porém utilizando letras ao invés de números inteiros. O pivot (bound) utilizado neste exemplo também é baseado em média aritmética, mas na forma de letra, de acordo com a seguinte conversão (número~'letra'): (1~'a') .. (26~'z').
h e l l o w o r l d (sum=124 n=10 avg=12~'l') [0:9] pivot=12~'l' 0 1 2 3 4 5 6 7 8 9 D h e l> l> 'l' o w o r <l <d U h e d l [3] o w o r l l [0:9].L[0:3] pivot=7~'g' 0 1 2 3 4 5 6 7 8 9 D h> e 'g' <d l U o w o r l l d e [1] h l o w o r l l [0:9].L[0:3].L[0:1] pivot=4~'d' 0 1 2 3 4 5 6 7 8 9 D d 'd' e U h l o w o r l l d [0] e h l o w o r l l [0:9].L[0:3].R[2:3] pivot=10~'j' 0 1 2 3 4 5 6 7 8 9 d e D h 'j' l U o w o r l l d e h [2] l o w o r l l [0:9].R[4:9] pivot=15~'o' 0 1 2 3 4 5 6 7 8 9 d e h l D o> w> o 'o' r <l <l U d e h l l l o [6] r w o [0:9].R[4:9].L[4:6] pivot=13~'m' 0 1 2 3 4 5 6 7 8 9 d e h l D l l 'm' o U r w o d e h l l l [5] o r w o [0:9].R[4:9].L[4:6].L[4:5] pivot=12~'l' 0 1 2 3 4 5 6 7 8 9 d e h l D l> 'l' <l U o r w o d e h l l [4] l o r w o [0:9].R[4:9].R[7:9] pivot=18~'r' 0 1 2 3 4 5 6 7 8 9 d e h l l l o D r> 'r' w <o U d e h l l l o o [7] w r [0:9].R[4:9].R[7:9].R[8:9] pivot=20~'t' 0 1 2 3 4 5 6 7 8 9 d e h l l l o o D w> 't' <r U d e h l l l o o r [8] w d e h l l l o o r w
[Hoare]
C. A. R. Hoare. Algorithm 64, Quicksort, Communications of the ACM, 4(7), 321-2 (1961).
C. A. R. Hoare. Quicksort. BCS, Computer Journal 5(1), 10-15(1962).
C. A. R. Hoare and C. B. Jones: Essays in Computing Science, 1989, Chapter 2.