Algoritmos e Estrutura de Dados: 1/2

Saudações, concurseiros !

Aqui estamos mais uma vez para dar início aos artigos sobre Algoritmos e Estrutura de Dados. Espero que estejam recuperados da maldade que foi o TCU – nada de desanimar, pois a jornada é longa e os que perseveram serão vencedores.

Quanto ao nosso encontro de hoje, é bom dizer que este é um assunto muito cobrado em qualquer prova de qualquer organizadora. A razão disso, simplesmente, é que ele é básico para qualquer curso de Ciência da Computação  e para o desenvolvimento de Software em geral. Nesta primeira parte, falaremos sobre os Algoritmos de busca e ordenação,  para, na segunda parte, falarmos das Estruturas de Dados.

Vamos lá.

Algoritmos de Busca

Busca linear (listas)

o Examina cada elemento da estrutura seqüencialmente

o Complexidade: O(n)

o Pode ser usado diretamente em uma lista não-processada (desordenada)

o Muito lento para grandes quantidades de dados,  mas aceitável para listas pequenas e que mudam constantemente

Implementação (iterativa):

alg12

Busca binária (listas)

o Realiza sucessivas divisões do espaço de busca, comparando o elemento buscado com o elemento no meio da subdivisão (divisão e conquista)

o Complexidade: O(log n)

o Parte do pressuposto que a lista é de acesso aleatório e está ordenada

o Ótimo desempenho comparado à busca linear para grandes quantidades de dados. Tem a desvantagem de requerer uma ordenação da lista após cada alteração na mesma

Implementação (recursiva):

alg21

Busca em árvores

o Depth-first (busca em profundidade)

Vai até uma determinada folha da árvore e faz backtracking

o Breadth-First (busca em largura)

Faz a procura por níveis. Começa na raiz e pesquisa todos os nós adjacentes no mesmo nível e, se não achar o elemento procurado, desce para o próximo nível e repete o processo

Algoritmos de Ordenação Simples – O(n2)

Bubble Sort

o A idéia é percorrer a lista diversas vezes,  fazendo o maior elemento deslocar-se para o final da mesma após sucessivas comparações

o Compara v[i] com v[i+1]. Se estiverem desordenados, há um swap (troca). Isso é repetido para todos os elementos da lista dois-a-dois

alg31

Selection Sort

o O algoritmo funciona da seguinte forma:

Ache o valor mínimo da lista

Troque-o pelo elemento na primeira posição

Repita esses passos para o restante da lista (começando de índice+1)

alg41

Insertion Sort

o Em termos gerais,  percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados.

alg51

Algoritmos de Ordenação Avançados – O(n log n)

Mergesort

o Conceitualmente o mergesort funciona da seguinte forma:

Divida a lista não-ordenada em duas sublistas de aproximadamente metade do tamanho da original

Divida cada uma das sublistas recursivamente até termos listas de tamanho 1, onde, então, elas são retornadas

Junte (merge) as duas sublistas em uma lista ordenada

alg61

Quicksort

o Os passos são:

Escolha um elemento , chamado de pivô, na lista

Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores ou iguais a ele, e todos os elementos posteriores ao pivô sejam maiores ou iguais a ele. Ao fim do processo o pivô           estará em sua posição final. Essa operação é denominada partição

Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores

o Complexidade: O (n log n) , mas , no pior caso, pode chegar a O(n2)

o Tipicamente, o quicksort é bem mais rápido do que os outros algoritmos que rodam a O(n log n), pois seu loop interno pode ser otimizado na maioria das arquiteturas

alg71

Para finalizar, vamos ver uma questão simples (presente na prova do TJ-PA comentada por mim) sobre algoritmos

42 – A necessidade de rearranjo de um certo conjunto de elementos, de acordo com um critério específico, indica

(A) o uso estrito de algoritmo de ordenação por permutação.

(B) o uso estrito de algoritmo de ordenação por particionamento.

(C) a possibilidade de uso de qualquer algoritmo de ordenação.

(D) o uso estrito de algoritmo de ordenação por inserção direta.

(E) o uso estrito de algoritmo de ordenação por seleção direta.

Comentário:

Há vários tipos de algoritmos de ordenação e todos eles têm o mesmo objetivo: rearranjar (ordenar) um conjunto de elementos de acordo com um critério específico (ordem numérica, alfabética, de acordo com alguma chave, etc.). O que varia entre eles é a estratégia utilizada para fazer reordenação – o que, normalmente, implica complexidades computacionais diferentes (quanto tempo demora o “pior caso” doalgoritmo, a quantidade de memória e processador que ele necessita, etc.)

Estratégias de permutação (bubble sort, insertion sort, shell sort, dentre outros) simplesmente movimentam os valores de entrada no vetor original de forma que a cada passo eles estejam cada mais ordenados, na posição correta, até o último passo, quando todos os elementos estão ordenados.

Estratégias de particionamento (mergesort, quicksort, dentre outros) usam o conceito de dividir-para-consquistar, isto é, dividem o conjunto de dados de entrada em partições menores até que seja trivial ordená-lo.

Portanto, voltando à questão, percebemos que qualquer algoritmo de ordenação tem a capacidade reordenar elementos de um conjunto de entrada segundo algum critério, modificando-se, apenas, a estratégia utilizada.

Bons estudos!

»crosslinked«

nandopedrosa

Analista de Finanças e Controle - Ministério da Fazenda/Coordenação de Sistemas Graduação: Universidade Federal de Pernambuco Certificações: ITIL Foundation Certified Java Programmer Certified Java Associate Certified Aprovações: Concurso Ano Cargo Posição Organizadora PBGÁS 2007 Analista de Sistemas 1 FCC SERPRO 2008 Administração de TI 1 CESPE COPERGÁS 2008 Analista de Sistemas 1 UPENET INMETRO 2007 Analista de Sistemas 2 CESPE STN 2008 AFC-TI 2 ESAF STJ 2008 Analista Judiciário 3 CESPE TRF-5 2008 Analista Judiciário 5 FCC TRF-5 2008 Técnico Judiciário 5 FCC TCU 2008 ACE-TI 7 CESPE TJ-PE 2007 Analista Judiciário 11 FCC BNDES 2008 Analista de Sistemas 27 CESGRANRIO

Você pode gostar...

1 Resultado

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *