Definição – o que significa Quicksort?
Quicksort é um algoritmo de classificação popular que geralmente é mais rápido na prática em comparação com outros algoritmos de classificação. Ele utiliza uma estratégia de dividir e conquistar para classificar rapidamente os itens de dados, dividindo um grande array em dois arrays menores. Foi desenvolvido por Charles Antony Richard Hoare (comumente conhecido como CAR Hoare ou Tony Hoare) em 1960 para um projeto de tradução automática para o National Physical Laboratory.
Definirtec explica Quicksort
Quicksort é um algoritmo usado para classificar rapidamente os itens em uma matriz, independentemente do tamanho da matriz. É bastante escalonável e funciona relativamente bem para conjuntos de dados pequenos e grandes e é fácil de implementar com pouca complexidade de tempo. Isso é feito por meio de um método de divisão e conquista que divide uma única matriz grande em duas menores e repete esse processo para todas as matrizes criadas até que a classificação seja concluída.
O algoritmo quicksort é executado da seguinte maneira:
- Um ponto de pivô é escolhido na matriz.
- O array é reordenado para que todos os valores menores que o pivô sejam movidos antes dele e todos os valores maiores que o pivô sejam movidos depois dele, com valores igualando o pivô indo em qualquer direção. Quando isso é feito, o pivô está em sua posição final.
- A etapa acima é repetida para cada submatriz de valores menores, bem como feita separadamente para a submatriz com valores maiores.
Isso é repetido até que toda a matriz seja classificada.