{"id":4469,"date":"2023-05-09T16:29:47","date_gmt":"2023-05-09T19:29:47","guid":{"rendered":"https:\/\/elemarjr.com\/clube-de-estudos\/?p=4469"},"modified":"2023-10-21T21:39:07","modified_gmt":"2023-10-22T00:39:07","slug":"o-que-e-e-como-funciona-o-bubblesort","status":"publish","type":"artigos","link":"https:\/\/elemarjr.com\/clube-de-estudos\/artigos\/o-que-e-e-como-funciona-o-bubblesort\/","title":{"rendered":"O que \u00e9 e como funciona o BubbleSort?"},"content":{"rendered":"\n

O que \u00e9 BubbleSort?<\/h2>\n\n\n\n

O Bubble sort<\/em> \u00e9 um algoritmo simples de ordena\u00e7\u00e3o que recebe como entrada uma lista de elementos e produz uma lista ordenada de acordo com um crit\u00e9rio. \u00c9 um algoritmo popular, mas menos eficiente em rela\u00e7\u00e3o a outros algoritmos de ordena\u00e7\u00e3o.<\/p>\n\n\n\n

\"\"
Visualiza\u00e7\u00e3o est\u00e1tica do Bubble sort<\/strong>. Fonte: Wikipedia<\/a><\/figcaption><\/figure>\n\n\n\n

Exemplo simples<\/h2>\n\n\n\n

Imagine que voc\u00ea tem uma sequ\u00eancia de n\u00fameros, como 5, 1, 9, 3, e deseja orden\u00e1-los em ordem crescente. O Bubble sort <\/em>pode ajudar nessa tarefa, reorganizando os n\u00fameros at\u00e9 que estejam na ordem correta.<\/p>\n\n\n\n

Exemplo de implementa\u00e7\u00e3o em C#<\/h3>\n\n\n\n

Confira esse exemplo na linguagem de programa\u00e7\u00e3o C#.<\/p>\n\n\n\n

C#<\/span><\/path><\/path><\/svg><\/span>
using<\/span> System<\/span>;<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>Program<\/span> <\/span>{<\/span><\/span>\n    <\/span>static<\/span> <\/span>void<\/span> <\/span>Main<\/span>(<\/span>string<\/span>[]<\/span> args<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>int<\/span>[]<\/span> numeros <\/span>=<\/span> <\/span>{<\/span>5<\/span>,<\/span> <\/span>1<\/span>,<\/span> <\/span>9<\/span>,<\/span> <\/span>3<\/span>}<\/span>;<\/span> <\/span>\/\/ Array de n\u00fameros a ser ordenado<\/span><\/span>\n        <\/span>int<\/span> tamanho <\/span>=<\/span> <\/span>numeros<\/span>.<\/span>Length<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>\/\/ Loop principal do Bubble Sort<\/span><\/span>\n        <\/span>for<\/span> <\/span>(<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>;<\/span> <\/span>i<\/span> <\/span><<\/span> <\/span>tamanho<\/span> <\/span>-<\/span> <\/span>1<\/span>;<\/span> <\/span>i<\/span>++<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>for<\/span> <\/span>(<\/span>int<\/span> j <\/span>=<\/span> <\/span>0<\/span>;<\/span> <\/span>j<\/span> <\/span><<\/span> <\/span>tamanho<\/span> <\/span>-<\/span> <\/span>i<\/span> <\/span>-<\/span> <\/span>1<\/span>;<\/span> <\/span>j<\/span>++<\/span>)<\/span> <\/span>{<\/span><\/span>\n                <\/span>if<\/span> <\/span>(<\/span>numeros<\/span>[<\/span>j<\/span>]<\/span> <\/span>><\/span> <\/span>numeros<\/span>[<\/span>j<\/span>+<\/span>1<\/span>])<\/span> <\/span>{<\/span><\/span>\n                    <\/span>\/\/ Troca os elementos de posi\u00e7\u00e3o<\/span><\/span>\n                    <\/span>int<\/span> temp <\/span>=<\/span> <\/span>numeros<\/span>[<\/span>j<\/span>]<\/span>;<\/span><\/span>\n                    <\/span>numeros<\/span>[<\/span>j<\/span>]<\/span> <\/span>=<\/span> <\/span>numeros<\/span>[<\/span>j<\/span>+<\/span>1<\/span>]<\/span>;<\/span><\/span>\n                    <\/span>numeros<\/span>[<\/span>j<\/span>+<\/span>1<\/span>]<\/span> <\/span>=<\/span> <\/span>temp<\/span>;<\/span><\/span>\n                <\/span>}<\/span><\/span>\n            <\/span>}<\/span><\/span>\n        <\/span>}<\/span><\/span>\n<\/span>\n        <\/span>\/\/ Imprime o array ordenado<\/span><\/span>\n        <\/span>Console<\/span>.<\/span>WriteLine<\/span>(<\/span>"<\/span>Array ordenado:<\/span>"<\/span>)<\/span>;<\/span><\/span>\n        <\/span>for<\/span> <\/span>(<\/span>int<\/span> i <\/span>=<\/span> <\/span>0<\/span>;<\/span> <\/span>i<\/span> <\/span><<\/span> <\/span>tamanho<\/span>;<\/span> <\/span>i<\/span>++<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>Console<\/span>.<\/span>Write<\/span>(<\/span>numeros<\/span>[<\/span>i<\/span>]<\/span> <\/span>+<\/span> <\/span>"<\/span> <\/span>"<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n    <\/span>}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ Fonte: ChatGPT<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Exemplo de implementa\u00e7\u00e3o em Python<\/h3>\n\n\n\n
Confira esse exemplo na linguagem de programa\u00e7\u00e3o Python.<\/p>\n\n\n\n
Python<\/span><\/path><\/path><\/svg><\/span>
numeros <\/span>=<\/span> <\/span>[<\/span>5<\/span>,<\/span> <\/span>1<\/span>,<\/span> <\/span>9<\/span>,<\/span> <\/span>3<\/span>]<\/span> <\/span># Lista de n\u00fameros a ser ordenado<\/span><\/span>\ntamanho <\/span>=<\/span> <\/span>len<\/span>(<\/span>numeros<\/span>)<\/span><\/span>\n<\/span>\n# Loop principal do Bubble Sort<\/span><\/span>\nfor<\/span> i <\/span>in<\/span> <\/span>range<\/span>(<\/span>tamanho <\/span>-<\/span> <\/span>1<\/span>):<\/span><\/span>\n    <\/span>for<\/span> j <\/span>in<\/span> <\/span>range<\/span>(<\/span>tamanho <\/span>-<\/span> i <\/span>-<\/span> <\/span>1<\/span>):<\/span><\/span>\n        <\/span>if<\/span> numeros<\/span>[<\/span>j<\/span>]<\/span> <\/span>><\/span> numeros<\/span>[<\/span>j<\/span>+<\/span>1<\/span>]:<\/span><\/span>\n            <\/span># Troca os elementos de posi\u00e7\u00e3o<\/span><\/span>\n            numeros<\/span>[<\/span>j<\/span>],<\/span> numeros<\/span>[<\/span>j<\/span>+<\/span>1<\/span>]<\/span> <\/span>=<\/span> numeros<\/span>[<\/span>j<\/span>+<\/span>1<\/span>],<\/span> numeros<\/span>[<\/span>j<\/span>]<\/span><\/span>\n<\/span>\n# Imprime a lista ordenada<\/span><\/span>\nprint<\/span>(<\/span>"<\/span>Lista ordenada:<\/span>"<\/span>)<\/span><\/span>\nfor<\/span> i <\/span>in<\/span> <\/span>range<\/span>(<\/span>tamanho<\/span>):<\/span><\/span>\n    <\/span>print<\/span>(<\/span>numeros<\/span>[<\/span>i<\/span>],<\/span> <\/span>end<\/span>=<\/span>"<\/span> <\/span>"<\/span>)<\/span><\/span>\n<\/span>\n# Fonte: ChatGPT<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Exemplo de implementa\u00e7\u00e3o em Java<\/h3>\n\n\n\n
Confira esse exemplo na linguagem de programa\u00e7\u00e3o Java.<\/p>\n\n\n\n
Java<\/span><\/path><\/path><\/svg><\/span>
public<\/span> <\/span>class<\/span> <\/span>BubbleSort<\/span> <\/span>{<\/span><\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[]<\/span> <\/span>args<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>int<\/span>[]<\/span> <\/span>numeros<\/span> <\/span>=<\/span> <\/span>{<\/span>5<\/span>,<\/span> <\/span>1<\/span>,<\/span> <\/span>9<\/span>,<\/span> <\/span>3<\/span>}<\/span>;<\/span> <\/span>\/\/ Array de n\u00fameros a ser ordenado<\/span><\/span>\n        <\/span>int<\/span> <\/span>tamanho<\/span> <\/span>=<\/span> <\/span>numeros<\/span>.<\/span>length<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>\/\/ Loop principal do Bubble Sort<\/span><\/span>\n        <\/span>for<\/span> <\/span>(<\/span>int<\/span> <\/span>i<\/span> <\/span>=<\/span> <\/span>0<\/span>;<\/span> i <\/span><<\/span> tamanho <\/span>-<\/span> <\/span>1<\/span>;<\/span> i<\/span>++<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>for<\/span> <\/span>(<\/span>int<\/span> <\/span>j<\/span> <\/span>=<\/span> <\/span>0<\/span>;<\/span> j <\/span><<\/span> tamanho <\/span>-<\/span> i <\/span>-<\/span> <\/span>1<\/span>;<\/span> j<\/span>++<\/span>)<\/span> <\/span>{<\/span><\/span>\n                <\/span>if<\/span> <\/span>(<\/span>numeros<\/span>[<\/span>j<\/span>]<\/span> <\/span>><\/span> numeros<\/span>[<\/span>j<\/span>+<\/span>1<\/span>])<\/span> <\/span>{<\/span><\/span>\n                    <\/span>\/\/ Troca os elementos de posi\u00e7\u00e3o<\/span><\/span>\n                    <\/span>int<\/span> <\/span>temp<\/span> <\/span>=<\/span> numeros<\/span>[<\/span>j<\/span>]<\/span>;<\/span><\/span>\n                    numeros<\/span>[<\/span>j<\/span>]<\/span> <\/span>=<\/span> numeros<\/span>[<\/span>j<\/span>+<\/span>1<\/span>]<\/span>;<\/span><\/span>\n                    numeros<\/span>[<\/span>j<\/span>+<\/span>1<\/span>]<\/span> <\/span>=<\/span> temp<\/span>;<\/span><\/span>\n                <\/span>}<\/span><\/span>\n            <\/span>}<\/span><\/span>\n        <\/span>}<\/span><\/span>\n<\/span>\n        <\/span>\/\/ Imprime o array ordenado<\/span><\/span>\n        <\/span>System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>"<\/span>Array ordenado:<\/span>"<\/span>)<\/span>;<\/span><\/span>\n        <\/span>for<\/span> <\/span>(<\/span>int<\/span> <\/span>i<\/span> <\/span>=<\/span> <\/span>0<\/span>;<\/span> i <\/span><<\/span> tamanho<\/span>;<\/span> i<\/span>++<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>System<\/span>.<\/span>out<\/span>.<\/span>print<\/span>(<\/span>numeros<\/span>[<\/span>i<\/span>]<\/span> <\/span>+<\/span> <\/span>"<\/span> <\/span>"<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n    <\/span>}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ Fonte: ChatGPT<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Como funciona o BubbleSort<\/h2>\n\n\n\n
Funcionamento b\u00e1sico<\/h3>\n\n\n\n
O funcionamento do Bubble sort <\/em>\u00e9 baseado na compara\u00e7\u00e3o dos elementos da lista e na troca de posi\u00e7\u00e3o dos mesmos quando necess\u00e1rio para atingir a ordena\u00e7\u00e3o pretendida. Ele atua localmente, ou seja, pode alterar a pr\u00f3pria lista de entrada.<\/p>\n\n\n\n
Passo a passo do algoritmo<\/h3>\n\n\n\n
    \n
  1. Percorra a lista da esquerda para a direita.<\/li>\n\n\n\n
  2. Compare cada elemento com o elemento adjacente \u00e0 sua direita.<\/li>\n\n\n\n
  3. Se o elemento \u00e0 esquerda for maior que o elemento \u00e0 direita, troque-os de posi\u00e7\u00e3o.<\/li>\n\n\n\n
  4. Repita os passos 1a 3 at\u00e9 que a lista esteja ordenada.<\/li>\n<\/ol>\n\n\n\n
    Analisando a efici\u00eancia do BubbleSort<\/h2>\n\n\n\n
    Compara\u00e7\u00e3o de elementos<\/h3>\n\n\n\n
    O Bubble sort<\/em> compara cada elemento com o elemento adjacente, o que aumenta o n\u00famero de compara\u00e7\u00f5es \u00e0 medida que o tamanho da lista aumenta.<\/p>\n\n\n\n
    Troca de posi\u00e7\u00e3o dos elementos<\/h3>\n\n\n\n
    Sempre que o Bubble sort<\/em> encontra elementos fora de ordem, ele troca suas posi\u00e7\u00f5es. Isso significa que o algoritmo pode realizar v\u00e1rias trocas para cada par de elementos, aumentando ainda mais o tempo de execu\u00e7\u00e3o.<\/p>\n\n\n\n
    Complexidade do algoritmo<\/h3>\n\n\n\n
    A complexidade do Bubble sort<\/em> \u00e9 O(n^2) no pior caso e no caso m\u00e9dio, onde n \u00e9 o n\u00famero de elementos na lista. No entanto, no melhor caso, quando a lista j\u00e1 est\u00e1 ordenada, a complexidade \u00e9 O(n).<\/p>\n\n\n\n
    Casos de melhor e pior desempenho<\/h3>\n\n\n\n
    O melhor caso ocorre quando a lista j\u00e1 est\u00e1 ordenada, e o Bubble sort<\/em> apenas percorre a lista uma vez para verificar isso. O pior caso ocorre quando a lista est\u00e1 ordenada na ordem inversa, exigindo que o algoritmo realize v\u00e1rias trocas e percorra a lista v\u00e1rias vezes.<\/p>\n\n\n\n
    Alternativas ao BubbleSort<\/h2>\n\n\n\n
    Outros algoritmos de ordena\u00e7\u00e3o<\/h3>\n\n\n\n
    Embora o Bubble sort<\/em> seja simples e f\u00e1cil de entender, existem algoritmos de ordena\u00e7\u00e3o mais eficientes dispon\u00edveis, como o QuickSort<\/em>, o MergeSort<\/em> e o HeapSort<\/em>. Esses algoritmos geralmente t\u00eam melhor desempenho e s\u00e3o preferidos para listas maiores.<\/p>\n\n\n\n
    Compara\u00e7\u00e3o entre algoritmos<\/h3>\n\n\n\n
    Comparando o Bubble sort<\/em> com algoritmos como o QuickSort<\/em> e o MergeSort<\/em>, o Bubble sort<\/em> \u00e9 geralmente mais lento e menos eficiente. Por\u00e9m, em casos espec\u00edficos, como listas pequenas ou quase ordenadas, o Bubble sort<\/em> pode ser uma op\u00e7\u00e3o adequada.<\/p>\n\n\n\n
    Bubble Sort: uma escolha eficaz para pequenas listas<\/h2>\n\n\n\n
    O Bubble sort<\/em> \u00e9 um algoritmo de ordena\u00e7\u00e3o simples e popular, mas menos eficiente em compara\u00e7\u00e3o com outras op\u00e7\u00f5es dispon\u00edveis. Ele funciona comparando e trocando elementos adjacentes at\u00e9 que a lista esteja ordenada. Embora n\u00e3o seja a melhor escolha para listas grandes, ele pode ser \u00fatil em casos espec\u00edficos e \u00e9 f\u00e1cil de entender e implementar.<\/p>\n\n\n\n
    Esse conte\u00fado \u00e9 parte do material disponibilizado para os participantes do meu grupo de estudos de Algoritmos e Estruturas de Dados<\/strong>. Voc\u00ea quer participar desse grupo? Clique aqui e veja como funciona<\/strong><\/a>.<\/p>\n\n\n\n
    D\u00favidas Frequentes<\/h2>\n\n\n\n
    O Bubble sort <\/em>\u00e9 o algoritmo de ordena\u00e7\u00e3o mais eficiente?<\/strong>
    N\u00e3o, o Bubble sort n\u00e3o \u00e9 o algoritmo de ordena\u00e7\u00e3o mais eficiente. Existem outros algoritmos, como o QuickSort<\/em>, o MergeSort <\/em>e o HeapSort<\/em>, que geralmente t\u00eam melhor desempenho.<\/p>\n\n\n\n
    Quando devo usar o Bubble sort<\/em>?<\/strong>
    O Bubble sort<\/em> \u00e9 adequado para listas pequenas, quase ordenadas ou quando a simplicidade do algoritmo \u00e9 uma prioridade.<\/p>\n\n\n\n
    O Bubble sort <\/em>\u00e9 um algoritmo est\u00e1vel?<\/strong>
    Sim, o Bubble sort <\/em>\u00e9 um algoritmo est\u00e1vel, o que significa que a ordem relativa dos elementos iguais n\u00e3o \u00e9 alterada durante a ordena\u00e7\u00e3o.<\/p>\n\n\n\n
    O Bubble sort <\/em>pode ser otimizado?<\/strong>
    Sim, \u00e9 poss\u00edvel otimizar o Bubble sort <\/em>adicionando uma vari\u00e1vel para verificar se houve trocas na \u00faltima passagem. Se n\u00e3o houver trocas, significa que a lista j\u00e1 est\u00e1 ordenada e o algoritmo pode ser interrompido.<\/p>\n\n\n\n
    Qual \u00e9 a complexidade de espa\u00e7o do Bubble sort<\/em>?<\/strong>
    A complexidade de espa\u00e7o do Bubble sort <\/em>\u00e9 O(1), pois ele ordena os elementos “in-place<\/em>“, ou seja, n\u00e3o requer espa\u00e7o adicional para armazenar os elementos durante a ordena\u00e7\u00e3o.<\/p>\n","protected":false},"featured_media":4470,"parent":0,"template":"","cursos":[5],"class_list":["post-4469","artigos","type-artigos","status-publish","has-post-thumbnail","hentry","cursos-algortimos"],"acf":[],"_links":{"self":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/artigos\/4469","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/artigos"}],"about":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/types\/artigos"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/media\/4470"}],"wp:attachment":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/media?parent=4469"}],"wp:term":[{"taxonomy":"cursos","embeddable":true,"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/cursos?post=4469"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}