A classificação rápida é um algoritmo de classificação altamente eficiente e é baseado no particionamento de uma matriz de dados em matrizes menores. Uma grande matriz é particionada em duas matrizes, uma das quais contém valores menores do que o valor especificado, digamos, pivô, com base no qual a partição é feita e outra matriz mantém valores maiores que o valor pivô.
Partições Quicksort e array e, em seguida, chama a si mesmo recursivamente duas vezes para classificar os dois subarrays resultantes. Este algoritmo é bastante eficiente para conjuntos de dados de grande porte, pois sua complexidade média e de pior caso são O (n2), respectivamente.
Partição em classificação rápida
A representação animada a seguir explica como para encontrar o valor do pivô em uma matriz.
O valor do pivô divide a lista em duas partes. E recursivamente, encontramos o pivô para cada sublista até que todas as listas contenham apenas um elemento.
Algoritmo de Pivô de classificação rápida
Com base em nosso entendimento de particionamento em classificação rápida, iremos agora tente escrever um algoritmo para ele, que é o seguinte.
Step 1 − Choose the highest index value has pivotStep 2 − Take two variables to point left and right of the list excluding pivotStep 3 − left points to the low indexStep 4 − right points to the highStep 5 − while value at left is less than pivot move rightStep 6 − while value at right is greater than pivot move leftStep 7 − if both step 5 and step 6 does not match swap left and rightStep 8 − if left ≥ right, the point where they met is new pivot
Pseudocódigo de Pivô de classificação rápida
O pseudocódigo para o algoritmo acima pode ser derivado como –
Algoritmo de classificação rápida
Usando o algoritmo de pivô recursivamente, acabamos com partições menores possíveis. Cada partição é então processada para classificação rápida. Definimos algoritmo recursivo para classificação rápida da seguinte forma –
Step 1 − Make the right-most index value pivotStep 2 − partition the array using pivot valueStep 3 − quicksort left partition recursivelyStep 4 − quicksort right partition recursively
Pseudocódigo de classificação rápida
Para obter mais informações, vejamos o pseudocódigo para algoritmo de classificação –
Para saber sobre a implementação de classificação rápida na linguagem de programação C, clique aqui.