Como eu disse no post na parte mais "humana" da procura e contratação de emprego (nesse post), hoje eu vou começar a expor quais são os principais algorítimos que são utilizados pra dividir experiências e qualificações técnicas entre os candidatos.
É muito comum que elas existam e todos devemos sempre estar preparados para essas questões que sempre podem nos por a frente durante a decisão de um posto de trabalho.
A primeira que eu vou falar vai ser do quick sort.
Quick Sort
Um dos muitos métodos de ordenação de um vetor, o quick sort é sempre um bom começo quando estamos estudando análise de algorítimo.
Uma de suas muitas características é que ele utiliza a metodologia de "dividir para conquistar". O quick sort deverá ser implementado com algumas ideologias:
Propriedade de http://www.instanceofjava.com
Pivô
O pivô será utilizado como base da comparação com a primeira e a segunda parte da iteração corrente. Existem muitas formas de como escolher o pivô e cada um tem sua característica mas, muito comumente ele é escolhido no meio do vetor inicial.
Comparações e Troca
Aqui é o primeiro coração do algorítimo. Tudo o que ele se propõe é, através da comparação constante com o pivô, ele escolhe dois elementos onde um sempre será menor que o outro e troca as suas posições.
Subdivisão
O segundo coração do algorítimo, quando as comparações e trocas terminam seu processamento, o código separa o vetor inicial em pedaços menores e repete o processamento desde o começo (na escolha do pivô). Esse procedimento continua até o momento em que uma divisão de vetor resulte em elementos únicos.
No momento em que o tamanho dos vetores divididos forem 1, o vetor ordenado estará pronto!
Custo
Obviamente precisamos saber um pouco de análise de algorítimos para entendermos no que constitui o custo do código.
Pior caso: θ(n²).
Melhor caso: θ(log 2 n).
Código
Para ver o código do quick sort implementado em pseudo código entrar em:
É isso, pessoal, o quick sort é um algorítimo muito utilizado nas entrevistas de emprego. Por isso, entendam e mantenham sempre na mente ao menos a lógica. O resto vem com o tempo!
Até a próxima!
Nenhum comentário:
Postar um comentário