.. -*- coding: utf-8 -*- 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. .. image:: ./imgs/BubbleSort.* :width: 420 :height: 132 :scale: 100 :alt: Sorting Algorithms - Design and Analysis of Algorithms :align: center :target: https://classic.csunplugged.org/activities/sorting-algorithms/ 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. .. image:: ./imgs/330px-Bubblesort-edited-color.svg.* :width: 330 :height: 275 :scale: 100 :alt: By Pmdumuid - Own work, CC0 :align: center :target: https://commons.wikimedia.org/w/index.php?curid=22164241 Borbulhamento ------------- O problema que continuaremos a tratar é o de ordenar uma lista de elementos. Dizemos que uma lista :math:`\mathtt{v[0:n]}` é **crescente** se .. math:: \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. .. image:: ./imgs/ordenacao.* :width: 810 :height: 384 :scale: 50 :alt: Instância de ordenação :align: center 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. .. image:: ./imgs/Bubble-sort-example-300px.* :width: 300 :height: 180 :scale: 100 :alt: By Swfung8 - Own work, CC BY-SA 3.0, :align: center :target: https://commons.wikimedia.org/w/index.php?curid=14953478 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. .. code:: python 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. .. code:: python 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. .. math:: \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} 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 :math:`\mathtt{n-1}` e o número de execuções da linha 4 será também :math:`\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 :math:`\mathtt{n = \textup{O}(n)}`. **Conclusão**. O consumo de tempo da função ``borbulhe(v, n)`` em todos os casos é proporcional a :math:`\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. 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. .. code:: python 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. .. image:: ./imgs/Sorting_bubblesort_anim.* :width: 277 :height: 257 :scale: 100 :alt: By Simpsons contributor - Own work, CC BY-SA 3.0, :align: center :target: https://commons.wikimedia.org/w/index.php?curid=14827645 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 :math:`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 :math:`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. .. math:: \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} Independentemente dos elementos na lista o consumo de tempo do ``bubblesort()`` é quadrático, ou seja, proporcional a :math:`\mathtt{n^2=\textup{O}(n^2)}`. **Conclusão**. O consumo de tempo da função ``bubblesort()`` em todos os casos é proporcional a :math:`\mathtt{n^2 = \textup{O}(n^2)}`, onde :math:`\mathtt{n}` é o número de elementos na lista ``v``. .. math:: \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} 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 :math:`\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 :math:`\mathtt{a \leq b}` que :math:`\mathtt{b \leq c}`, então não precisamos comparar ``a`` e ``c`` para concluirmos que :math:`\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. 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. .. code:: python 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. .. code:: python 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] 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. .. code:: python 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. .. code:: python 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. .. raw:: html 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`` :math:`\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. .. code:: python 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()``. .. code:: python 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] 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 .. image:: ./imgs/Sorting_shaker_sort_anim.* :width: 277 :height: 257 :scale: 100 :alt: By Simpsons contributor - Own work, CC BY-SA 3.0 :align: center :target: https://commons.wikimedia.org/w/index.php?curid=14828123 A especificação da função é a seguinte: .. code:: 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. .. code:: 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. .. raw:: html 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. Exercícios ---------- #. Suponha que uma função que fazendo :math:`400n` operações resolve em 1 segundo um *problema de tamanho* :math:`n=2500`. Qual o tamanho do problema que a função resolve em 1 minuto? #. 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]? #. 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)? :math:`\mathtt{\textup{O}(1)}`? :math:`\mathtt{\textup{O}(\lg n)}`? :math:`\mathtt{\textup{O}(n \lg n)}`? :math:`\mathtt{\textup{O}(n^2)}`? :math:`\mathtt{\textup{O}(n^3)}`? :math:`\mathtt{\textup{O}(2^n)}`? #. 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)? :math:`\mathtt{\textup{O}(1)}`? :math:`\mathtt{\textup{O}(\lg n)}`? :math:`\mathtt{\textup{O}(n \lg n)}`? :math:`\mathtt{\textup{O}(n^2)}`? :math:`\mathtt{\textup{O}(n^3)}`? :math:`\mathtt{\textup{O}(2^n)}`? #. 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)? :math:`\mathtt{\textup{O}(1)}`? :math:`\mathtt{\textup{O}(\lg n)}`? :math:`\mathtt{\textup{O}(n \lg n)}`? :math:`\mathtt{\textup{O}(n^2)}`? :math:`\mathtt{\textup{O}(n^3)}`? :math:`\mathtt{\textup{O}(2^n)}`? #. Dentre as funções ``bubblesort()``, ``bubblesortX()`` e ``shakersort()`` qual tem o melhor desempenho para listas aleatórias? #. 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? #. 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? 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.