Questão EPO - Quicksort

O QuickSort, como o MergeSort, é baseado em uma estratégia de dividir para conquistar e é um dos algoritmos de ordenação mais populares. O QuickSort é baseado no método de ordenação por trocas.

O algoritmo QuickSort pode ser dividido nos seguintes passos:

O array A[p..r] é subdividido em dois arrays A[p..q] e A[q+1..r] não vazios tal que cada elemento de A[p..q] é menor ou igual a cada elemento de A[q+1..r]. O índice q é calculado como parte deste particionamento.

Os dois subarrays A[p..q] e A[q+1..r] são ordenados por recursivas chamadas do QuickSort.

Dado o array  f e d h a c g b, e tomando o valor “d” para partição, o primeiro passo do quicksort rearranja o array da seguinte forma:

a) a b c d e f g h
b) f e d h a c g b
c) b c a d h e g f
d) b c f a h e g f
e) NDA