Fala rapaziada do Kode Bro, na aula de hoje nós iremos falar sobre um algoritmo que irá fazer com que nós encontremos o K-ésimo menor elemento em um vetor e esse algoritmo é o QuickSelect.

O QuickSelect é um algoritmo baseado no algoritmo de ordenação                   e assim é semelhante ao mesmo.

O QuickSelect funciona da seguinte forma: utilizando o QuickSort, ele pega um elemento do vetor, iremos chamar esse elemento de pivô, e faz com que todos os elementos antes do pivô sejam menores ou iguais a ele e todos os elementos depois do pivô sejam maiores que do que ele, até que o vetor esteja totalmente ordenado. O número 8(de azul) é o pivô no seguinte exemplo:

2, 1, 3, 4, 8, 11, 10, 9, 13

Além disso, o QuickSelect aborda um intervalo de posições e se precisar, o algoritmo irá limitar o intervalo cada vez mais, seguindo suas restrições.

O algoritmo irá percorrer um for começando pela a primeira posição do intervalo até a última, sempre guardando em uma variável, chamada "ult", a última posição em que o elemento do vetor foi menor ou igual ao pivô, se no loop, nós não tivermos encontrado um número maior que o pivô então sempre mudaremos os elementos de posições iguais, porém quando encontrarmos um número maior que o pivô, na próxima vez que o elemento atual for menor ou igual ao pivô trocaremos esse elemento pelo primeiro elemento maior que o pivô, dessa forma fazemos com que os elementos anteriores ao pivô sejam menores ou iguais do que ele e o elementos sucessores a ele sejam maiores.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Quando terminarmos a "ordenação", nós checamos se "ult" é igual ao K, já que estamos procurando pelo K-ésimo menor elemento, se sim, então retornamos o elemento, se "ult" for maior que K, então a última posição do nosso intervalo se torna "ult" menos 1, já que temos certeza que o elemento que nós queremos estará antes de "ult" e se "ult" é menor que K, então a primeira posição do nosso intervalo se torna "ult" mais 1, pois temos certeza que o elemento que nós queremos estará depois de "ult".

Segue o código para melhor entedimento: