A ideia deste artigo \u00e9 apresentar um resumo r\u00e1pido desses algoritmos de ordena\u00e7\u00e3o, abordando os seguintes t\u00f3picos:<\/p>\n\n\n\n
- \n
- Algoritmo de Ordena\u00e7\u00e3o da Bolha<\/li>\n\n\n\n
- Algoritmo de Ordena\u00e7\u00e3o por Sele\u00e7\u00e3o<\/li>\n\n\n\n
- Algoritmo de Ordena\u00e7\u00e3o por Inser\u00e7\u00e3o<\/li>\n\n\n\n
- Desempenho dos Algoritmos de Ordena\u00e7\u00e3o\n
- \n
- Complexidade<\/li>\n\n\n\n
- Efici\u00eancia<\/li>\n<\/ul>\n<\/li>\n\n\n\n
- Quadro comparativo dos algoritmos de ordena\u00e7\u00e3o<\/li>\n\n\n\n
- Quest\u00f5es para praticar<\/li>\n<\/ul>\n\n\n\n
Algoritmo de Ordena\u00e7\u00e3o da Bolha (<\/strong>Bubble Sort<\/em><\/strong>)<\/strong><\/h2>\n\n\n\n
O m\u00e9todo da bolha consiste em percorrer uma lista, comparando elementos que est\u00e3o lado a lado (pares consecutivos) e trocando suas posi\u00e7\u00f5es se estiverem fora de ordem<\/strong>. Em cada passo, o maior elemento “flutua” para a \u00faltima posi\u00e7\u00e3o, e este processo \u00e9 repetido at\u00e9 que todos os elementos estejam na ordem correta.<\/p>\n\n\n\n
Aqui est\u00e1 um exemplo de como ordenar a lista [8, 2, 3, 5, 1]<\/strong>:<\/p>\n\n\n\n
Exemplo de ordena\u00e7\u00e3o com o m\u00e9todo de ordena\u00e7\u00e3o bolha<\/em><\/figcaption><\/figure>\n\n\n\n Perceba que a cada itera\u00e7\u00e3o, o maior elemento entre aqueles que ainda n\u00e3o foram ordenados \u00e9 movido para a \u00faltima posi\u00e7\u00e3o. \u00c9 importante notar que durante esse processo, ocorreram 10 compara\u00e7\u00f5es e 7 trocas.<\/p>\n\n\n\n
No m\u00e9todo da bolha, o n\u00famero de compara\u00e7\u00f5es realizadas pode ser calculado usando a seguinte f\u00f3rmula: compara\u00e7\u00f5es = N * (N – 1) \/ 2, onde N representa o n\u00famero de elementos presentes na lista.<\/p>\n\n\n\n
Algoritmo de Ordena\u00e7\u00e3o por Sele\u00e7\u00e3o (<\/strong>Selection Sort<\/em><\/strong>)<\/strong><\/h2>\n\n\n\n
O algoritmo de ordena\u00e7\u00e3o por sele\u00e7\u00e3o opera escolhendo o menor elemento de uma lista desordenada e colocando-o na primeira posi\u00e7\u00e3o<\/strong>. Isso \u00e9 repetido em cada itera\u00e7\u00e3o, removendo os elementos j\u00e1 ordenados. Em outras palavras, a cada passo, seleciona-se o menor elemento da parte n\u00e3o ordenada da lista e o posiciona no in\u00edcio.<\/p>\n\n\n\n
Aqui est\u00e1 uma representa\u00e7\u00e3o visual de um exemplo de ordena\u00e7\u00e3o utilizando o algoritmo de sele\u00e7\u00e3o com a lista [6, 2, 3, 5, 1, 4]<\/strong>:<\/p>\n\n\n\n
Exemplo de ordena\u00e7\u00e3o com o algoritmo de ordena\u00e7\u00e3o por sele\u00e7\u00e3o.<\/em><\/figcaption><\/figure>\n\n\n\n Observe que a cada itera\u00e7\u00e3o o menor elemento dentre os n\u00e3o ordenados \u00e9 trocado pelo primeiro elemento deles. O algoritmo realiza, no m\u00e1ximo, uma troca a cada itera\u00e7\u00e3o. Uma desvantagem deste algoritmo \u00e9 que mesmo com lista j\u00e1 ordenada, ele compara todos os elementos da parte n\u00e3o ordenada por ele para descobrir o menor elemento.<\/p>\n\n\n\n
Por exemplo, perceba que depois da primeira itera\u00e7\u00e3o, os elementos 2 e 3 j\u00e1 est\u00e3o ordenados. Mesmo assim, o algoritmo faz as compara\u00e7\u00f5es com os demais elementos para \u201cter certeza\u201d de que realmente eles s\u00e3o os menores elementos.<\/p>\n\n\n\n
Nesse exemplo, o algoritmo ao todo faz 15 compara\u00e7\u00f5es e apenas 3 trocas, pois na segunda e terceira itera\u00e7\u00e3o n\u00e3o s\u00e3o realizadas trocas. <\/p>\n\n\n\n
As compara\u00e7\u00f5es s\u00e3o realizadas para encontrar o menor elemento. Na primeira itera\u00e7\u00e3o, o algoritmo compara os seis elementos, ou seja, realiza 5 compara\u00e7\u00f5es. Na segunda itera\u00e7\u00e3o, como o primeiro elemento j\u00e1 est\u00e1 ordenado, o algoritmo s\u00f3 compara os cinco elementos restantes, realizando quatro compara\u00e7\u00f5es. <\/p>\n\n\n\n
Assim como no m\u00e9todo da bolha, a f\u00f3rmula C = n * (n-1) \/ 2 encontra o n\u00famero de compara\u00e7\u00f5es realizadas pela ordena\u00e7\u00e3o por sele\u00e7\u00e3o. <\/p>\n\n\n\n
Algoritmo de Ordena\u00e7\u00e3o por Inser\u00e7\u00e3o (<\/strong>Insertion Sort<\/em><\/strong>)<\/strong><\/h2>\n\n\n\n
O algoritmo de ordena\u00e7\u00e3o por inser\u00e7\u00e3o funciona assim: voc\u00ea divide a lista em duas partes, uma parte ordenada e outra desordenada. Em cada passo, pega-se o primeiro elemento da parte desordenada e o coloca na posi\u00e7\u00e3o correta da parte ordenada<\/strong>. Repete-se esse processo at\u00e9 que todos os elementos estejam na parte ordenada e a lista esteja completamente ordenada.<\/p>\n\n\n\n
Aqui est\u00e1 uma representa\u00e7\u00e3o visual de um exemplo de ordena\u00e7\u00e3o utilizando o algoritmo de inser\u00e7\u00e3o com a lista [6, 2, 3, 5, 1, 4]<\/strong>:<\/p>\n\n\n\n
Exemplo de ordena\u00e7\u00e3o com o algoritmo de ordena\u00e7\u00e3o por inser\u00e7\u00e3o<\/em><\/figcaption><\/figure>\n\n\n\n Observe que no in\u00edcio, o elemento 6 \u00e9 considerado como ordenado. Em seguida, o algoritmo seleciona o primeiro elemento n\u00e3o ordenado e o insere na posi\u00e7\u00e3o correta entre os elementos ordenados. Por exemplo, se tivermos a parte ordenada [2, 6] e o elemento 3 for selecionado, ele ser\u00e1 inserido entre os dois valores, resultando em [2, 3, 6]. No final, a lista estar\u00e1 totalmente ordenada.<\/p>\n\n\n\n
Em resumo, o n\u00famero de compara\u00e7\u00f5es e movimenta\u00e7\u00f5es feitas pelo algoritmo varia dependendo do grau de ordena\u00e7\u00e3o da lista. Para listas com pouca ordena\u00e7\u00e3o, muitas compara\u00e7\u00f5es e movimenta\u00e7\u00f5es s\u00e3o necess\u00e1rias. Por outro lado, para listas quase ordenadas, apenas algumas compara\u00e7\u00f5es e movimenta\u00e7\u00f5es s\u00e3o necess\u00e1rias.<\/p>\n\n\n\n
Desempenho dos Algoritmos de Ordena\u00e7\u00e3o<\/strong><\/h2>\n\n\n\n
Complexidade dos algoritmos de ordena\u00e7\u00e3o<\/strong><\/h3>\n\n\n\n
Aqui est\u00e1 um quadro comparativo da complexidade dos algoritmos de ordena\u00e7\u00e3o bolha, por sele\u00e7\u00e3o e por inser\u00e7\u00e3o nos casos pior, m\u00e9dio e melhor:<\/p>\n\n\n\n
Algoritmo de Ordena\u00e7\u00e3o<\/td> Pior Caso<\/td> Caso M\u00e9dio<\/td> Melhor Caso<\/td><\/tr> Bolha<\/td> O(n^2)<\/td> O(n^2)<\/td> O(n^2)**<\/td><\/tr> Sele\u00e7\u00e3o<\/td> O(n^2)<\/td> O(n^2)<\/td> O(n^2)<\/td><\/tr> Inser\u00e7\u00e3o<\/td> O(n^2)<\/td> O(n^2)<\/td> O(n)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n ** Uma varia\u00e7\u00e3o do m\u00e9todo bolha com condi\u00e7\u00e3o de parada tem complexidade linear, ou seja, N, no melhor caso, isto \u00e9, quando a lista est\u00e1 ordenada. Neste caso, o algoritmo apenas percorre a lista uma vez, e estando ela ordenada, finaliza a execu\u00e7\u00e3o.<\/p>\n\n\n\n
O algoritmo de ordena\u00e7\u00e3o por inser\u00e7\u00e3o possui no melhor caso a complexidade de N.<\/p>\n\n\n\n
Por fim, o pior e o m\u00e9dio caso para todos os tr\u00eas algoritmos s\u00e3o O(n^2), o que significa que eles s\u00e3o menos eficientes em conjuntos de dados n\u00e3o ordenados ou grandes.<\/p>\n\n\n\n
Em resumo, temos:
<\/p>\n\n\n\n- \n
- Pior e m\u00e9dio caso<\/strong>: os tr\u00eas algoritmos tem complexidade quadr\u00e1tica (n\u00b2) <\/li>\n\n\n\n
- Melhor caso:\n
- \n
- Ordena\u00e7\u00e3o por sele\u00e7\u00e3o<\/strong>: complexidade quadr\u00e1tica, ou seja, n\u00b2.<\/li>\n\n\n\n
- Ordena\u00e7\u00e3o por inser\u00e7\u00e3o<\/strong>: complexidade linear, ou seja, n.<\/li>\n\n\n\n
- M\u00e9todo da bolha<\/strong>:\n
- \n
- algoritmo tradicional da bolha: complexidade quadr\u00e1tica, <\/li>\n\n\n\n
- algoritmo com condi\u00e7\u00e3o de parada: complexidade linear. <\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
Efici\u00eancia dos algoritmos de ordena\u00e7\u00e3o<\/strong><\/h3>\n\n\n\n
Entre os tr\u00eas algoritmos de ordena\u00e7\u00e3o discutidos neste resumo, o menos eficiente \u00e9 o algoritmo da bolha. Embora seja f\u00e1cil de entender, na pr\u00e1tica ele \u00e9 mais lento em compara\u00e7\u00e3o com os outros algoritmos de mesma complexidade, devido ao grande n\u00famero de movimenta\u00e7\u00f5es e compara\u00e7\u00f5es que requer.<\/p>\n\n\n\n
Por outro lado, o algoritmo de ordena\u00e7\u00e3o por sele\u00e7\u00e3o tem menos movimenta\u00e7\u00f5es, tornando-o vantajoso para ordenar estruturas complexas. No entanto, uma desvantagem \u00e9 que o n\u00famero de compara\u00e7\u00f5es \u00e9 o mesmo para todas as listas, inclusive as que j\u00e1 est\u00e3o ordenadas.<\/p>\n\n\n\n
Por \u00faltimo, o algoritmo de ordena\u00e7\u00e3o por inser\u00e7\u00e3o demonstra o melhor desempenho na pr\u00e1tica em compara\u00e7\u00e3o com os outros dois. O n\u00famero de compara\u00e7\u00f5es e movimenta\u00e7\u00f5es depende do n\u00edvel de ordena\u00e7\u00e3o da lista. Em uma lista totalmente reversa, o n\u00famero de compara\u00e7\u00f5es e movimenta\u00e7\u00f5es \u00e9 alto, mas em uma lista j\u00e1 ordenada, \u00e9 m\u00ednimo, resultando em uma complexidade linear nesse caso. Enfim, este algoritmo \u00e9 recomendado para conjuntos pequenos de dados.<\/p>\n\n\n\n
Quadro comparativo dos principais algoritmos de ordena\u00e7\u00e3o<\/strong><\/h2>\n\n\n\n
O quadro abaixo apresenta um resumo comparativo dos algoritmos de ordena\u00e7\u00e3o bolha, por sele\u00e7\u00e3o e por inser\u00e7\u00e3o:<\/p>\n\n\n\n
Caracter\u00edstica<\/strong><\/td> Bolha<\/strong><\/td> Sele\u00e7\u00e3o<\/strong><\/td> Inser\u00e7\u00e3o<\/strong><\/td><\/tr> Complexidade<\/strong><\/td> O(n^2)O(n^2)O(n)<\/td> O(n^2)O(n^2)O(n^2)<\/td> O(n^2)O(n^2)O(n)<\/td><\/tr> Efici\u00eancia<\/strong><\/td> Baixa<\/td> M\u00e9dia<\/td> Alta para pequenos conjuntos de dados<\/td><\/tr> Estabilidade<\/strong><\/td> Est\u00e1vel<\/td> N\u00e3o est\u00e1vel<\/td> Est\u00e1vel<\/td><\/tr> Modo de opera\u00e7\u00e3o<\/strong><\/td> Compara\u00e7\u00f5es consecutivas<\/td> Sele\u00e7\u00e3o do menor elemento<\/td> Inser\u00e7\u00e3o ordenada<\/td><\/tr> Uso<\/strong><\/td> Pouco comum<\/td> Pouco comum<\/td> Comum em listas encadeadas ou pequenos conjuntos de dados<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n - \n
- Complexidade<\/strong>: Refere-se ao n\u00famero de opera\u00e7\u00f5es que o algoritmo realiza para ordenar um conjunto de dados.
<\/li>\n\n\n\n- Efici\u00eancia<\/strong>: Refere-se \u00e0 velocidade do algoritmo em ordenar um conjunto de dados.
<\/li>\n\n\n\n- Estabilidade<\/strong>: Refere-se \u00e0 capacidade de manter a ordem relativa dos elementos iguais em um conjunto de dados durante a ordena\u00e7\u00e3o.
<\/li>\n\n\n\n- Modo de opera\u00e7\u00e3o<\/strong>: Refere-se \u00e0 maneira como o algoritmo funciona para ordenar um conjunto de dados.<\/li>\n<\/ul>\n\n\n\n
Quest\u00f5es comentadas<\/strong><\/h1>\n\n\n\n
Quest\u00e3o 1<\/strong><\/h3>\n\n\n\n
Ano: 2014 Banca: CESGRANRIO \u00d3rg\u00e3o: Petrobras Prova: CESGRANRIO – 2014 – Petrobras – T\u00e9cnico(a) de Inform\u00e1tica J\u00fanior<\/strong><\/p>\n\n\n\n
Os algoritmos de ordena\u00e7\u00e3o por sele\u00e7\u00e3o (SS) e bubble sort (BS) foram usados para ordenar a sequ\u00eancia 31, 11, 23, 17, 13 de forma crescente.<\/p>\n\n\n\n
Quantas trocas e compara\u00e7\u00f5es foram realizadas, respectivamente, por cada um?<\/p>\n\n\n\n
a) SS – 3 e 10 \/ BS – 7 e 10<\/p>\n\n\n\n
b) SS – 3 e 11 \/ BS – 8 e 16<\/p>\n\n\n\n
c) SS- 8 e 16\/ BS – 3 e 11<\/p>\n\n\n\n
d) SS – 7 e 16 \/ BS – 3 e 10<\/p>\n\n\n\n
e) SS- 4 e 11\/ BS – 8 e 16<\/p>\n\n\n\n
Coment\u00e1rio<\/strong>:<\/p>\n\n\n\n
Pela f\u00f3rmula do n\u00famero de compara\u00e7\u00f5es do algoritmo de ordena\u00e7\u00e3o por sele\u00e7\u00e3o e bolha j\u00e1 matar\u00edamos a quest\u00e3o. Veja que a lista possui 5 elementos, logo:<\/p>\n\n\n\n
C = n * (n – 1) \/ 2;<\/em><\/strong><\/p>\n\n\n\n
C = 5 * 4 \/ 2;<\/em><\/strong><\/p>\n\n\n\n
C = 10.<\/em><\/strong><\/p>\n\n\n\n
Assim, tanto o m\u00e9todo da bolha, quanto a ordena\u00e7\u00e3o por sele\u00e7\u00e3o fazem 10 compara\u00e7\u00f5es. Dessa forma, a \u00fanica alternativa que possui 10 compara\u00e7\u00f5es para o algoritmo de ordena\u00e7\u00e3o por sele\u00e7\u00e3o e da bolha \u00e9 a letra A<\/strong>.<\/p>\n\n\n\n
Mas, para o desencargo de consci\u00eancia, vamos verificar o n\u00famero de trocas realizadas. <\/p>\n\n\n\n
Vejamos:<\/p>\n\n\n\n
<\/figure>\n\n\n\n
Observe que no m\u00e9todo bolha tivemos 7 trocas e na ordena\u00e7\u00e3o por sele\u00e7\u00e3o tivemos 3 trocas. <\/p>\n\n\n\n
Portanto, a letra A<\/strong> \u00e9 a alternativa correta.<\/p>\n\n\n\n
Quest\u00e3o 2<\/strong><\/h3>\n\n\n\n
Ano: 2011 Banca: CESGRANRIO \u00d3rg\u00e3o: FINEP Prova: CESGRANRIO – 2011 – FINEP – Analista – Desenvolvimento de Sistemas<\/strong><\/p>\n\n\n\n
Considerando-se a an\u00e1lise assint\u00f3tica (Nota\u00e7\u00e3o Big O), qual \u00e9 a complexidade do caso m\u00e9dio do algoritmo de ordena\u00e7\u00e3o chamado de Ordena\u00e7\u00e3o por Inser\u00e7\u00e3o?<\/p>\n\n\n\n
a) O(n\u00b2)<\/p>\n\n\n\n
b) O(1)<\/p>\n\n\n\n
c) O(n)<\/p>\n\n\n\n
d) O(n log n)<\/p>\n\n\n\n
e) O(log n)<\/p>\n\n\n\n
Coment\u00e1rios:<\/strong><\/p>\n\n\n\n
A complexidade do algoritmo de ordena\u00e7\u00e3o por inser\u00e7\u00e3o \u00e9:<\/p>\n\n\n\n
- \n
- Pior caso e caso m\u00e9dio: n\u00b2<\/strong><\/li>\n\n\n\n
- Melhor caso: n<\/strong><\/li>\n<\/ul>\n\n\n\n
Portanto, a letra A<\/strong> \u00e9 a alternativa correta<\/strong>.<\/p>\n\n\n\n
Quest\u00e3o 3<\/strong><\/h3>\n\n\n\n
Ano: 2021 Banca: CESGRANRIO \u00d3rg\u00e3o: Banco do Brasil Prova: CESGRANRIO – 2021 – Banco do Brasil – Agente de Tecnologia<\/strong><\/p>\n\n\n\n
Dentre os problemas identificados pela ger\u00eancia de um banco comercial, est\u00e1 a localiza\u00e7\u00e3o das contas dos seus titulares nas listagens e nos relat\u00f3rios impressos em diferentes situa\u00e7\u00f5es. Um especialista de TI sugeriu ordenar as contas por meio dos CPF dos seus n<\/em> titulares antes das impress\u00f5es.<\/p>\n\n\n\n
Dentre alguns algoritmos pr\u00e9-selecionados para essa ordena\u00e7\u00e3o, o especialista escolheu o algoritmo de ordena\u00e7\u00e3o por inser\u00e7\u00e3o, no qual o consumo de tempo \u00e9, no melhor caso, proporcional a<\/p>\n\n\n\n
a) n log n <\/p>\n\n\n\n
b) log n<\/p>\n\n\n\n
c) n\u00b2<\/p>\n\n\n\n
d) n<\/p>\n\n\n\n
e) 1<\/p>\n\n\n\n
Coment\u00e1rios:<\/strong><\/p>\n\n\n\n
Quest\u00e3o bem semelhante \u00e0 anterior. A complexidade do algoritmo de ordena\u00e7\u00e3o por inser\u00e7\u00e3o \u00e9:<\/p>\n\n\n\n
- \n
- Pior caso e caso m\u00e9dio: n\u00b2<\/strong><\/li>\n\n\n\n
- Melhor caso: n<\/strong><\/li>\n<\/ul>\n\n\n\n
Portanto, a letra D \u00e9 a alternativa correta<\/strong>.<\/p>\n\n\n\n
Conclus\u00e3o<\/strong><\/h2>\n\n\n\n
Bom pessoal, terminamos por aqui este artigo. Procuramos apresentar um resumo dos pontos mais importantes dos principais algoritmos de ordena\u00e7\u00e3o para concursos p\u00fablicos. Espero que o conte\u00fado aqui apresentado seja \u00fatil em sua jornada rumo \u00e0 aprova\u00e7\u00e3o.<\/p>\n\n\n\n
<\/p>\n\n\n\n
Quer saber quais ser\u00e3o os pr\u00f3ximos concursos?<\/strong><\/p>\n\n\n\n
Confira nossos artigos!<\/strong><\/p>\n\n\n\n
- Melhor caso: n<\/strong><\/li>\n<\/ul>\n\n\n\n
- Melhor caso: n<\/strong><\/li>\n<\/ul>\n\n\n\n
- Efici\u00eancia<\/strong>: Refere-se \u00e0 velocidade do algoritmo em ordenar um conjunto de dados.
- Complexidade<\/strong>: Refere-se ao n\u00famero de opera\u00e7\u00f5es que o algoritmo realiza para ordenar um conjunto de dados.
- Ordena\u00e7\u00e3o por inser\u00e7\u00e3o<\/strong>: complexidade linear, ou seja, n.<\/li>\n\n\n\n
- Melhor caso:\n
- Pior e m\u00e9dio caso<\/strong>: os tr\u00eas algoritmos tem complexidade quadr\u00e1tica (n\u00b2) <\/li>\n\n\n\n
![\"Exemplo](\"https:\/\/lh7-us.googleusercontent.com\/XF_rRhX6MWmRZX2GG3Pp2aTu7y52jAAXv3DA4WQV0JcUo6sPB0FEawkBW82NXiiUvojkTVEh4_TKTa3UaYvYvicKR_LlAgqeAJ_a1lw6endGeXv9CzBbsmVoWpIQDG5_GfM8P3HP7ehK9EHYMn7Dgd4\")
![\"Exemplo](\"https:\/\/lh7-us.googleusercontent.com\/zJPaJj_WlYw0ULR-xoEItLD8zoxKg-mSQBCD2ro-AlvaygMyCN7JT-hyChbVli26FOwFs-1BOSKQEHB-Z1RJcaTmbmW7fqV1b6_9qZRasesEwzSKyrVF5iov3Nt6hcs3tWGPEhvz1ogdQQl_f2vnCUA\")
![\"Exemplo](\"https:\/\/lh7-us.googleusercontent.com\/IJ-1QBE6L4G7mV3k9hXJZ_-gi2nIl9QvvzNHPZWg9cfGfFojS2AeiDEItdhcDRYSlVdMCK5_DeV47gSRN33-Qw4y37jRi53PRBIhWIFOVyE5cp1DGN4zIo1rA-WzfqFdrUiMGCeTCKc0aSgCTVc0ZnI\")