Algoritmos #04 - Algoritmos de ordenação, parte I
Na computação, há uma quantidade imensa de diferentes tipos de algoritmos, que utilizam dos mais diversos métodos para realizar funções que facilitem a vida do programador. A partir de agora, a série de posts sobre algoritmos irá focar em apresentar alguns exemplos das mais famosas sequências de instruções da ciência da computação.
Algoritmos de ordenação
A primeira categoria a ser trabalhada é a de ordenação, composta por algoritmos que têm como atribuição organizar uma determinada sequência de elementos (listas, arrays, vetores, etc), de forma crescente ou decrescente. Eles podem ser divididos em métodos simples (de fácil implementação, mas pouca velocidade) e métodos eficientes (de implementação mais complexa, mas maior velocidade). Este primeiro post tratará, a seguir, do primeiro caso, o qual é mais adequado para pequenos vetores.
Métodos simples
- Bubble Sort
O Bubble Sort é conhecido por ser o algoritmo de ordenação de mais fácil implementação. Nele, são comparados elementos adjacentes entre si. O elemento da 1ª posição será comparado com o elemento da posição seguinte (2ª), caso o 1º seja maior, ele irá trocar de lugar com o 2º, caso contrário, eles permanecem nas mesmas posições. A seguir, o 2º valor será comparado ao 3º, e assim por diante. Isso se repetirá até que todos os elementos estejam ordenados. É provável que o Bubble Sort tenha que percorrer uma lista várias vezes, até que ela esteja organizada, por isso, ele não é indicado para vetores de maior tamanho.
- Selection Sort
O Selection Sort, também conhecido como "Ordenação por seleção", consiste em pegar um elemento i, a começar pelo 1º elemento, e compará-lo com os elementos à sua direita, até que um valor menor seja encontrado e as posições entre eles sejam trocadas. Caso não haja um número menor, as comparações serão feitas utilizando-se do elemento seguinte, ou seja, ele visa colocar o menor elemento na primeira posição, o segundo menor na segunda posição, e assim sucessivamente (O processo é repetido até que a lista seja ordenada). O Selection Sort costuma ser mais rápido que o Bubble, mas também é um algoritmo instável.
- Insertion Sort
O Insertion Sort, ou "Ordenação por inserção", é o mais rápido e estável dos métodos de ordenação simples a serem apresentados neste post. Ele começa a partir do segundo elemento (x) do vetor, que vai sendo comparado a todos os elementos à sua esquerda (início do vetor). Caso o valor comparado à ele (y) seja maior, o x é inserido na posição anterior a y, até que não haja elementos maiores à esquerda. O processo é repetido para todos os elementos da lista, que só será percorrida uma única vez.
Parte II: Algoritmos eficientes de ordenação
Referências
Comentários
Postar um comentário