16.Divisão e Conquista.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "toc": true
   },
   "source": [
    "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#Divisão-e-Conquista\" data-toc-modified-id=\"Divisão-e-Conquista-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Divisão e Conquista</a></span><ul class=\"toc-item\"><li><span><a href=\"#Quick-Sort\" data-toc-modified-id=\"Quick-Sort-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Quick Sort</a></span><ul class=\"toc-item\"><li><span><a href=\"#Análise-de-Complexidade\" data-toc-modified-id=\"Análise-de-Complexidade-1.1.1\"><span class=\"toc-item-num\">1.1.1&nbsp;&nbsp;</span>Análise de Complexidade</a></span></li><li><span><a href=\"#Algoritmo-Recursivo\" data-toc-modified-id=\"Algoritmo-Recursivo-1.1.2\"><span class=\"toc-item-num\">1.1.2&nbsp;&nbsp;</span>Algoritmo Recursivo</a></span></li><li><span><a href=\"#Algoritmo-usando-compreensão-de-listas\" data-toc-modified-id=\"Algoritmo-usando-compreensão-de-listas-1.1.3\"><span class=\"toc-item-num\">1.1.3&nbsp;&nbsp;</span>Algoritmo usando compreensão de listas</a></span></li><li><span><a href=\"#Exercícios\" data-toc-modified-id=\"Exercícios-1.1.4\"><span class=\"toc-item-num\">1.1.4&nbsp;&nbsp;</span>Exercícios</a></span></li></ul></li><li><span><a href=\"#Merge-Sort\" data-toc-modified-id=\"Merge-Sort-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Merge Sort</a></span><ul class=\"toc-item\"><li><span><a href=\"#Algoritmo\" data-toc-modified-id=\"Algoritmo-1.2.1\"><span class=\"toc-item-num\">1.2.1&nbsp;&nbsp;</span>Algoritmo</a></span></li><li><span><a href=\"#Análise-de-Complexidade\" data-toc-modified-id=\"Análise-de-Complexidade-1.2.2\"><span class=\"toc-item-num\">1.2.2&nbsp;&nbsp;</span>Análise de Complexidade</a></span></li><li><span><a href=\"#Exercícios\" data-toc-modified-id=\"Exercícios-1.2.3\"><span class=\"toc-item-num\">1.2.3&nbsp;&nbsp;</span>Exercícios</a></span></li><li><span><a href=\"#Solução-alternativa-para-o-Merge-sort\" data-toc-modified-id=\"Solução-alternativa-para-o-Merge-sort-1.2.4\"><span class=\"toc-item-num\">1.2.4&nbsp;&nbsp;</span>Solução alternativa para o Merge sort</a></span></li><li><span><a href=\"#Exercícios\" data-toc-modified-id=\"Exercícios-1.2.5\"><span class=\"toc-item-num\">1.2.5&nbsp;&nbsp;</span>Exercícios</a></span></li></ul></li></ul></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Divisão e Conquista"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Os algoritmos de classificação que estudamos têm tempos de execução $\\large{O}$\n",
    "($n^2$). Existem várias variações nesses algoritmos de classificação, alguns\n",
    "dos quais são marginalmente mais rápidos, mas eles também são $\\large{O}$\n",
    "($n^2$) nos casos médios e piores. Hoje iremos estudar alguns algoritmos\n",
    "melhores que são $\\large{O}$ ($n log_{2} n$). O segredo para esses melhores\n",
    "algoritmos é o uso da estratégia de divisão e conquista que\n",
    "empregamos, por exemplo, na busca binária. Ou seja, cada algoritmo encontra uma maneira de\n",
    "quebrar a lista em sublistas menores. Essas sublistas são então ordenadas\n",
    "recursivamente. Idealmente, se o número dessas subdivisões é $log_{2} (n)$ e a\n",
    "quantidade de trabalho necessário para reorganizar os dados em cada subdivisão\n",
    "é $n$, então a complexidade total de tal algoritmo de ordenação é $\\large{O}$\n",
    "($n log_{2} n$). Na tabela a seguir, você pode ver que a taxa de crescimento do\n",
    "trabalho de um algoritmo $\\large{O}$ ($n log_{2} n$) é muito mais lenta que a\n",
    "de um algoritmo $\\large{O}$ ($n^2$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "|$n$ |$n Log_{2} n$| $n^2$|\n",
    "| :--: | :--: | :--: |\n",
    "|512 |4,608| 262,144|\n",
    "|1,024| 10,240 |1,048,576|\n",
    "|2,048| 22,458| 4,194,304|\n",
    "|8,192| 106,496| 67,108,864|\n",
    "|16,384| 229,376| 268,435,456|\n",
    "|32,768| 491,520| 1,073,741,824|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Recapitulando, a estratégia de Divisão e Conquista pode ser feito em três amplos passos:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- Dividir:\n",
    "O passo de divisão quebra o problema original em subproblemas que são instâncias menores do problema original.\n",
    "\n",
    "- Conquistar:\n",
    "O passo de conquistar resolve os subproblemas de forma recursiva. No passo recursivo, os subproblemas são resolvidos, até o caso base, que é o ponto em que o problema não pode ser mais dividido.\n",
    "\n",
    "- Combinar:\n",
    "Neste passo, combina-s os subproblemas resolvidos para resolver o problema original."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Quick Sort\n",
    "\n",
    "Vamos começar estudando um esboço da estratégia de Divisão e Conquista utilizada no algoritmo conhecido como quicksort:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Comece selecionando o item no ponto médio da lista. Chamamos esse item de pivô. (Mais tarde, discutiremos maneiras alternativas de escolher o pivô).\n",
    "\n",
    "- Particione os itens na lista para que todos os itens inferiores ao pivô fiquem à esquerda do pivô, e o resto, à sua direita. A posição final do próprio pivô varia, dependendo dos itens reais envolvidos. Mas onde quer que o pivô termine, essa é a sua posição final na lista totalmente ordenada.\n",
    "\n",
    "- Dividir e conquistar. Reaplicar o processo de forma recursiva às sublistas formadas pela divisão da lista no pivô. Uma sublista consiste em todos os itens à esquerda do pivô (agora os menores itens que o pivô) e a outra sublista tem todos os itens à direita (agora os maiores).\n",
    "\n",
    "- O processo termina toda vez que encontramos uma sublista com menos de dois itens."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Vejamos uma animação da aplicação do algoritmo:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<video controls src=\"videos/quick.mp4\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A parte mais complicada do algoritmo é a operação de partição dos itens em uma sublista. Existem duas maneiras principais de fazer isso. Informalmente, o que se segue é uma descrição do método mais fácil, pois se aplica a qualquer sublista:\n",
    "\n",
    "1. Troque o pivô com o último item na sublista.\n",
    "\n",
    "2. Estabeleça um limite entre os itens que são conhecidos como inferiores ao pivô e ao resto dos itens. Inicialmente, esse limite é posicionado imediatamente antes do primeiro item.\n",
    "\n",
    "3. Iniciando com o primeiro item na sublista, explore a sublista. Toda vez que um item menor que o pivô é encontrado, troque-o com o primeiro item após o limite e avance o limite.\n",
    "\n",
    "4. Termine, trocando o pivô com o primeiro item após o limite."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Depois que uma sublista foi particionada, reaplicamos o processo às suas sublistas à esquerda e à direita e assim por diante, até que as sublistas tenham um comprimento de um."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Análise de Complexidade"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Apresentamos agora uma análise informal da complexidade do Quick Sort. Durante a primeira operação de partição, examinamos todos os itens desde o início da lista até o fim. Assim, a quantidade de trabalho durante esta operação é proporcional a $n$, o comprimento da lista.\n",
    "A quantidade de trabalho após esta partição é proporcional ao comprimento da sublista à esquerda mais o comprimento da sublistra à direita, que em conjunto produzem $n-1$. E quando essas sublistas são divididas, existem quatro partes cujo comprimento combinado é aproximadamente $n$, então o trabalho combinado é proporcional a $n$ novamente. Como a lista é dividida em mais partes, o trabalho total permanece proporcional a $n$.\n",
    "Para completar a análise, precisamos determinar quantas vezes as listas são particionadas. Vamos fazer a suposição otimista de que, cada vez, a linha divisória entre as novas sublistas se torna tão próxima do centro da sublista atual quanto possível. Na prática, este não é geralmente o caso. Você já sabe, a partir da discussão do algoritmo de busca binária, que quando você divide uma lista pela metade repetidamente, você chega a um único elemento nas etapas em $log_{2} n$. Assim, o algoritmo é $\\large{O}$ ($n log_{2} n$) no melhor caso."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Para o desempenho do pior caso, considere o caso de uma lista que já está ordenada. Se o elemento de pivô escolhido for o primeiro elemento, então, há $n-1$ elementos à direita na primeira partição, $n-2$ elementos à direita na segunda partição, e assim por diante. Embora nenhum elemento seja trocado, o número total de partições é $n-1$ e o número total de comparações realizadas é $1/2 n^2 - 1/2 n$, o mesmo número no Selection Sort e no Bubble Sort. Assim, no pior caso, o algoritmo Quick Sort é $\\large{O}$ ($n^2$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Se Quick Sort for implementado como um algoritmo recursivo, a análise também deve considerar o uso de memória para a pilha de chamadas. Cada chamada recursiva requer uma quantidade constante de memória para um frame da pilha, e há duas chamadas recursivas após cada partição. Assim, o uso de memória é $\\large{O}$ ($log_{2} n$) no melhor caso e $\\large{O}$ ($n$) no pior dos casos.\n",
    "Embora o desempenho do pior caso do Quick Sort seja raro, os programadores certamente preferem evitá-lo. Escolher o pivô na primeira ou última posição não é uma estratégia sábia. Outros métodos de escolha do pivô, como selecionar uma posição aleatória ou escolher a mediana dos primeiros, médios e últimos elementos, podem ajudar a aproximar o desempenho para $\\large{O}$ ($n log_{2} n$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Algoritmo Recursivo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def quicksort(lst):\n",
    "    quicksortHelper(lst, 0, len(lst) - 1)\n",
    "    \n",
    "def quicksortHelper(lst, left, right):\n",
    "    if left < right:\n",
    "        pivotLocation = partition(lst, left, right)\n",
    "        quicksortHelper(lst, left, pivotLocation - 1)\n",
    "        quicksortHelper(lst, pivotLocation + 1, right)\n",
    "    \n",
    "def partition(lst, left, right):\n",
    "    # Find the pivot and exchange it with the last item\n",
    "    middle = (left + right) // 2\n",
    "    pivot = lst[middle]\n",
    "    lst[middle] = lst[right]\n",
    "    lst[right] = pivot\n",
    "    # Set boundary point to first position\n",
    "    boundary = left\n",
    "    # Move items less than pivot to the left\n",
    "    for index in range(left, right):\n",
    "        if lst[index] < pivot:\n",
    "            lst[index], lst[boundary] = lst[boundary], lst[index]\n",
    "            boundary += 1\n",
    "    # Exchange the pivot item and the boundary item\n",
    "    lst[boundary], lst[right] = lst[right], lst[boundary]\n",
    "    return boundary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "lst = [12, 90, 47, -9, 78, 45, 78, 3323, 1, 2, 34, 20]\n",
    "quicksort(lst)\n",
    "print(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "lst = []\n",
    "for count in range(500000):\n",
    "    lst.append(randint(1, 500000))\n",
    "%time quicksort(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Algoritmo usando compreensão de listas"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def qsort(v):\n",
    "    if v == []:\n",
    "        return []\n",
    "    p = v[0]\n",
    "    return qsort([x for x in v[1:] if x < p]) + [p] + qsort([x for x in v[1:] if x >= p])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "lst = []\n",
    "for count in range(500000):\n",
    "    lst.append(randint(1, 500000))\n",
    "%time res = qsort(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Ou ainda:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def qsort2(L):\n",
    "    return (qsort2([y for y in L[1:] if y <  L[0]]) + L[:1] + \n",
    "            qsort2([y for y in L[1:] if y >= L[0]])) if len(L) > 1 else L"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exercícios\n",
    "\n",
    "1. Aplique o algoritmo de particionamento sobre o vetor [13, 19, 9, 5, 12, 21, 7, 4, 11, 2, 6, 6] com pivô igual a 6.\n",
    "\n",
    "2. Qual o valor retornado pelo algoritmo de particionamento se todos os elementos do vetor tiverem valores iguais?\n",
    "\n",
    "3.  Faça uma execução passo-a-passo do Quick Sort com o vetor [4, 3, 6, 7, 9, 10, 5, 8].\n",
    "\n",
    "4. Modifique o algoritmo Quick Sort para ordenar vetores em ordem decrescente."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Merge Sort\n",
    "\n",
    "Outro algoritmo, denominado Merge Sort, emprega também uma estratégia recursiva, de\n",
    "divisão e conquista, para quebrar a barreira $\\large{O}$ ($n^2$). Vejamos um\n",
    "resumo informal do algoritmo:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "- Calcule a posição do meio de uma lista e ordene recursivamente suas sublistas\n",
    "  da esquerda e direita (dividir e conquistar).\n",
    "- Junte as duas sublistas ordenadas novamente em uma única lista ordenada (mesclagem ou merge).\n",
    "- Pare o processo quando as sublistas não puderem mais ser subdivididas.\n",
    "\n",
    "O processo de mesclagem, também conhecido por ordenação por intercalação usa\n",
    "uma lista auxiliar do mesmo tamanho da lista. A ideia é executar um laço\n",
    "onde em cada iteração testamos quem é o menor elemento dentre as duas sublistas e\n",
    "copiamos este elemento para a nova lista.\n",
    "Durante a execução deste laço podemos chegar em uma situação onde todos os\n",
    "elementos de uma das sublistas foram todos avaliados. Neste caso terminamos o laço\n",
    "e copiamos os elementos restantes da outra sublista.\n",
    "Vamos chamar essa lista auxiliar de copyBuffer. Para evitar a sobrecarga de alocação e\n",
    "desalocação do copyBuffer sempre que a função Merge for chamada, o buffer é alocado uma\n",
    "única vez no mergeSort e passado como argumento para as funções auxiliares.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Vejamos uma animação da aplicação do algoritmo:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<video controls src=\"videos/merge.mp4\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Abaixo temos um exemplo com a ordem de execução das chamadas recursivas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<img src=\"img/merge1.png\" alt=\"Drawing\" style=\"width: 800px;\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Abaixo temos o retorno do exemplo anterior."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<img src=\"img/merge2.png\" alt=\"Drawing\" style=\"width: 800px;\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Algoritmo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Três funções do Python colaboram no design do algoritmo:\n",
    "\n",
    "- MergeSort: A função chamada pelos usuários.\n",
    "- MergeSortHelper: A função auxiliar que esconde os parâmetros extras requeridos nas chamadas recursivas.\n",
    "- Merge: A função que implementa o processo de mesclagem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def mergeSort(lst):\n",
    "    # lst         list being sorted\n",
    "    # copyBuffer  temporary space needed during merge\n",
    "    copyBuffer = [0 for i in range(len(lst))]\n",
    "    mergeSortHelper(lst, copyBuffer, 0, len(lst) - 1)\n",
    "    \n",
    "def mergeSortHelper(lst, copyBuffer, low, high):\n",
    "    # lst         list being sorted\n",
    "    # copyBuffer  temp space needed during merge\n",
    "    # low, high   bounds of sublist\n",
    "    # middle      midpoint of sublist\n",
    "    if low < high:\n",
    "        middle = (low + high) // 2\n",
    "        mergeSortHelper(lst, copyBuffer, low, middle)\n",
    "        mergeSortHelper(lst, copyBuffer, middle + 1, high)\n",
    "        merge(lst, copyBuffer, low, middle, high)\n",
    "        \n",
    "def merge(lst, copyBuffer, low, middle, high):\n",
    "    # lst         list that is being sorted\n",
    "    # copyBuffer  temp space needed during the merge process\n",
    "    # low         beginning of first sorted sublist\n",
    "    # middle      end of first sorted sublist\n",
    "    # middle + 1  beginning of second sorted sublist\n",
    "    # high        end of second sorted sublist\n",
    "    \n",
    "    # Initialize i1 and i2 to the first items in each sublist\n",
    "    i1 = low\n",
    "    i2 = middle + 1\n",
    "    # Interleave items from the sublists into the\n",
    "    # copyBuffer in such a way that order is maintained.\n",
    "    for i in range(low, high + 1):\n",
    "        if i1 > middle:\n",
    "            copyBuffer[i] = lst[i2] # First sublist exhausted\n",
    "            i2 += 1\n",
    "        elif i2 > high:\n",
    "            copyBuffer[i] = lst[i1] # Second sublist exhausted\n",
    "            i1 += 1\n",
    "        elif lst[i1] < lst[i2]:\n",
    "            copyBuffer[i] = lst[i1] # Item in first sublist is \"<\"\n",
    "            i1 += 1\n",
    "        else:\n",
    "            copyBuffer[i] = lst[i2] # Item in second sublist is \"<\"\n",
    "            i2 += 1\n",
    "    for i in range(low, high + 1):  # Copy sorted items back to\n",
    "        lst[i] = copyBuffer[i]      # proper position in lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "lst = [12, 90, 47, -9, 78, 45, 78, 3323, 1, 2, 34, 20]\n",
    "mergeSort(lst)\n",
    "print(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "lst = []\n",
    "for count in range(500000):\n",
    "    lst.append(randint(1, 500000))\n",
    "%time mergeSort(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A função de mesclagem combina duas sublistas ordenadas em uma sub-lista\n",
    "ordenada maior. A primeira sublista situa-se entre $low$ e $middle$ e a segunda entre o $middle + 1$ e $high$. O processo consiste em três etapas:\n",
    "\n",
    "1. Configure os ponteiros de índice para os primeiros itens em cada sublista.\n",
    "Estes estão em posições $low$ e $middle + 1$.\n",
    "\n",
    "2. Iniciando com o primeiro item em cada sublista, compare os itens repetidamente.\n",
    "Copie o item menor de sua sublista para o buffer de cópia e avance para o\n",
    "próximo item na sublist. Repita até que todos os itens tenham sido copiados de\n",
    "ambas as sublistas. Se o final de uma sublista for atingido antes do outro,\n",
    "termine copiando os itens restantes da outra sublista.\n",
    "\n",
    "3. Copie a parte do copyBuffer entre as parte $low$ e $high$ para as posições\n",
    "correspondentes em lst."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Análise de Complexidade"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "O tempo de execução da função de mesclagem é dominado pelas duas instruções, cada uma das quais ($high - low + 1$) vezes. Conseqüentemente, o tempo de execução da função é $\\large{O}$ ($high-low$), e todas os merges em um único nível levam o tempo $\\large{O}$ ($n$). Como mergeSortHelper divide as sublistas o mais uniformemente possível em cada nível, o número de níveis é $\\large{O}$ ($log_{2} n$) e o tempo máximo de execução dessa função é $\\large{O}$ ($n log_{2} n$) em todos os casos.\n",
    "O merge possui dois requisitos de espaço que dependem do tamanho da lista. Primeiro, o espaço de $\\large{O}$ ($log_{2} n$) é necessário na pilha de chamadas para suportar chamadas recursivas. Segundo, o espaço $\\large{O}$ ($n$) é usado pelo buffer de cópia."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exercícios"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "a. Mostre passo a passo a execução da função Merge considerando duas sub-listas:\n",
    "\n",
    "    [3, 5, 7, 10, 11, 12]  e   [4, 6, 8, 9, 11, 13, 14].\n",
    "    \n",
    "\n",
    "b. Faça uma execução Passo-a-Passo do MergeSort para a lista:\n",
    "\n",
    "    [30, 45, 21, 20, 6, 715, 100, 65, 33].\n",
    "    \n",
    "\n",
    "c. Reescreva o algoritmo MergeSort para que este passe a ordenar um vetor em ordem decrescente.\n",
    "\n",
    "\n",
    "d. Considere o seguinte problema: Temos como entrada uma lista de inteiros $lst$ (não necessariamente ordenada), e um inteiro $x$. Desenvolva um algoritmo que determina se há dois números em $lst$ cuja soma seja $x$. Tente fazer o algoritmo o mais eficiente possível. Utilize um dos algoritmos de ordenação na sua solução."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solução alternativa para o Merge sort \n",
    "\n",
    "Esta solução alternativa não cria explicitamente uma lista auxiliar para o processo de mesclagem, porém ele retorna a lista ordenada. De qualquer forma você acaba tendo uma cópia da lista. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(left, right):\n",
    "    \"\"\"Merge sort merging function.\"\"\"\n",
    "\n",
    "    left_index, right_index = 0, 0\n",
    "    result = []\n",
    "    while left_index < len(left) and right_index < len(right):\n",
    "        if left[left_index] < right[right_index]:\n",
    "            result.append(left[left_index])\n",
    "            left_index += 1\n",
    "        else:\n",
    "            result.append(right[right_index])\n",
    "            right_index += 1\n",
    "\n",
    "    result += left[left_index:]\n",
    "    result += right[right_index:]\n",
    "    return result\n",
    "\n",
    "\n",
    "def merge_sort(array):\n",
    "    if len(array) <= 1:  # base case\n",
    "        return array\n",
    "\n",
    "    # divide array in half and merge sort recursively\n",
    "    half = len(array) // 2\n",
    "    left = merge_sort(array[:half])\n",
    "    right = merge_sort(array[half:])\n",
    "\n",
    "    return merge(left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "lst = []\n",
    "for count in range(500000):\n",
    "    lst.append(randint(1, 500000))\n",
    "%time lst = merge_sort(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercícios"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Dado a seguinte lista de números:\n",
    "```\n",
    "[21, 1, 26, 45, 29, 28, 2, 9, 16, 49, 39, 27, 43, 34, 46, 40]\n",
    "```\n",
    "\n",
    "Qual resposta abaixo ilustra a lista a ser ordenada depois de 3 chamadas recursivas ao merge sort?\n",
    "\n",
    "(A) ```[16, 49, 39, 27, 43, 34, 46, 40]```\n",
    "\n",
    "(B) ```[21,1]```\n",
    "\n",
    "(C) ```[21, 1, 26, 45]```\n",
    "\n",
    "(D) ```[21]```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Dado a seguinte lista de números:\n",
    "```\n",
    "[21, 1, 26, 45, 29, 28, 2, 9, 16, 49, 39, 27, 43, 34, 46, 40]\n",
    "```\n",
    "\n",
    "Qual resposta abaixo ilustra as primeiras duas listas que serão mescladas no processo do merge sort?\n",
    "\n",
    "(A) ```[21, 1]``` and ```[26, 45]````\n",
    "\n",
    "(B) ```[[1, 2, 9, 21, 26, 28, 29, 45]``` and ```[16, 27, 34, 39, 40, 43, 46, 49]````\n",
    "\n",
    "(C) ```[21]``` and ```[1]````\n",
    "\n",
    "(D) ```[9]``` and ```[16]```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "livereveal": {
   "theme": "solarized",
   "transition": "slide"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}