Vídeo: Ordenamiento Quicksort (Rápido!) en Java 2024
Aqui, você descobre como uma das técnicas de classificação mais utilizadas em Java realmente funciona. Esta técnica é chamada Quicksort, e é um uso muito engenhoso da recursão.
Para a maioria de nós, descobrir como os algoritmos de classificação, como o Quicksort, são meramente um exercício intelectual. A API Java já está sendo classificada.
A técnica Quicksort classifica uma matriz de valores usando a recursão. Seus passos básicos são assim:
-
Escolha um valor arbitrário que esteja dentro do intervalo de valores na matriz.
Esse valor é o ponto de pivô . A maneira mais comum de escolher o ponto de pivô é simplesmente escolher o primeiro valor na matriz. As pessoas escreveram graus de doutorado em formas mais sofisticadas para escolher um ponto de pivô que resulte em triagem mais rápida. Fique a par com o uso do primeiro elemento na matriz.
-
Reorganize os valores na matriz para que todos os valores que são inferiores ao ponto de pivô estão no lado esquerdo da matriz e todos os valores que são maiores ou iguais ao ponto de pivô estão no lado direito do matriz.
O valor de pivô indica o limite entre o lado esquerdo e o lado direito da matriz. Provavelmente não será um centro morto, mas isso não importa. Esta etapa é chamada de particionamento, e os lados esquerdo e direito dos arrays são partições.
-
Agora trate cada uma das duas seções da matriz como uma matriz separada e comece novamente com a Etapa 1 para essa seção.
Essa é a parte recursiva do algoritmo.
A parte mais difícil do algoritmo Quicksort é o passo de particionamento, que deve reorganizar a partição para que todos os valores que são menores que o ponto de pivô estão à esquerda e todos os elementos que são maiores que o pivô O ponto está à direita. Suponha que a matriz tenha esses dez valores:
38 17 58 22 69 31 88 28 86 12
Aqui o ponto de pivô é 38 e a tarefa do passo de particionamento é reorganizar a matriz para algo como isto: < 17 12 22 28 31 38 88 69 86 58
Observe que os valores ainda estão fora de ordem. A matriz, no entanto, foi dividida em torno do valor 38: Todos os valores que são menores que 38 estão à esquerda de 38 e todos os valores maiores que 38 estão à direita de 38.
Agora você pode dividir o entre duas partições no valor 38 e repita o processo para cada lado. O valor de pivô em si é válido para a partição esquerda, então a partição esquerda é esta:
17 12 22 28 31 38
Desta vez, o passo de particionamento seleciona 17 como o ponto de pivô e reorganiza os elementos da seguinte forma: > 12 17 22 28 31 38
Como você pode ver, esta parte da matriz está ordenada agora.Infelizmente, Quicksort não percebe que neste momento, então é preciso mais algumas recursões para ter certeza. Mas esse é o processo básico.
