12.Ordenação.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\" style=\"margin-top: 1em;\"><ul class=\"toc-item\"><li><span><a href=\"#Ordenação\" data-toc-modified-id=\"Ordenação-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Ordenação</a></span><ul class=\"toc-item\"><li><span><a href=\"#Selection-sort\" data-toc-modified-id=\"Selection-sort-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Selection sort</a></span></li><li><span><a href=\"#Bubble-sort\" data-toc-modified-id=\"Bubble-sort-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Bubble sort</a></span></li><li><span><a href=\"#Insertion-sort\" data-toc-modified-id=\"Insertion-sort-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Insertion sort</a></span></li></ul></li><li><span><a href=\"#Exercícios\" data-toc-modified-id=\"Exercícios-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Exercícios</a></span><ul class=\"toc-item\"><li><span><a href=\"#Ordem-Crescente\" data-toc-modified-id=\"Ordem-Crescente-2.1\"><span class=\"toc-item-num\">2.1&nbsp;&nbsp;</span>Ordem Crescente</a></span></li><li><span><a href=\"#Inserindo-Chave\" data-toc-modified-id=\"Inserindo-Chave-2.2\"><span class=\"toc-item-num\">2.2&nbsp;&nbsp;</span>Inserindo Chave</a></span></li><li><span><a href=\"#Insertion-Sort-Recursivo\" data-toc-modified-id=\"Insertion-Sort-Recursivo-2.3\"><span class=\"toc-item-num\">2.3&nbsp;&nbsp;</span>Insertion Sort Recursivo</a></span></li><li><span><a href=\"#Critique-a-seguinte-implementação-do-algoritmo-de-ordenação-por-inserção:\" data-toc-modified-id=\"Critique-a-seguinte-implementação-do-algoritmo-de-ordenação-por-inserção:-2.4\"><span class=\"toc-item-num\">2.4&nbsp;&nbsp;</span>Critique a seguinte implementação do algoritmo de ordenação por inserção:</a></span></li><li><span><a href=\"#Mediana\" data-toc-modified-id=\"Mediana-2.5\"><span class=\"toc-item-num\">2.5&nbsp;&nbsp;</span>Mediana</a></span></li></ul></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Ordenação"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Vamos estudar alguns algoritmos para o seguinte problema:\n",
    "\n",
    "- Dado uma coleção de elementos com uma relação de ordem entre si, devemos gerar uma saída com os elementos ordenados.\n",
    "\n",
    "Antes porém, vamos estabelecer (pelo menos um motivo) por que é útil ter dados que estão ordenados. Em suma, os dados ordenados tornam o processamento de dados muito mais rápido.\n",
    "\n",
    "Mas como medimos o que é \"rápido\" vs. o que é \"lento?\" A chave para analisar o tempo que um programa leva para executar é contar o número de operações que ele executará para um determinado tamanho de entrada. Os cientistas raramente se preocupam com algoritmos rápidos ou lentos para entradas muito pequenas: quase sempre são rápidos se a entrada for pequena. No entanto, ao processar grandes entradas (por exemplo, milhões de usuários que avaliam centenas ou mesmo milhares de dados), a velocidade torna-se crítica."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Vamos analisar quanto tempo leva para calcular o número de objetos iguais entre duas listas usando a função abaixo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def numMatches(list1, list2):\n",
    "    ''' return the number of elements that match between\n",
    "        list1 and list2 '''\n",
    "    count = 0\n",
    "    for item in list1:\n",
    "        if item in list2:\n",
    "            count += 1\n",
    "    return count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Para efeito de análise, vamos supor que as listas em questão tem comprimento 4, isto é, `len(list1) == len(list2) == 4`. Inicialmente, pegue o primeiro elemento da primeira lista e pergunte se este elemento está na segunda lista. O comando `in` é um pouco enganador porque esconde um número significativo de comparações. Como o Python verifica se um item está em uma lista? É necessário comparar esse item com cada item da lista! Então, neste caso, o primeiro item da primeira lista é comparado a cada item na segunda lista para determinar se está nessa lista ou não."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "\"Espere!\", Você diz. Se o item estiver realmente na lista, ele não precisa verificar os quatro itens, e pode parar de verificar quando ele encontra o item em questão. Isso é exatamente correto, mas na verdade não importa em nossa análise. Para uma análise como essa, os cientistas da computação são bastante pessimistas. Eles raramente se importam com o que acontece quando as coisas funcionam bem -- o que eles importam é o que pode acontecer no pior dos casos. Nesse caso, o pior caso é quando o item não está na lista e o Python tem que compará-lo com cada item da lista para determinar que o elemento não está lá. Uma vez que o que nos interessa é o comportamento do pior caso, realizaremos nossa análise como se estivéssemos lidando com o pior caso."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Então, de volta à análise: Para o primeiro item na lista, a Python fez quatro comparações aos itens na segunda lista -- comandos que foram escondidos no comando `in`. Agora, nosso programa passa para o segundo item na primeira lista, onde novamente faz quatro comparações com a segunda lista. Da mesma forma, faz quatro comparações para cada um dos terceiro e quarto elementos na primeira lista, o que nos leva a um total de $4 + 4 + 4 + 4 = 4 * 4 = 16$ comparações. Isso provavelmente não soa como um número tão ruim. Afinal, seu computador pode fazer 16 comparações em menos de um segundo. Mas e se nossas listas fossem mais longas? E se a lista1 tivesse $100$ elementos e a lista 2, $1000$ elementos (alto, mas não muito)? Isto posto, o sistema teria que fazer $1000$ comparações (para os itens na segunda lista) para cada um dos $100$ itens na primeira lista para um total de $100 * 1000 = 10^5$ comparações. Ainda não é enorme, mas espero que você possa ver onde isso está nos levando. Em geral, o algoritmo de \\textit{match}  que escrevemos acima leva $N * M$ comparações, onde $N$ é o tamanho da primeira lista e $M$ é o tamanho da segunda lista. Por simplicidade, podemos assumir que as duas listas sempre terão o mesmo comprimento, $N$, caso em que ele faz as $N^2$ comparações."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A boa notícia é que podemos fazer significativamente melhor, mas temos que fazer uma suposição sobre as próprias listas. E se nossas listas fossem ordenadas alfabeticamente? Como isso pode tornar nosso algoritmo de \\textit{match}  mais rápido? A resposta é que podemos manter as listas \"sincronizadas\", por assim dizer, e \"caminhar\" através de ambas as listas ao mesmo tempo, em vez de selecionar um único elemento da primeira lista e compará-lo com todos os elementos na segunda. Por exemplo, se as listas são compostas de strings (por exemplo, nomes de bandas) ordenados lexicograficamente e, se você está olhando para o primeiro elemento da primeira lista e este string é igual a \"Black Eyed Peas\" e o primeiro elemento da segunda lista é \"Counting Crows\", você sabe que o string \"Black Eyed Peas\" não aparecem na segunda lista , porque C é lexicograficamente maior que B. Então, você pode simplesmente descartar o \"Black Eyed Peas\" e passar para a próxima banda na primeira lista."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Veja como seria o algoritmo. Lembre-se que assumimos que as listas estão ordenadas. \n",
    "\n",
    "- Inicialize um contador em 0\n",
    "- Defina o item atual em cada lista para ser o primeiro item em cada lista\n",
    "- Repita o procedimento a seguir até chegar ao final de uma das duas listas:\n",
    " - Compare os itens atuais em cada lista.\n",
    " - Se forem iguais, incremente o contador e avance o item atual de ambas as listas para os próximos itens nas listas.\n",
    " - Caso contrário, se o item atual na primeira lista for alfabeticamente menor do que o item atual na segunda lista, avance o item atual na primeira lista.\n",
    " - Caso contrário, avance o item atual na segunda lista.\n",
    "- O contador detém o número de \\textit{matches}."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Antes de olhar para o código a seguir, pergunte a si mesmo: \"Que tipo de laço devo usar aqui? Um laço `for` ou `while`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Aqui está o código Python correspondente:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def numMatches(list1, list2):\n",
    "    '''return the number of elements that match between two sorted lists'''\n",
    "    matches = 0\n",
    "    i = 0\n",
    "    j = 0\n",
    "    while i < len(list1) and j < len(list2):\n",
    "        if list1[i] == list2[j]:\n",
    "            matches += 1\n",
    "            i += 1\n",
    "            j += 1\n",
    "        elif list1[i] < list2[j]:\n",
    "            i += 1\n",
    "        else:\n",
    "            j += 1\n",
    "    return matches\n",
    "\n",
    "\n",
    "print(numMatches(['a', 'l', 'i', 's', 'o', 'n'], ['a', 'k', 'h', 'i', 'l']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Agora, a questão permanece: esta abordagem é realmente mais rápida do que a abordagem anterior para comparar os elementos em duas listas? A resposta é definitivamente sim. Voltemos a olhar o número de comparações que deveriam ser feitas para comparar duas listas com 4 elementos cada. Imagine que nenhum dos elementos coincida e que as listas são exatamente entrelaçadas alfabeticamente. Ou seja, primeiro o elemento da lista 1 é menor, então o elemento na lista 2 é menor, e assim por diante, como nas listas [\"Amy Winehouse\", \"Coldplay\", \"Madonna\", \"Red Hot Chili Peppers\"] e [\"Black Eyed Peas\", \"Dave Matthews Band\", \"Maroon 5\", \"Stevie Nicks\"]\n",
    "\n",
    "Com estas duas listas, o código acima nunca irá disparar na primeira condição if -- sempre aumentará i ou j, mas não ambos. Além disso, ele ficará sem elementos em uma lista, logo antes de ficar sem elementos na segunda. Essencialmente, o algoritmo irá analisar todos os elementos em ambas as listas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "No começo, pode parecer que não fizemos nenhuma melhoria. Afinal, ainda não estamos olhando todos os elementos de ambas as listas? Aha, mas agora há uma diferença importante! Enquanto antes de ver todos os elementos da segunda lista para cada elemento na primeira lista, aqui estamos olhando apenas todos os elementos da segunda lista uma vez. Em outras palavras, cada vez que \"caminhamos\"no laço, i ou j é incrementado mas nunca são diminuídos. Então, i ou j irão chegar ao final da lista depois que todos os elementos dessa lista terem sido analisados e os elementos menos 1 da outra lista serem analisados. Então, neste exemplo, isso significa que faremos exatamente 7 comparações. Em geral, se as listas são de comprimento $N$, o número de comparações que este algoritmo fará é $N + N-1$ ou $2N - 1$. Então, mesmo para o caso em que uma lista tem 100 elementos e a segunda tem 1000, isso é apenas cerca de 1100 comparações, uma melhoria significativa em relação ao $10^5$ da abordagem anterior!\n",
    "Os cientistas da computação chamam este segundo algoritmo de um algoritmo de tempo linear (em notação matemática, $\\large{O}$ $(n)$ ) porque a equação que descreve o número de comparações é linear. O primeiro algoritmo é chamado de algoritmo de tempo quadrático ( $\\large{O}$ $(n^2)$ ) porque sua equação é quadrática."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Selection sort\n",
    "\n",
    "Agora que temos pelo menos um motivo para classificar os dados (há muitos outros -- você provavelmente pode pensar em vários deles), vejamos um primeiro algoritmo, chamado \"Selection sort\", para realizar a classificação e vamos analisar sua complexidade em termos de tempo.\n",
    "\n",
    "Nos nossos exemplos a seguir usaremos um lista de números como a coleção. É claro que quaisquer números possuem uma relação de ordem entre si. Apesar de usarmos inteiros, os algoritmos servem para ordenar qualquer coleção de elementos que possam ser comparados."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A idéia do algoritmo \"selection sort\" é a seguinte:\n",
    "- Ache o menor elemento a partir da posição $0$. Troque então este elemento com o elemento da posição $0$\n",
    "- Ache o menor elemento a partir da posição $1$. Troque então este elemento com o elemento da posição $1$\n",
    "- Ache o menor elemento a partir da posição $2$. Troque então este elemento com o elemento da posição $2$\n",
    "\n",
    "E assim sucessivamente...\n",
    "\n",
    "Este algoritmo é chamado de \"selection sort\" porque ele prossegue selecionando repetidamente o elemento mínimo restante e movendo-o para a próxima posição na lista. Vejamos uma animação da execução do algoritmo:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<video controls src=\"videos/selection.mp4\" />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def selectionSort(vet):\n",
    "    for i in range(len(vet) - 1):\n",
    "        min = i\n",
    "        \n",
    "        for j in range(i, len(vet)):\n",
    "            if vet[min] > vet[j]:\n",
    "                min = j\n",
    "        if min != i:\n",
    "            vet[i], vet[min] = vet[min], vet[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lista = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]\n",
    "selectionSort(lista)\n",
    "lista"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "O algoritmo \"selection sort\" conforme descrito a seguir, tem duas propriedades que geralmente são desejáveis em algoritmos de classificação.\n",
    "\n",
    "A primeira propriedade é que o algoritmo é realizado \"in-place\". Isso significa que ele usa essencialmente nenhum armazenamento extra além do necessário para a entrada (a lista não triada nesse caso). Um pouco de armazenamento extra pode ser usado (por exemplo, uma variável temporária para manter o índice para o menor elemento). A propriedade importante é que o armazenamento extra necessário não deve aumentar à medida que o tamanho da entrada aumenta."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A segunda é que o algoritmo de classificação é estável. Isso significa que dois elementos que são iguais mantêm sua ordem relativa inicial. Isso se torna importante se houver informações adicionais anexadas aos valores que estão sendo classificados (por exemplo, se estamos ordenando uma lista de pessoas usando uma função de comparação que compara suas datas de nascimento). Os algoritmos de classificação estáveis garantem que a classificação de uma lista já ordenada deixa a ordem da lista inalterada, mesmo na presença de elementos que são tratados como iguais pela comparação."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "\"Selection sort\" é apenas um dos muitos algoritmos de classificação, alguns dos quais são mais rápidos do que outros. O algoritmo realiza uma troca por cada passagem na lista. Para fazer isso, ele procura o menor valor realizando uma passagem pela lista e, depois de completar a passagem, o coloca no local apropriado. Após a segunda passagem, o próximo menor elemento está no lugar. Este processo continua e requer $n-1$ passagens para classificar $n$ itens, uma vez que o item final deve estar no lugar após $n-1$ passos. Sua complexidade portanto é expressa como $\\large{O}$ $(n^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Bubble sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "O algoritmo \"Bubble sort\" faz várias passagens através de uma lista. Ele compara itens adjacentes e troca aqueles que estão fora de ordem. Cada passagem pela lista coloca o próximo maior valor no seu devido lugar. Em essência, cada item \"borbulha\" até o local onde pertence.\n",
    "Se houver $n$ itens na lista, existem $n-1$ pares de itens que precisam ser comparados na primeira passagem. É importante notar que, uma vez que o maior valor da lista faz parte de um par, ele será continuamente movido até a passagem estar completa.\n",
    "\n",
    "No início da segunda passagem, o maior valor está agora no lugar. Existem $n-1$ itens para ordenar, o que significa que haverá $n-2$ pares. Uma vez que cada passagem coloca o próximo maior valor no lugar, o número total de passes necessários será $n-1$. Depois de completar as $n-1$ passagens, o menor item deve estar na posição correta, sem necessidade de processamento adicional. A simulação abaixo mostra a função completa do \"Bubble sort\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<video controls src=\"videos/bubble.mp4\" />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def bubbleSort (vet):\n",
    "    for i in range(len(vet) - 1):\n",
    "        for j in range(0, len(vet) - i - 1):\n",
    "            if vet[j] > vet[j + 1]:\n",
    "                vet[j], vet[j + 1] = vet[j + 1], vet[j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lista = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]\n",
    "bubbleSort(lista)\n",
    "lista"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Para analisar o \"Bubble sort\", devemos notar que, independentemente de como os itens estão dispostos na lista inicial, as $n-1$ passagens serão feitas para classificar uma lista de tamanho $n$. O número total de comparações é a soma dos primeiros $n-1$ inteiros. Lembre-se de que a soma dos $n$ primeiros inteiros é $\\frac{1}{2}n^2 + \\frac{1}{2}n$. A soma dos $n-1$ primeiros inteiros é $\\frac{1}{2}n^2 + \\frac{1}{2}n - n$, que é $\\frac{1}{2}n^2 - \\frac{1}{2}n$. Isso ainda é uma comparação de $\\large{O}$ $(n^2)$. No melhor dos casos, se a lista já estiver ordenada, nenhuma troca será feita. No entanto, no pior caso, cada comparação causará uma troca. Em média, trocamos metade do tempo."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "O algoritmo \"Bubble sort\" é muitas vezes considerado o método de classificação mais ineficiente, pois deve trocar itens antes que a localização final seja conhecida. Essas operações de câmbio \"desperdiçadas\" são muito onerosas. No entanto, como o \"bubble sort\" faz passar toda a parte não ordenada da lista, ele tem a capacidade de fazer algo que a maioria dos algoritmos de classificação não pode. Em particular, se durante uma passagem não houver trocas, então sabemos que a lista deve estar ordenada. O algoritmo pode ser modificado para parar cedo se achar que a lista foi ordenada. Isso significa que, para listas que exigem apenas algumas passagens, o \"buble sort\" pode ter uma vantagem na medida em que reconhecerá a lista ordenada e irá parar. O código a seguir mostra esta modificação, que é muitas vezes referida como a \"short bubble sort\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def bubbleSort (vet):\n",
    "    for i in range(len(vet) - 1, 0, -1):\n",
    "        exchange = False\n",
    "        for j in range(i):\n",
    "            if vet[j] > vet[j + 1]:\n",
    "                vet[j], vet[j + 1] = vet[j + 1], vet[j]\n",
    "                exchange = True\n",
    "        if not exchange:\n",
    "            break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Insertion sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Nosso \"Bubble sort\" modificado funciona melhor do que o \"Selection sort\" para listas que já estão classificadas. Mas nosso \"Bubble sort\" modificado ainda pode funcionar mal se muitos itens estiverem fora de ordem na lista. Outro algoritmo, denominado \"Insertion sort\" tenta explorar a ordem parcial da lista de maneira diferente. A estratégia é a seguinte:\n",
    "- No i-ésimo passo pela lista, onde $i$ varia de $1$ a $n-1$, o i-ésimo item deve ser inserido em seu lugar apropriado entre os primeiros $i$ itens na lista.\n",
    "- Após o i-ésimo passo, os primeiros \"i\" itens devem estar ordenados.\n",
    "\n",
    "Este processo é análogo ao modo como muitas pessoas organizam cartas em suas mãos. Ou seja, se você mantiver as primeiras $i-1$ cartas em ordem, você escolhe a i-ésima carta e compara com esses cartas até que seu local apropriado seja encontrado."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Tal como acontece com os outros algoritmos de ordenação, o \"Insertion sort\" consiste em dois laços. O laço externo atravessa as posições de $1$ a $n-1$. Para cada posição $i$ neste laço, você salva o item e inicia o laço interno na posição $i-1$. Para cada posição $j$ neste laço, você move o item para $j+1$ até encontrar o ponto de inserção para o item salvo (item $i$).\n",
    "A simulação abaixo mostra a função completa para o \"Insertion sort\":"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<video controls src=\"videos/insertion.mp4\" />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def insertionSort(vet):\n",
    "    for i in range (1, len(vet)):\n",
    "        aux = vet[i]\n",
    "        j = i - 1\n",
    "        while j >= 0 and vet[j] > aux:  # Poe elementos v[j] > v[i]\n",
    "            vet[j + 1] = vet[j]         # para frente e\n",
    "            j -= 1                      # decrementa j\n",
    "        vet[j + 1] = aux                # poe v[i] na pos. correta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lista = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]\n",
    "insertionSort(lista)\n",
    "lista"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Mais uma vez, a análise se concentra no laço interno. O laço externo executa $n-1$ vezes. No pior caso, quando todos os dados estão fora de ordem, o laço interno é iniciado uma vez na primeira passagem pelo laço externo, duas vezes na segunda passagem, e assim por diante, para um total de $\\frac{1}{2}n^2 - \\frac{1}{2}n$ vezes. Assim, o comportamento do pior caso do tipo de inserção é $\\large{O}$ $(n^2)$.\n",
    "\n",
    "Quanto mais itens na lista estiverem em ordem, melhor fica o \"Insertion sort\" até, no melhor caso de uma lista ordenada, ter o comportamento linear. No caso médio, no entanto, o \"Insertion sort\" ainda é quadrático. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercícios"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ordem Crescente\n",
    "Escreva uma função que verifique se um vetor `v[0..n-1]` está em ordem crescente. Esse exercício põe em prática a estratégia de escrever os testes antes de inventar algoritmos para um dado problema."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Inserindo Chave\n",
    "Escreva uma função que receba um inteiro `x` e um vetor `v[0..n-1]` de inteiros em ordem crescente e inseri `x` no vetor de modo a manter a ordem crescente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "def insertKey(x, v):\n",
    "    n = len(v)\n",
    "    e, d = 0, n - 1\n",
    "    while e <= d:\n",
    "        m = (e + d) // 2\n",
    "        if m == n - 1 and x >= v[m]:\n",
    "            v.append(x)\n",
    "            return\n",
    "        elif m == 0 and x <= v[0]:\n",
    "            v.insert(0, x)\n",
    "            return\n",
    "        elif v[m] <= x < v[m + 1]:\n",
    "            v.insert(m+1, x)\n",
    "            return\n",
    "        elif x < v[m]:\n",
    "            d = m - 1\n",
    "        else:\n",
    "            e = m + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "lst = sorted([randint(10,50) for _ in range(15)])\n",
    "print(lst)\n",
    "key = randint(0, 60)\n",
    "print(key)\n",
    "insertKey(key, lst)\n",
    "print(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Insertion Sort Recursivo\n",
    "Escreva uma versão recursiva do algoritmo de ordenação por inserção."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "def insertionSort(vet):\n",
    "    if len(vet) <= 1:\n",
    "        return vet\n",
    "    else:\n",
    "        return insert(vet[0], insertionSort(vet[1:]))\n",
    "    \n",
    "    \n",
    "def insert(element, vet):\n",
    "    ''' Inserts element into its proper place in a sorted list vet.\n",
    "        input: element is an item to be inserted.  vet is a sorted list.\n",
    "        output: A sorted list.\n",
    "    '''\n",
    "    if len(vet) == 0:\n",
    "        return [element]\n",
    "    elif element < vet[0]:\n",
    "        return [element] + vet\n",
    "    else:\n",
    "        return vet[0:1] + insert(element, vet[1:])\n",
    "    \n",
    "\n",
    "vet = [randint(0, 100) for _ in range(15)]\n",
    "print(vet)\n",
    "print(insertionSort(vet))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Critique a seguinte implementação do algoritmo de ordenação por inserção:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion(v):\n",
    "    n = len(v)\n",
    "    for j in range(1, n):\n",
    "        i = j - 1\n",
    "        while i >= 0 and v[i] > v[i+1]:\n",
    "            v[i], v[i+1] = v[i+1], v[i]\n",
    "    return v\n",
    "\n",
    "print(insertion([6, 2, 3, 8, 1, 7, 9, 4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mediana\n",
    "Seja `v[0..n-1]` um vetor de números inteiros, todos diferentes entre si.  A mediana do vetor é um elemento do vetor que seja maior que metade dos elementos do vetor e menor que (a outra) metade dos elementos.  Mais precisamente, a mediana de `v[0..n-1]` é um número `m` dotado de duas propriedades: (1) `m` é estritamente maior que exatamente `⌊(n-1)/2⌋` elementos do vetor; (2) se n (número de elementos do vetor) é impar então `m` é igual a algum elemento do vetor, caso contrário, a mediana é definida como a média dos dois valores do meio. Não confunda mediana com média. Por exemplo, a média de  `1 2 99`  é  `51`, enquanto a mediana é `2`.)  Escreva um algoritmo que encontre a mediana de um vetor `v[0..n-1]` de números diferentes entre si."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "\n",
    "def insertionSort(vet):\n",
    "    for i in range (1, len(vet)):\n",
    "        aux = vet[i]\n",
    "        j = i - 1\n",
    "        while j >= 0 and vet[j] > aux:  # Poe elementos v[j] > v[i]\n",
    "            vet[j + 1] = vet[j]         # para frente e\n",
    "            j -= 1                      # decrementa j\n",
    "        vet[j + 1] = aux                # poe v[i] na pos. correta\n",
    "\n",
    "        \n",
    "def mediana(vet):\n",
    "    insertionSort(vet)\n",
    "    n = len(vet)\n",
    "    i_mediana = (n - 1) // 2\n",
    "    if n % 2 == 1: \n",
    "        return vet[i_mediana]\n",
    "    else:\n",
    "        return (vet[i_mediana] + vet[i_mediana + 1]) // 2\n",
    "\n",
    "\n",
    "vet = [randint(0, 100) for _ in range(15)]\n",
    "print(vet)\n",
    "print(mediana(vet))"
   ]
  }
 ],
 "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.6.5"
  },
  "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": {
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}