As vantagens e desvantagens dos algoritmos de ordenação
Thinkstock/Comstock/Getty Images
Ordenar um conjunto de itens em uma lista é uma tarefa frequente na programação. Muitas vezes, um ser humano pode realizar essa tarefa intuitivamente. No entanto, um programa de computador precisa seguir uma sequência exata de instruções para completá-la, e essa sequência é chamada algoritmo. Um algoritmo de ordenação é um método utilizado para colocar uma lista de itens desorganizados em uma determinada ordem. A sequência da ordenação é determinada por uma chave. Existem vários algoritmos de ordenação que diferem em termos de eficiência e desempenho. Alguns conhecidos e importantes desse tipo incluem: bubble sort, selection sort, insertion sort e o quick sort.
Bubble sort
O bubble sort troca repetidamente elementos adjacentes que não estão em ordem até que toda lista de itens esteja em sequência. Dessa maneira, os itens flutuam na lista conforme os seus valores, indo o maior (no caso de ordenação crescente) pro final ao fim de cada iteração.
A principal vantagem desse algoritmo é que sua implementação é fácil e conhecida. Além disso, no bubble sort, os elementos são trocados de lugar sem utilizar armazenamento temporário, o que faz o requerimento de espaço ser mínimo. A principal desvantagem é o fato de que não apresenta bons resultados quando a lista contém muitos itens. Isso porque esse tipo de ordenação exige n² passos de processamento para cada número n de elementos que serão ordenados. Portanto, o bubble sort é indicada para o ensino acadêmio, mas não para aplicações na vida real.
Selection sort
O selection sort vasculha repetidamente a lista de itens, selecionando um elemento de cada vez e colocando-o na posição correta da sequência.
A principal vantagem do selection sort é que ela funciona bem em uma lista pequena. Além disso, por ser um algoritmo de ordenação de local, não precisa de armazenamento temporário além do necessário para guardar a lista original. A principal desvantagem é sua baixa eficiência em listas grandes. Assim como o bubble sort, ele exige n² números de passos para cada n elementos. Adicionalmente, o seu desempenho é facilmente influenciado pela ordem inicial dos itens antes do processo de triagem. Devido a isso, esse tipo seleção é adequado apenas para uma lista em que poucos elementos estejam em ordem aleatória.
Insertion sort
O insertion sort varre a lista repetidamente e, a cada vez, insere um item da sequência desordenada na posição correta.
A principal vantagem da ordenação por inserção é a sua simplicidade, além de mostrar um bom desempenho em listas pequenas. É um algoritmo de ordenação de local, logo, o requerimento de espaço é mínimo. A desvantagem é que não possui um desempenho tão bom quanto outros algoritmos de ordenação. Com n² passos necessários para funcionar, o insertion sort também não funciona bem com listas grandes. No entanto, é particularmente útil com listas de poucos itens.
Quick sort
O quick sort trabalha com o princípio da divisão-e-conquista. Primeiramente, ela divide a lista de itens em duas sub-listas com base em um elemento pivô. Todos os elementos na primeira sub-lista são dispostos de maneira que sejam menores do que o pivô, enquanto que todos os elementos na segunda sub-lista são dispostos para serem maiores que o pivô. O mesmo processo de particionamento e organização é executado repetidamente nas sub-listas resultantes até que toda a lista seja organizada.
O quick sort é considerado por alguns o melhor algoritmo de ordenação por causa da sua vantagem significante em termos de eficiência, uma vez que funciona bem com uma lista grande de itens. Por ordenar no próprio local, também não há necessidade de espaço adicional de armazenamento. A leve desvantagem que ela apresenta é que seu pior desempenho é similar à média de desempenho dos outros algoritmos descritos acima. Entretanto, é importante notar que esse pior caso é muito raro. De um modo mais geral, o quick sort produz o método de organização mais eficiente e amplamente utilizado para organizar uma lista de qualquer tamanho.
Referências
- "Introduction to Algorithms"; Thomas H. Cormen et al.; 2009
- ShannaraSite.org: Bubble sort [em inglês]
- ShannaraSite.org: Selection sort [em inglês]
- ShannaraSite.org: Insertion sort [em inglês]
- ShannaraSite.org: Quick sort [em inglês]
Sobre o Autor
Joe Wandy is an experienced software developer who has worked in the development and maintenance of several large-scale enterprise systems. He holds a Bachelor of Science in computing. Wandy has used his expertise in software development to write easy-to-understand tutorials and articles for various websites since 2011.
Créditos Fotográficos
Thinkstock/Comstock/Getty Images