22. Bolhinhas, bolhas e bolhonas

Anteriormente investigamos a ordenação por inserção que é um representante da classe dos algoritmos incrementais ou online. Foi deixado como exercício construir uma variante da ordenação por inserção que explora o fato dessa ordenação ter como relação invariante fundamental que o prefixo da lista é mantido crescente. Com isso é aberta a possibilidade do uso da busca binária para encontrar a posição de um novo elemento da lista. Essa variante é conhecida como ordenação por inserção binária.

O problema de ordenação de uma lista é bastante simples e ideal para explorarmos um rico universo de ideias e soluções diferentes. A simplicidade do problema permite que o nosso foco não seja distraído do mundo da ideias para o das aplicações, que são sem dúvida alguma muito importantes. Continuaremos a utilizar ordenação nos nossos próximos laboratório de ideias e com isso também nos aperfeiçoarmos em métodos analíticos e experimentais para estimar os recursos computacionais utilizados por algoritmos.

22.1. Objetivos de aprendizagem

Todo problema tem o direito de ficar calado. Se o problema abrir mão desse direito, toda e qualquer informação que ele nos der pode e será usada para resolvê-lo de forma mais eficiente. Praticaremos a observação para evitar comparações desnecessárias feitas por alguns métodos de ordenação.

22.2. Borbulhamento

O problema que continuaremos a tratar é o de ordenar uma lista de elementos.

Dizemos que uma lista \(\mathtt{v[0:n]}\) é crescente se

\[\mathtt{v[0] \leq v[1] \leq v[2] \leq \cdots \leq v[n{-}1].}\]

Como temos feito nos exemplos as listas serão de objetos int mas elas poderiam ser de str ou de quaisquer outros objetos que possam atuar como operandos de operadores relacionais como <, <=, > ou >=.

Problema: Rearranjar os elementos de uma lista v[0:n] de modo que ela fique crescente.

O algoritmo que veremos é baseado na operação de troca. Por essa razão esse algoritmo é chamado de ordenação por troca, mas ele é conhecido como ordenação por borbulhamento ou Bubble sort.

A troca é realizada entre elementos vizinhos da lista que estão relativamente fora de ordem. Ou seja, se há um índice j tal que v[j] < v[j-1], então os elementos nessas posições devem ser trocados de posição v[j], v[j-1] = v[j-1], v[j]. Um par de posições adjacentes v[j], v[j-1] tal que v[j] < v[j-1] é chamado de inversão. É evidente que quando a lista v não possui inversão alguma então ela é crescente.

A ordenação por borbulhamento trabalha procurando incansavelmente por inversões em v. Assim que encontra alguma inversão, o algoritmo a desfaz trocando os elementos de posição. O algoritmo só se dá por satisfeito quando não há mais inversões e, portanto, a lista está ordenada.

Há certa maneiras, ou políticas, de procurar por inversões. De um certo ponto de vista a ordenação por inserção que vimos é uma ordenação por borbulhamento que em cada ‘’iteração i’’ procura por inversões com a participação do elemento que no início da iteração é o dono da posição v[i].

A política de troca que adotaremos é exemplificada na animação a seguir. Percorremos sequencialmente a lista v do início até uma certa posição que pode ser inclusive o final da lista, como na animação.

Durante o percurso todos os pares de elementos em posições vizinhas são comparados como, por exemplo, v[1] e v[0], v[6] e v[5] e, em geral, v[j] e v[j-1] para todo j no intervalo range(1, n) em que n um certo inteiro conveniente. Se v[j] e v[j-1] formarem uma inversão então seus valores são trocados. Por exemplo, para v = [w, x, y, 7, 5, z] temos inversão com j=4 já que v[4]=5 < v[3]=7. Portanto, eles elementos devem ser trocados de posição de tal forma que obtenhamos v = [w, x, y, 5, 7, z]. Aqui os valores de w, x, y e z são irrelevantes para o raciocínio.

Essa política de caça a inversões ilustrada na animação está implementada na função borbulhe() a seguir. Como de hábito, os números no início das linhas não faz parte do código e só está presente para fazermos futuras referências.

def borbulhe(v, n):
    ''' (list, int) -> int
    RECEBE uma lista v e um inteiro n.
    PERCORRE sequencialmente, do início até o fim, a lista v[0:n]
       desfazendo através de trocas todas as inversões encontradas ao
       longo do caminho.
    RETORNA o número de trocas realizadas durante o percurso.
    '''
 0  trocas = 0
 1  for j in range(1, n):
 2      if v[j] < v[j-1]:
 3          v[j], v[j-1] = v[j-1], v[j]
 4          trocas += 1
 5  return trocas

A função borbulhe() será o coração pulsante do algoritmo de ordenação que nos apresentará novas ideias. A seguir estão exemplos de execução da função borbulhe() no IPython.

In [24]: v = [7, 4, 11, 5, 3]
In [25]: t = borbulhe(v, 3)
In [26]: t
Out[26]: 1
In [27]: v
Out[27]: [4, 7, 11, 5, 3]

In [28]: v = [7, 4, 11, 5, 3]
In [29]: t = borbulhe(v, 4)
In [30]: t
Out[30]: 2
In [31]: v
Out[31]: [4, 7, 5, 11, 3]

In [32]: v = [7, 4, 11, 5, 3]
In [33]: t = borbulhe(v, 5)
In [34]: t
Out[34]: 3
In [35]: v
Out[35]: [4, 7, 5, 3, 11]

Vamos estimar o consumo de tempo da função borbulhe(), ou seja, quanto tempo ela trabalha para percorrer v desfazendo as inversões que encontra no caminho. Para isso vamos supor que cada linha consome 1 unidade de tempo para estimar o número de linhas executadas.

\[\begin{split}\begin{array}{ll} \text{linha} & \text{todas as execuções da linha}\\ \hline 0 & = \mathtt{1} \\ 1 & = \mathtt{n-1} \\ 2 & = \mathtt{n-1} \\ 3 & \leq \mathtt{n-1} \\ 4 & \leq \mathtt{n-1}\\ 5 & = \mathtt{1}\\[2mm] \hline \rule[0ex]{0ex}{3ex}% {\text{total}} & \leq \mathtt{4n-2 = \textup{O}(n)} \end{array}\end{split}\]

Com exceção feita ao número de execuções da linha 3 e 4, o número de execuções das demais linhas independem dos valores de v e estão calculados exatamente. O pior caso para a função borbulhe(), quando ela tem que trabalhar mais, ocorre quando a lista v[0,n] é decrescente. Nesse caso teremos que o número de execuções da linha 3 será exatamente \(\mathtt{n-1}\) e o número de execuções da linha 4 será também \(\mathtt{n-1}\).

O melhor caso para a função borbulhe() é quano v[0:n] já é crescente e não há inversões para serem trocadas. Nesse caso as linhas 3 e 4 não serão executadas uma única vez sequer. Mesmo assim, devido ao número de execuções da linha 1 e 2, teremos que o consumo de tempo da função borbulhe() será linear, ou seja, proporcional a \(\mathtt{n = \textup{O}(n)}\).

Conclusão. O consumo de tempo da função borbulhe(v, n) em todos os casos é proporcional a \(\mathtt{n = \textup{O}(n)}\).

Em termos práticos a linearidade do consumo de tempo de borbulhe() significa que se dobrarmos o tamanho da lista v que é dada à função borbulhe() então é de se esperar que o tempo gasto pela função para fazer o seu serviço também dobre.

22.3. Bubblesort

O bubble sort é um algoritmo por borbulhagem que se apoia na política de eliminação de inversões ditada pela função borbulhe(). Abaixo está uma possível implementação do bubble sort.

def bubblesort(v):
    '''(list) -> int
    RECEBE uma lista v.
    REARRANJA os elementos de v para que fique crescente.
    RETORNA o número de trocas feitas durante o processo.
    '''
 0  total_de_trocas = 0
 1  n = len(v)
 2  for i in range(n, 1, -1):  #1#
 3      total_de_trocas += borbulhe(v, i)
 4  return total_de_trocas

Para entender o funcionamento da função bubblesort() considere o seguinte exemplo. Suponha que v = [7, 4, 11, 5, 3]. Na chamada bubblesort(v), após a execução de

• borbulhe(v, 5) teremos que v = [4, 7, 5, 3, 11] e foram realizada 3 trocas;
• borbulhe(v, 4) obteremos v = [4, 5, 3, 7, 11] depois de mais 2 trocas;
• borbulhe(v, 3) chegaremos a v = [4, 3, 5, 7, 11] depois de mais 1 troca; e
• borbulhe(v, 2) veremos que v = [3, 4, 5, 7, 11] depois de mais 1 troca.

Pronto! Os elementos da lista v foram rearranjados e ela agora é crescente. Logo, para v = [7, 4, 11, 5, 3] a execução de bubblesort(v) faz com que v seja crescente após 7 trocas. Portanto, nesse caso, a execução de bubblesort(v) retorna 7.

A animação a seguir ilustra o funcionamento da função bubblesort(). As alturas das barras indicam os valores dos elementos de v. Quanto maior a barra, maior o valor.

As relações invariantes fundamentais da função bubblesort() é de que em #1# vale que:

• v[i:n] é crescente e, portanto, não contém inversões; e
• val0 <= val1 para todo elemento val0 em v[0:i] e todo elemento val1 em v[i:n].

Essas relações valem no início da primeira iteração já que i = n e v[n:n] é a lista vazia. Supondo que as relações invariantes valem, a correção do algoritmo é evidente. No início da última iteração das linhas \(1--4\) tem-se que i = 1. Da primeira relação invariante conclui-se que v[1:n] é crescente e da segunda temos que v[0] é mmenor ou igual que qualquer elemento em v[1:n].

Vamos estimar o consumo de tempo da função bubblesort(). Sabemos que o consumo de tempo da linha 3 é proporcional a \(i = \textup{O}(i)\). O consumo de tempo das demais linhas é constante, independe do número de elementos na lista v e, portanto, vamos supor que consome 1 unidade de tempo.

\[\begin{split}\begin{array}{ll} \text{linha} & \text{todas as execuções da linha}\\ \hline 0 & = \mathtt{1} \\ 1 & = \mathtt{1} \\ 2 & = \mathtt{n-2} \\ 3 & = \mathtt{n+(n-1)+\cdots+2 \ \approx \ n(n-1)/2}\\ 4 & = \mathtt{1}\\[2mm] \hline \rule[0ex]{0ex}{3ex}% {\text{total}} & \leq \mathtt{n^2/2 + n/2 + 1 = \textup{O}(n^2)} \end{array}\end{split}\]

Independentemente dos elementos na lista o consumo de tempo do bubblesort() é quadrático, ou seja, proporcional a \(\mathtt{n^2=\textup{O}(n^2)}\).

Conclusão. O consumo de tempo da função bubblesort() em todos os casos é proporcional a \(\mathtt{n^2 = \textup{O}(n^2)}\), onde \(\mathtt{n}\) é o número de elementos na lista v.

\[\begin{split} \begin{array}{|r|c|c|c|} \hline \mathtt{n}& \text{crescente} & \text{aleatória} & \text{decrescente}\\ \hline 1024 & 0.05 & 0.08 & 0.11 \\ \hline 2048 & 0.18 & 0.29 & 0.45 \\ \hline 4096 & 0.70 & 1.16 & 1.87 \\ \hline 8192 & 2.80 & 4.58 & 7.03 \\ \hline 16384 & 11.11 & 19.21 & 28.42 \\ \hline 32768 & 51.18 & 77.78 & 112.86 \\ \hline 65536 & 175.71 & 307.32 & 468.25 \\ \hline 131072 & 734.10 & 1279.06 & 1807.98 \\ \hline \end{array}\end{split}\]

Os tempos estão em segundos. Assim, por exemplo 1279 s é mais do que 21 minutos! Compare com os tempos obtidos com a ordenação por inserção.

A coluna com os consumos de tempo mostra que os tempos aproximadamente qradruplicam à medida que o número n de elementos da lista dobra. Esse é um sintoma de algoritmo que consome tempo quadrático proporcional a \(\mathtt{n^2 = \textup{O}(n^2)}\). Em termos absolutos de tempo gasto o bubblesort() gasta mais tempo quanto maior é o número de inversões na lista v.

O nome bubble sort é devido a uma metáfora. Imagine os valores na lista como sendo a densidade de bolhas de algumas substâncias imersas em água. Suponha que quanto menor o valor, menor a densidade da substância. Nesse caso as bolhas de menor densidade subirão rapidamente à superfície. A simulação abaixo foca nessa perspectiva.

     v     n=12
 +----+----+----+----+----+----+----+----+----+----+----+----+
 | 50 | 35 | 99 | 38 | 55 | 20 | 44 | 10 | 40 | 65 | 25 | 35 |
 +----+----+----+----+----+----+----+----+----+----+----+----+
   0    1    2    3    4    5    6    7    8    9   10   11


50                         10 | 10                         | 10
35                      10 50 | 50                      20 | 20
99                   10 35    | 35                   20 50 | 50
38                10 99       | 99                20 35    | 35
55             10 38          | 38             20 99       | 99
20          10 55             | 55          20 38          | 38
44       10 20                | 20          55             | 55
10       44                   | 44       25                | 25
40    25                      | 25       44                | 44
65 25 40                      | 40    35                   | 35
25 65                         | 65 35 40                   | 40
35                            | 35 65                      | 65

As trocas feitas pelo bubblesort(), com um pouco de boa vontade, se assemelham ao caminho feito pelas bolhas menos densas até a superfície e as mais densas até o fundo. Esse fenômeno ocorre quando vemos mergulhadoras soltando ar pela boca quando estão sob a água com seus tanques de oxigênio.

Agora você vai desenvolver uma versão X dessas funções:

• borbulheX(v,n) e
• bubblesortX(v)

que possivelmente/provavelmente façam menos comparações entre seu elementos.

A ideia básica é que se sabemos que \(\mathtt{a \leq b}\) que \(\mathtt{b \leq c}\), então não precisamos comparar a e c para concluirmos que \(\mathtt{a \leq c}\). Essa ideia já foi usada em ordenação por inserção e ordenação por inserção binária para evitar comparações supérfluas. Ela será usada de formas mais sofisticadas por outros algoritmos. Fiquem ligada(o)s!

Tratemos uma função por vez.

22.4. BorbulheX

A função borbulheX(v,n) é semelhante a função borbulhe(v,n). A diferença crucial é que ela retorna também um índice u tal que os elementos da sublista de v[u:] já estão nas suas posições de direito na lista ordenada. Observar a animação acima pode ser esclarecedor.

def borbulheX(v, n):
    '''(list, int) -> int, int
    RECEBE uma lista v e um inteiro n.
    PERCORRE sequencialmente, do início até o fim, a lista v[0:n]
       desfazendo através de trocas todas as inversões encontradas
       ao logo do caminho.
    RETORNA o número de trocas realizadas durante o percurso e também
        RETORNA o maior índice de uma posição de v que foi alterada durante
        o percurso. Se nenhum posição de v é alterada a função deve retorna o
        par (0, 0).
    '''

Aqui estão alguns exemplos da execução de borbulheX() no IPython Shell.

In [4]: v = [7, 4, 11, 5, 3]
In [5]: t, u = borbulheX(v, 3)
In [6]: t # trocas
Out[6]: 1
In [7]: u # índice
Out[7]: 1
In [8]: v
Out[8]: [4, 7, 11, 5, 3]

In [9]: v = [7, 4, 11, 5, 3]
In [10]: t, u = borbulheX(v, 4)
In [11]: t # trocas
Out[11]: 2
In [12]: u # índice
Out[12]: 3
In [13]: v
Out[13]: [4, 7, 5, 11, 3]

In [18]: v = [7, 4, 11, 5, 3]
In [19]: t, u = borbulheX(v, 5)
In [20]: t # trocas
Out[20]: 3
In [21]: u # índice
Out[21]: 4
In [22]: v
Out[22]: [4, 7, 5, 3, 11]

22.5. BubblesortX

A especificação desta função é muito semelhante a da sua função irmãzinha que não tem o X no nome. Além do número de trocas, a função bubblesortX() também retorna o número de comparações entre posições vizinhas realizadas durante toda a ordenação.

A função bublesortX() fará repetidas chamadas à função borbulheX() até que a lista v seja crescente. A fim de evitar que comparações desnecessárias entre elementos da lista v sejam feitas, bubblesortX() deverá utilizar o índice retornado por borbulheX(). Em caso de necessidade, busquem inspiração examinando o comportamento da função bubblesort() e as comparações claramente desnecessárias que ela faz considerando, por exemplo, que a lista v já é crescente logo de início.

def bubblesortX(v):
    '''(list) -> int, int
    RECEBE uma lista v.
    REARRANJA os elementos de v para que fique crescente.
    RETORNA o número de trocas e RETORNA o número de comparações
        feitas durante o processo.
    '''

Alguns exemplos da execução de bubblesortX() no IPython Shell.

In [24]: v = [7, 4, 11, 5, 3]
In [25]: t, c = bubblesortX(v)
In [26]: t # trocas
Out[26]: 7
In [27]: c # comparações
Out[27]: 10
In [28]: v
Out[28]: [3, 4, 5, 7, 11]

In [29]: v = [5, 3, 11, 4, 7]
In [30]: t, c = bubblesortX(v)
In [31]: t # trocas
Out[31]: 4
In [32]: c # comparações
Out[32]: 8
In [33]: v
Out[33]: [3, 4, 5, 7, 11]

In [34]: v = [5, 3, 4, 7, 11]
In [35]: t, c = bubblesortX(v)
In [36]: t # trocas
Out[36]: 2
In [37]: c # comparações
Out[37]: 5
In [38]: v
Out[38]: [3, 4, 5, 7, 11]

Se for conveniente você pode escrever e testar suas funções borbulheX() e bubblesortX() na janela a seguir.

22.6. Borbulhe de luxe

Aplicaremos a ideia da função borbulheX() em dose dupla percorrendo a lista da esquerda para a direita e da direita para a esquerda.

Chamaremos a nova versão da função responsável pelo borbublhamento de borbulhe_de_luxe(). Essa nova versão recebe, além da lista v, três inteiros e e d e passo em que e \(\leq\) d e passo é +1 ou -1. Os inteiros e e d indicam que v[e:d] e sublista de interesse da lista v. O inteiro passo diz a direção que v[e:d] deve ser percorrida.

A função borbulhe_de_luxe() deve percorrer sequencialmente a lista v. Se passo for +1 o percurso deve ser da posição de índice e até a posição de índice d. Já se passo for -1 o percurso deve ser da posição de índice d-1 até a posição de índice e.

Durante o percurso a função procura inversões entre posições vizinhas v[j] e v[j-1] para todo j, e < j < d. Se uma inversão for encontrada ela deve ser desfeita por meio de uma troca de valores.

A função retorna o número de trocas e retorna o índice de uma posição de v[e:d] que foi alterada durante o percurso. Se passo for +1 o índice deve ser o maior dentre os alterados e se passo for -1 o índice deve ser o menor. Se nenhuma posição de v for alterada a função retorna o par (0,e) quando passo é +1 e retorna o par (0,d) quando passo é -1.

Para fazer essa função busque inspiração na função borbulheX(). Notem que borbulhe_de_luxe(v,0,n,1) faz exatamente o mesmo serviço que borbubleX(v,n) e, a partir dessa observação, escreva borbulhe_de_luxe().

Uma especificação mais compacta de borbulhe_de_luxe() é a seguinte.

def borbulhe_de_luxe(v, e, d, passo):
    '''(list, int, int, int) -> int, int
    RECEBE uma lista v e três inteiros e e d e passo em que
        e <= d e passo é +1 ou -1.
    PERCORRE sequencialmente a sublista v[e:d] desfazendo através
       de trocas todas as inversões encontradas ao logo do caminho.
       Se passo é +1 o percurso é feito da esquerda para a direita.
       Se passo é -1 o percurso é feito da direita para a esquerda.
    RETORNA o número de trocas realizadas durante o percurso e também
        RETORNA o maior índice da última  posição de v que foi alterada durante
        o percurso. Se passo é +1 o índice deve ser o maior possível e
        se passo é -1 o índice deve ser o menor possível. Se nenhuma troca é
        realizada a função RETORNA (0, e) se passo é +1 e RETORNA  (0, d)
        se passo é -1.
    '''

Abaixo estão exemplos de execuções da função borbulhe_de_luxe().

In [7]: v = [7, 4, 11, 5, 3]
In [8]: t, u = borbulhe_de_luxe(v, e=0, d=3, passo=1) # vai para direita
In [9]: t # trocas
Out[9]: 1
In [10]: u # maior índice de posição alterada
Out[10]: 1
In [11]: v
Out[11]: [4, 7, 11, 5, 3]

In [13]: v = [7, 4, 11, 5, 3]
In [14]: t, u = borbulhe_de_luxe(v, e=0, d=4, passo=1) # vai para direita
In [15]: t # trocas
Out[15]: 2
In [16]: u # maior índice de posição alterada
Out[16]: 3
In [17]: v
Out[17]: [4, 7, 5, 11, 3]

In [18]: v = [7, 4, 11, 5, 3]
In [19]: t, u = borbulhe_de_luxe(v, e=0, d=5, passo=1) # vai para direita
In [20]: t # trocas
Out[20]: 3
In [21]: u # maior índice de posição alterada
Out[21]: 4
In [22]: v
Out[22]: [4, 7, 5, 3, 11]

In [23]: v = [7, 4, 11, 5, 3]
In [24]: t, u = borbulhe_de_luxe(v, e=0, d=3, passo=-1) # vai para esquerda
In [25]: t # trocas
Out[25]: 1
In [26]: u # menor índice de posição alterada
Out[26]: 0
In [27]: v
Out[27]: [4, 7, 11, 5, 3]

In [32]: v = [7, 4, 11, 5, 3]
In [33]: t, u = borbulhe_de_luxe(v, e=0, d=5, passo=-1) # vai para esquerda
In [34]: t # trocas
Out[34]: 4
In [35]: u # menor índice de posição alterada
Out[35]: 0
In [36]: v
Out[36]: [3, 7, 4, 11, 5]

In [37]: v = [7, 4, 11, 5, 3]
In [38]: t, u = borbulhe_de_luxe(v, e=1, d=5, passo=-1) # vai para esquerda
In [39]: t # trocas
Out[39]: 3
In [40]: u
Out[40]: 1
In [41]: v
Out[41]: [7, 3, 4, 11, 5]

22.7. Shakersort

A função ordene por borbulhagem de luxe que você escreverá é chamada nas redes sociais de Shaker sort. A animação a seguir ilustra o seu comportamento

A especificação da função é a seguinte:

def shakersort(v):
    '''(list) -> int, int
    RECEBE uma lista v.
    REARRANJA os elementos de v para que  v seja crescente
    '''

A função shakersort() deve chamar repetidamente a função borbulhe_de_luxe() sobre a lista v até que esta seja crescente. A função retorna o número total de trocas e retorna o número total de comparações realizadas durante o processo de ordenação. Os valores retornados por borbulhe_de_luxe() e os seus parâmetros e, d e passo são manipulados para possivelmente evitar comparações desnecessárias entre posições vizinhas de v.

Em caso de necessidade, procure inspiração na função ordene_por_borbulhagemX() e na animação acima.

Os exemplos a seguir mostram algumas execuções da função no IPython Shell.

In [41]: v = [7, 4, 11, 5, 3]
In [42]: t, c = shakersort(v)
In [43]: t
Out[43]: 7
In [44]: c
Out[44]: 12
In [45]: v
Out[45]: [3, 4, 5, 7, 11]

In [46]: v = [5, 3, 11, 4, 7]
In [47]: t, c = shakersort(v)
In [48]: t
Out[48]: 4
In [49]: c
Out[49]: 8
In [50]: v
Out[50]: [3, 4, 5, 7, 11]

In [51]: v = [5, 3, 4, 7, 11]
In [52]: t, c = shakersort(v)
In [53]: t
Out[53]: 2
In [54]: c
Out[54]: 6
In [55]: v
Out[55]: [3, 4, 5, 7, 11]

In [65]: v = [7, 1, 5, 2, 9, 6, 0, 4, 3, 8]
In [66]: a = v[:] # a é clone de v
In [67]: b = v[:] # b é clone de v
In [68]: t, c = ordene_por_borbulhagemX(a)
In [69]: t # trocas
Out[69]: 22
In [70]: c # comparações
Out[70]: 35

In [71]: t, c = shakersort(b)
In [72]: t
Out[72]: 22
In [73]: c # comparações
Out[73]: 32
In [74]: a
Out[74]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In [75]: b
Out[75]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
'''

Se for conveniente você pode escrever e testar suas funções borbulhe_de_luxe() e shakersort() na janela a seguir.

22.8. Lições

Para evitar comparações desnecessárias as funções feitas utilizaram algumas ideias.

• a contagem do número de trocas faz com a ordenação pare assim que a lista está ordenada.
• ao retornar o índice da última troca as funções da família borbulheX() nos dizem que a partir daquele índice não há mais nada a ser feito.

É claro é que toda essa contabilidade vem com um custo. Boas intenções podem produzir, para alguns casos, funções mais lentas.

22.9. Exercícios

1. Suponha que uma função que fazendo \(400n\) operações resolve em 1 segundo um problema de tamanho \(n=2500\). Qual o tamanho do problema que a função resolve em 1 minuto?
2. Qual é o número de trocas e de comparações entre pares vizinhos são feitas por bubblesort() para ordenar as listas:
   • [1, 2, 3, 4, 5]?
   • [5, 4, 3, 2, 1]?
   • [1, 3, 2, 4, 5]?
3. Se uma lista v tem n elementos, qual é o consumo de tempo da função bubblesort() no melhor caso (= a função trabalha pouco) e no pior caso (= a função se mata de trabalhar)? \(\mathtt{\textup{O}(1)}\)? \(\mathtt{\textup{O}(\lg n)}\)? \(\mathtt{\textup{O}(n \lg n)}\)? \(\mathtt{\textup{O}(n^2)}\)? \(\mathtt{\textup{O}(n^3)}\)? \(\mathtt{\textup{O}(2^n)}\)?
4. Se uma lista v tem n elementos, qual é o consumo de tempo da função bubblesortX() no melhor caso (= a função trabalha pouco) e no pior caso (= a função se mata de trabalhar)? \(\mathtt{\textup{O}(1)}\)? \(\mathtt{\textup{O}(\lg n)}\)? \(\mathtt{\textup{O}(n \lg n)}\)? \(\mathtt{\textup{O}(n^2)}\)? \(\mathtt{\textup{O}(n^3)}\)? \(\mathtt{\textup{O}(2^n)}\)?
5. Se uma lista v tem n elementos, qual é o consumo de tempo da função shakersort() no melhor caso (= a função trabalha pouco) e no pior caso (= a função se mata de trabalhar)? \(\mathtt{\textup{O}(1)}\)? \(\mathtt{\textup{O}(\lg n)}\)? \(\mathtt{\textup{O}(n \lg n)}\)? \(\mathtt{\textup{O}(n^2)}\)? \(\mathtt{\textup{O}(n^3)}\)? \(\mathtt{\textup{O}(2^n)}\)?
6. Dentre as funções bubblesort(), bubblesortX() e shakersort() qual tem o melhor desempenho para listas aleatórias?
7. Dentre as funções bubblesort(), bubblesortX() e shakersort() qual tem o melhor desempenho para listas crescentes? E para lista quase crescentes que são aquelas que têm poucos elemento fora de suas posição correta?
8. Dentre as funções bubblesort(), bubblesortX() e shakersort() qual tem o melhor desempenho para listas decrescentes? E para lista quase decrescentes que são aquelas que têm poucos elemento fora de suas posição correta?

22.10. Para saber mais

• Ordenação: algoritmos elementares de Projeto de Algoritmos de Paulo Feofiloff.
• O Bubble Sort de Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python de Brad Miller e David Ranum.
• Analysis of Algorithms de Introduction to Programming in Python. de Robert Sedgewick, Kevin Wayne e Robert Dondero.