Clases/Clase_19_Caso_de_Estudio_III_Busqueda_y_Ordenamiento_2020.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "colab": {
      "name": "Clase_19_Caso_de_Estudio_III_Busqueda_y_Ordenamiento_2020.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "JLo6NbmI4Wc3",
        "QxNn1b5i4Wc3",
        "G7NLxcH5ru0P",
        "LtNxVVf-b1Zt",
        "Ex5we7Qy4Wc3"
      ],
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/bpoblete/CC1002/blob/master/Clases/Clase_19_Caso_de_Estudio_III_Busqueda_y_Ordenamiento_2020.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "B5f-tlYA4Wc3"
      },
      "source": [
        "# Clase 19: Caso de Estudio III\n",
        "\n",
        "## Búsqueda y ordenamiento\n",
        "\n",
        "En este caso de estudio se estudiarán algoritmos de búsqueda y ordenamiento utilizando estructuras mutables (listas de Python). En particular:\n",
        "\n",
        "- Algoritmos de búsqueda: \n",
        "    - Búsqueda Secuencial\n",
        "    - Búsqueda Binaria\n",
        "\n",
        "- Algoritmos de ordenamiento: \n",
        "    - Mergesort\n",
        "    - Bubblesort\n",
        "    - Quicksort\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zfA54oxq4Wc3"
      },
      "source": [
        "## Búsqueda en una lista\n",
        "\n",
        "### Problema\n",
        "\n",
        "- Lista (de Python) de números enteros\n",
        "- Se desea buscar el índice en la lista donde se encuentra un valor en particular\n",
        "  - Si hay varias ocurrencias de valor, se debe devolver el índice de la primera\n",
        "  - Si el valor no está en el arreglo, se devuelve None (valor inválido para un índice)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HncPXZnR4Wc3"
      },
      "source": [
        "### Búsqueda Secuencial\n",
        "\n",
        "La búsqueda secuencial es el algoritmo usado en clases para buscar sobre una lista. Dado una lista L y un valor x a buscar, seguimos el siguiente **algoritmo**:\n",
        "- partiendo del primer elemento (indice i=0) comparamos el elemento en esa posición con el valor buscado x. \n",
        "- si es igual, ¡lo encontramos! Retornamos el índice i.\n",
        "- si no, incrementamos i en 1, esto es, seguimos buscando con el siguiente elemento.\n",
        "- al final, si i sobrepasa el índice del mayor elemento de la lista, podemos decir que el valor buscado x **no está**.\n",
        "\n",
        "**Observación:** Este algoritmo sirve para tanto para una lista ordenada, como una lista desordenada. Por ahora supondremos que la lista está _desordenada_. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pNmGSCYh4Wc3"
      },
      "source": [
        "# Las listas utilizadas en esta implementacion son listas de Python\n",
        "# Los valores almacenados en las listas son numeros enteros\n",
        "\n",
        "# Busqueda Secuencial\n",
        "\n",
        "# busquedaSecuencial: list(int) int -> int o None\n",
        "# devuelve el indice de la lista donde se encuentra valor haciendo una\n",
        "# busqueda secuencial, o devuelve None si no esta\n",
        "# ejemplo: busquedaSecuencial([258, 45, 99, 14, 102, 75, 128], 14) devuelve 3\n",
        "def busquedaSecuencial(lista, valor):\n",
        "    for indice in range(len(lista)):\n",
        "        if lista[indice] == valor:\n",
        "            # se encontro el valor\n",
        "            return indice\n",
        "    # valor no fue encontrado\n",
        "    return None\n",
        "\n",
        "# Test\n",
        "lista = [258, 45, 99, 14, 102, 75, 128]\n",
        "assert busquedaSecuencial(lista, 14) == 3\n",
        "assert busquedaSecuencial(lista, 20) == None\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "68j5KOBo4Wc3"
      },
      "source": [
        "lista = [258, 45, 99, 14, 102, 75, 128]\n",
        "busquedaSecuencial(lista, 102)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "z2ZZKDLb4Wc3"
      },
      "source": [
        "**¿Cuántas comparaciones debe realizar para buscar una lista con n valores?**\n",
        "\n",
        "- Mínimo = 1 (mejor caso)\n",
        "- Máximo = n (peor caso)\n",
        "- Promedio? Si uno busca el primer elemento de la lista, entonces haremos 1 comparación, si buscamos el segundo, haremos 2 comparaciones, y así hasta el último, donde hacemos n comparaciones.\n",
        "Si buscaremos n elementos en la lista y cada elemento que buscamos está en una posición al azar en la lista, entonces intuitivamente uno de ellos será el 1ero de la lista, otro será el segundo, etc. Entonces, si sumamos las comparaciones del 1ero, del 2do, etc. y lo dividimos por n calcularemos el número promedio de comparaciones:   \n",
        "\n",
        "  Promedio = $\\frac{1+2+\\ldots+n}{n} = \\frac{1}{n}\\sum_{i=1}^{n}i = \\frac{n+1}{2}$       \n",
        "  - En promedio 500 comparaciones para buscar en  $n = 1000$ valores\n",
        "  - En promedio 500.000.000 comparaciones para buscar en $n = 1.000.000.000$ valores\n",
        "\n",
        "\n",
        "**Listas ordenadas**: Si supiéramos que vamos a buscar siempre sobre una lista ordenada, cómo podríamos mejorar el algoritmo de búsqueda lineal para que se demore un poco menos en encontrarlo? Piense en (a) cómo modificaría el algoritmo, y (b) cuánto mejoraría. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JLo6NbmI4Wc3"
      },
      "source": [
        "### Búsqueda Binaria\n",
        "\n",
        "Si la lista sobre la cual buscamos está **ordenada** podemos mostrar un algoritmo mucho más eficiente (rápido), uno que toma menos comparaciones!\n",
        "\n",
        "El algoritmo se denomina **búqueda binaria** y aquí daremos la versión recursiva:\n",
        "\n",
        "- Si lista está vacía, retornar None (caso base)\n",
        "- Sino:\n",
        "  - Comparar x con elemento en la mitad de la lista\n",
        "  - Si son iguales, devolver índice de mitad\n",
        "  - Si x es menor, buscar recursivamente en primera mitad de la lista\n",
        "  - Si x es mayor, buscar recursivamente en segunda mitad de la lista\n",
        "\n",
        "\n",
        "**EXPLICACIÓN**: Puede ver una explicación detallada del algoritmo de búsqueda binaria en el siguiente video: [¿Cómo funciona la búsqueda binaria?](https://drive.google.com/file/d/1oZUv4mj6A5KPi74k9y2MS3yZ00429e6y/view?usp=sharing)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "l44zVdMErEJq"
      },
      "source": [
        "### Función que implementa Búsqueda Binaria"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gQtwFQ7k4Wc3"
      },
      "source": [
        "# Busqueda Binaria\n",
        "\n",
        "# busquedaBinariaRec: list(int) int int int -> int o None\n",
        "# devuelve el indice de la lista donde se encuentra valor haciendo una\n",
        "# busqueda binaria en el rango [ip,iu], o devuelve None si no esta\n",
        "# Requiere que la lista este ordenada ascendentemente\n",
        "# ejemplo: busquedaBinariaRec([14, 45, 75, 99, 102, 128, 258], 45, 0, 6) devuelve 1\n",
        "def busquedaBinariaRec(listaOrdenada, valor, ip, iu):\n",
        "    # Caso base: valor no fue encontrado\n",
        "    if ip > iu:\n",
        "        return None\n",
        "    im = (ip + iu) // 2 # indice del medio\n",
        "    # Caso base: valor esta al medio de la lista\n",
        "    if listaOrdenada[im] == valor:\n",
        "        return im\n",
        "    # Llamados recursivos\n",
        "    elif valor < listaOrdenada[im]:\n",
        "        return busquedaBinariaRec(listaOrdenada, valor, ip, im - 1)\n",
        "    else: # valor > listaOrdenada[im]\n",
        "        return busquedaBinariaRec(listaOrdenada, valor, im + 1, iu)        \n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2ggdtfUK4Wc3"
      },
      "source": [
        "# busquedaBinaria: list(int) int -> int o None\n",
        "# Hace la primera invocacion a busquedaBinariaRec\n",
        "def busquedaBinaria(listaOrdenada, valor):\n",
        "    return busquedaBinariaRec(listaOrdenada, valor, 0, len(listaOrdenada) - 1)\n",
        "\n",
        "# Test\n",
        "lista = [14, 45, 75, 99, 102, 128, 258]\n",
        "assert busquedaBinaria(lista, 45) == 1\n",
        "assert busquedaBinaria(lista, 20) == None"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4fJMTq0L4Wc3"
      },
      "source": [
        "listaOrdenada = [14, 45, 75, 99, 102, 128, 258]\n",
        "busquedaBinaria(lista, 102)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QxNn1b5i4Wc3"
      },
      "source": [
        "### Tiempo (rapidez) del algoritmo\n",
        "\n",
        "**La Búsqueda binaria es eficiente**\n",
        "\n",
        "- Si lista tiene n valores, búsqueda binaria realiza aproximadamente $\\log n$ comparaciones\n",
        "  - Si $n = 1.000.000.000$, búsqueda binaria realiza aproximadamente 30 comparaciones (*)\n",
        "  - Mucho más rápido que búsqueda secuencial\n",
        "- Si la única operación permitida para buscar es la comparación entre objetos, búsqueda binaria es óptima (lo mejor posible)\n",
        "\n",
        "\n",
        "**Observación matemática:** ¿Por qué podemos decir que siempre toma $\\log n$ comparaciones? En cada comparación se descarta _la mitad_ del arreglo. Un buen desafío es demostrar que, si tiene un arreglo de n elementos, al descartar la mitad en cada paso, el número máximo de pasos siempre es $\\log n$. Inténte demostrarlo!\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Tn85CmGb4Wc3"
      },
      "source": [
        "# Segunda Parte:\n",
        "\n",
        "## Ordenamiento (ordenar una lista)\n",
        "\n",
        "### El Problema\n",
        "\n",
        "Tenemos el siguiente problema. Queremos ordenar una lista de valores (por ejemplo, enteros):\n",
        "- los valores en la lista están desordenados\n",
        "- queremos terminar con una lista con los valores ordenados.\n",
        "\n",
        "Gráficamente:\n",
        "\n",
        "<div>\n",
        "<img src=\"https://github.com/bpoblete/CC1002/raw/master/Clases/ordenamiento.png\" alt=\"Ejemplo de AB\" width=\"50%\"/>\n",
        "</div>\n",
        "\n",
        "**Nota:** Si bien mencionamos listas de enteros, puede ser listas de cualquier tipo de valor, basta que los elementos sean comparables entre sí. Por ejemplo, podrían ser _strings_, _floats_, etc. Por simplicidad, pensaremos en números enteros.\n",
        "\n",
        "### Los Algoritmos\n",
        "\n",
        "Explicaremos 3 algoritmos distintos:\n",
        "- Mergesort (o algoritmo de mezcla)\n",
        "- Bubblesort\n",
        "- Quicksort\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "G7NLxcH5ru0P"
      },
      "source": [
        "## Mergesort\n",
        "\n",
        "Para entender el problema de ordenamiento y el algoritmo de Ordenamiento por Mezcla (*Mergesort*), debe ver el siguiente video.\n",
        "\n",
        "El video plantea un desafío principal. Intente primero resolverlo por su cuenta (es OPCIONAL!) antes de ir a mirar la solución de más abajo.  \n",
        "\n",
        "[Video MergeSort](https://drive.google.com/file/d/1Ad4ZCGbese8yPBmnBd3ywvvqQAf3nJnG/view?usp=sharing)\n",
        "\n",
        "Si logró hacer el desafío principal, intente ahora hacer el siguiente desafíos secundario OPCIONAL. No es difícil pero puede tomar harto tiempo pues requiere manejarse con archivos.\n",
        "\n",
        "- Implemente una versión de mergesort que ordene palabras que lea desde un archivo de texto que contiene una palabra por línea. Suponga que el archivo es demasiado grande como para leerlo en memoria (varios de Gigabytes) por no puede usar listas de Python para almacenarlo. En vez, debe ir leyéndolo desde el archivo y ir escribiendo de inmediato lo que vaya ordenando en otros archivo. **Nota**: es posible usar listas de Python de tamaño fijo (2, 4, o 10 elementos, si necesita); el punto es que no puede leer todo el archivo a una lista de Python y luego hacer mergesort a la lista. \n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LtNxVVf-b1Zt"
      },
      "source": [
        "### Solución de Mergesort (Recursiva):"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Rurk7lWdbhsQ"
      },
      "source": [
        "# mezclarListas: list(in) list(in) -> list(any)\n",
        "# Recibe dos listas de enteros, cada una de ellas ordenada\n",
        "# y retorna una sola lista ordenada compuesta por los elementos de las dos listas.\n",
        "def mezclarListas (L1, L2):\n",
        "  assert type(L1)==list and type(L2)==list\n",
        "  L = []\n",
        "  while len(L1)>0 and len(L2)>0:\n",
        "    if L1[0]<=L2[0]:\n",
        "      primerElemento = L1.pop(0)\n",
        "      L.append(primerElemento)\n",
        "    else: # cao L2[0]<L1[0]\n",
        "      primerElemento = L2.pop(0)\n",
        "      L.append(primerElemento)\n",
        "  # Al terminar el while una de las listas (L1 o L2) es vacia\n",
        "  # Pero la otra podria NO ser vacia, hay que copiarla a L\n",
        "  if len(L1)==0:\n",
        "    L.extend(L2)\n",
        "  else: # caso len(L1)==0\n",
        "    L.extend(L1)\n",
        "  return L\n",
        "\n",
        "# Tests\n",
        "L1 = [14, 16, 22, 22, 30, 44, 55]\n",
        "L2 = [5, 7, 18, 22, 23, 25, 29]\n",
        "L = [5, 7, 14, 16, 18, 22, 22, 22, 23, 25, 29, 30, 44, 55]\n",
        "assert mezclarListas(L1,L2) == L\n",
        "\n",
        "# mergesort: list(int) -> list(int)\n",
        "# Ordena ascendemente la lista usando el algoritmo Mergesort\n",
        "# ejemplo: mergesort([258, 45, 99, 14, 102, 75, 128]) retorna una nueva lista\n",
        "# [14, 45, 75, 99, 102, 128, 258]\n",
        "def mergesort(lista):\n",
        "    assert type(lista)==list\n",
        "    # Si la lista es de tamano 1 o 0, nada que hacer: ya esta ordenada!\n",
        "    largo = len(lista)\n",
        "    if largo<=1: \n",
        "      return lista \n",
        "    # Dividir en dos listas\n",
        "    puntoMedio = largo//2\n",
        "    listaIzq = lista[0:puntoMedio]\n",
        "    listaDer = lista[puntoMedio:]\n",
        "    listaIzqOrdenada = mergesort(listaIzq) \n",
        "    listaDerOrdenada = mergesort(listaDer)\n",
        "    listaOrdenada = mezclarListas(listaIzqOrdenada,listaDerOrdenada)\n",
        "    return listaOrdenada\n",
        "\n",
        "# Test\n",
        "lista = [258, 45, 99, 14, 102, 75, 128]\n",
        "listaOrdenada = mergesort(lista)\n",
        "assert listaOrdenada == [14, 45, 75, 99, 102, 128, 258]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hnbB5AmNicSQ"
      },
      "source": [
        "import random\n",
        "L = []\n",
        "for i in range(0,30):\n",
        "  L.append(random.randint(1,100))\n",
        "print(\"Lista L =\",L)\n",
        "print(\"Lista L ordenada =\",mergesort(L))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "g7-Er8Y04Wc3"
      },
      "source": [
        "## Bubblesort\n",
        "\n",
        "Este es un algoritmo de ordenación más simple que mergesort pero más lento.\n",
        "\n",
        "**Idea:** en cada una de las pasadas \"hacer subir la burbuja (el mayor) al último lugar\"\n",
        "\n",
        "**Algoritmo:**\n",
        "\n",
        "- Repetir $n-1$ veces(para los $n, n-1,\\ldots,2$ primeros elementos)\n",
        "  - Recorrer todos los elementos (salvo el último)\n",
        "  - Comparar elemento con siguiente\n",
        "  - Intercambiar si están fuera de orden, es decir, si elemento es mayor que el siguiente\n",
        "\n",
        "**Intuición:** Este algoritmo es lo que Ud. quizás haría para ordenar una fila de personas. Comenzando del inicio de la fila, compararía a la primera persona con el segunda persona. Si la primera es más alta, las intercambiaría de posición. Luego, compararía a la persona actualmente segunda con la tercera; si la segunda es más alta, los intercambiaría de posición. Etc. Y seguría así hasta el final. Note que estos intercambios ¡no dejan a todos ordenados en una primera pasada! Debe volver a revisarlos de nuevo a todos desde el comienzo, de a pares consecutivos (con el mismo procedimiento descrito), haciendo los intercambios que corresponda. Sólo cuando ha revisado a pares desde el inicio al final y NO ha hecho ningún intercambio, es que puede decir que la lista está ordenada. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yXbyJoqW4Wc3"
      },
      "source": [
        "# Bubblesort\n",
        "\n",
        "# bubblesort: list(int) -> None\n",
        "# efecto: ordena ascendemente la lista usando el algoritmo Bubblesort\n",
        "# ejemplo: bubblesort([258, 45, 99, 14, 102, 75, 128]) modifica la lista\n",
        "# y la deja en el estado [14, 45, 75, 99, 102, 128, 258]\n",
        "def bubblesort(lista):\n",
        "    k = len(lista)\n",
        "    while k > 1:\n",
        "        # hacer una pasada sobre lista[0], ..., lista[k - 1]\n",
        "        for j in range(k-1):\n",
        "            if lista[j] > lista[j + 1]:\n",
        "                # intercambiar a[j] con a[j+1]\n",
        "                # sintaxis para swap con listas de Python\n",
        "                lista[j], lista[j + 1] = lista[j + 1], lista[j]\n",
        "        # disminuir k\n",
        "        k = k - 1\n",
        "\n",
        "# Test\n",
        "lista = [258, 45, 99, 14, 102, 75, 128]\n",
        "bubblesort(lista)\n",
        "assert lista == [14, 45, 75, 99, 102, 128, 258]\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ex5we7Qy4Wc3"
      },
      "source": [
        "### Entendiendo Bubblesort:\n",
        "\n",
        "\n",
        "Intentaremos ordenar manualmente la siguiente lista, de menor a mayor, usando bubblesort:\n",
        "\n",
        "```\n",
        "[\"D\",\"C\",\"B\",\"E\",\"A\"]\n",
        "```\n",
        "\n",
        "para eso mostraremos las distintas pasadas en una tabla, a continuación. En la tabla, cada línea muestra una \"pasada\" ordenando de a pares, mostrando cuáles elementos se comparan y si se intercambian o no.\n",
        "\n",
        "Aquí usaremos la notación:\n",
        "- \"X\" con \"Y\": significa que comparamos la letra X con la letra Y, \n",
        "- Si aparece **\"(si)\"** significa que se hizo un un intercambio.\n",
        "- Si aparece **\"(no)\"** es  que se hizo un un intercambio.\n",
        "- Al final de cada línea, se muestra cómo quedó la lista en esa pasada.\n",
        "\n",
        "<br/>\n",
        "<br/>\n",
        "\n",
        "\n",
        "```\n",
        "Lista original: [\"D\",\"C\",\"B\",\"E\",\"A\"]\n",
        "```\n",
        "\n",
        "\n",
        "\n",
        "| Recorrido  | 1ra comp. | 2da comp. | 3ra comp.|4ta comp.| lista resultado al final de la pasada|\n",
        "| :----------|:---------:| ---------:|----------|---------|------|\n",
        "| 1ro | \"D\" con \"C\":(si) | \"D\" con \"B\":(si)  |  \"D\" con \"E\": (no) | \"E\" con \"A\":(si)     |     [\"C\",\"B\",\"D\",\"A\",\"E\"]   |\n",
        "| 2do | \"C\" con \"B\":(si) | \"C\" con \"D\":(no)  |  \"D\" con \"A\": (si)  | \"D\" con \"E\":(no)    |  [\"B\",\"C\",\"A\",\"D\",\"E\"] |\n",
        "| 3ro | \"B\" con \"C\":(no) | \"C\" con \"A\":(si)    | \"C\" con \"D\":(no)  | \"D\" con \"E\":(no)  | [\"B\",\"A\",\"C\",\"D\",\"E\"] |\n",
        "| 4to | \"B\" con \"A\":(si)  | \"B\" con \"C\":(no) | \"C\" con \"D\":(no) | \"D\" con \"E\":(no)  |  [\"A\",\"B\",\"C\",\"D\",\"E\"]    ||\n",
        "| 4to $(n)$| \"A\" con \"B\":(no)  | \"B\" con \"C\":(no) | \"C\" con \"D\":(no) | \"D\" con \"E\":(no)  |  [\"A\",\"B\",\"C\",\"D\",\"E\"]    ||\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EiU6uceI4Wc3"
      },
      "source": [
        "## Quicksort\n",
        "\n",
        "Este algoritmo es un algoritmo muy rápido, más rápido que Bubblesort pero algo más difícil de entender. Sin embargo es uno de los más usados en la práctica, porque\n",
        "- es rápido, y\n",
        "- ordena las listas \"en el lugar\", sin requerir crear otras listas (en su implementación más simple, Mergesort requiere usar otras listas). \n",
        "\n",
        "**Introducción:** Quicksort es un algoritmo recursivo de ordenamiento. Se basa en la siguiente idea:\n",
        "1. Dada la lista desordenada, se escoge un elemento \"pivote\" dentro de la lista (por ejemplo, el que está al medio). Llamémoslo **P**.\n",
        "2. El resto de la lista se compara con **P**. Los elementos _menores que **P**_ se copian a la izquierda de **P**, y los elementos _mayores que **P**_ se copian a la derecha de **P**. \n",
        "3. Y luego se ordenan recursivamente las listas a la izquierda y derecha de **P**. \n",
        "\n",
        "**Nota:** Al paso 2, donde se mueven menores y mayores con respecto a **P**, se le llama **particionar**.\n",
        "\n",
        "Gráficamente:\n",
        "\n",
        "</br>\n",
        "<div>\n",
        "<img src=\"https://github.com/bpoblete/CC1002/raw/master/Clases/quicksort.png\" alt=\"Ejemplo de AB\" width=\"60%\" />\n",
        "</div>\n",
        "\n",
        "Detalles:\n",
        "\n",
        "- P: se denomina “pivote”\n",
        "  - P puede ser cualquier valor de la lista\n",
        "- La recomendación es siempre escogerlo aleatoriamente entre los valores de la lista\n",
        "- Otro método de selección: escoger tres valores aleatorios de la lista, el del medio de los tres se escoge como pivote\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "H8Xrp85C4Wc3"
      },
      "source": [
        "# qsort: list(int) int int -> None\n",
        "# efecto: ordena ascendemente la lista usando el algoritmo Quicksort\n",
        "# en el rango [ip,iu]\n",
        "# ejemplo: qsort([258, 45, 99, 14, 102, 75, 128], 0, 6) modifica la lista\n",
        "# y la deja en el estado [14, 45, 75, 99, 102, 128, 258]\n",
        "def qsort(lista, ip, iu):\n",
        "    # si ip >= iu no se hace nada\n",
        "    if ip < iu:\n",
        "        pivote = particionar(lista, ip, iu)\n",
        "        qsort(lista, ip, pivote - 1)\n",
        "        qsort(lista, pivote + 1, iu)\n",
        "\n",
        "# Test\n",
        "lista = [258, 45, 99, 14, 102, 75, 128]\n",
        "qsort(lista, 0, 6)\n",
        "assert lista == [14, 45, 75, 99, 102, 128, 258]\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "83kQOu1y4Wc3"
      },
      "source": [
        "### Particionar\n",
        "\n",
        "<div>\n",
        "<img src=\"https://github.com/bpoblete/CC1002/raw/master/Clases/particionar.png\" alt=\"Ejemplo de AB\" width=\"60%\"/>\n",
        "</div>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cUUfadGH4Wc3"
      },
      "source": [
        "# Quicksort\n",
        "\n",
        "import random\n",
        "\n",
        "# particionar: list(int) int int -> int\n",
        "# escoge aleatoriamente un pivote y devuelve la posicion donde queda el pivote\n",
        "# luego de particionar la lista en el rango [ip,iu]\n",
        "# efecto: deja todos los valores menores que el pivote a la izquierda de este\n",
        "# y todos los valores mayores que el pivote a la derecha de este\n",
        "# ejemplo: particionar([258, 45, 99, 14, 102, 75, 128], 0, 6) y el pivote es 99\n",
        "# entonces la lista queda como [45, 14, 75, 99, 258, 102, 128] y devuelve 3\n",
        "def particionar(lista, ip, iu):\n",
        "    # Pre-condicion: ip < iu\n",
        "    assert ip < iu\n",
        "    # se escoge pivote aleatoriamente\n",
        "    pivote = random.randint(ip, iu)\n",
        "    # se intercambia con el primero del segmento de lista\n",
        "    lista[ip], lista[pivote] = lista[pivote], lista[ip]\n",
        "    # se particiona usando el pivote\n",
        "    i = ip\n",
        "    for j in range(ip + 1, iu + 1):\n",
        "        if lista[j] < lista[ip]: # recordar que pivote esta en ip\n",
        "            i = i + 1\n",
        "            lista[i], lista[j] = lista[j], lista[i]\n",
        "    # lista[i] contiene el ultimo valor que es menor que el pivote\n",
        "    lista[ip], lista[i] = lista[i], lista[ip]\n",
        "    return i\n",
        "\n",
        "# Test\n",
        "lista = [258, 45, 99, 14, 102, 75, 128]\n",
        "pivote = particionar(lista, 0, 6)\n",
        "for indice in range(0, pivote - 1):\n",
        "    assert lista[indice] < lista[pivote]\n",
        "for indice in range(pivote + 1, len(lista)):\n",
        "    assert lista[indice] > lista[pivote]\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gEtcdxIG4Wc3"
      },
      "source": [
        "# quicksort: list(int) -> None\n",
        "# efecto: ordena ascendemente la lista usando el algoritmo Quicksort\n",
        "# ejemplo: quicksort([258, 45, 99, 14, 102, 75, 128]) modifica la lista\n",
        "# y la deja en el estado [14, 45, 75, 99, 102, 128, 258]\n",
        "def quicksort(lista):\n",
        "    qsort(lista, 0, len(lista) - 1)\n",
        "\n",
        "# Test\n",
        "lista = [258, 45, 99, 14, 102, 75, 128]\n",
        "quicksort(lista)\n",
        "assert lista == [14, 45, 75, 99, 102, 128, 258]\n",
        "lista = [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]\n",
        "quicksort(lista)\n",
        "assert lista == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9WP2cWf34Wc3"
      },
      "source": [
        "### Eficiencia\n",
        "\n",
        "- Tiempos de ordenamiento para una lista con $n$ valores\n",
        "  - Bubblesort: proporcional a $n^2$\n",
        "  - Quicksort: proporcional a $n \\log n$ en promedio (tiene un peor caso $nˆ2$)\n",
        "  - Mergesort: proporcional a $n \\log n$ en promedio. Su peor caso es también $n \\log n$ por lo que a veces es preferido a Quicksort, por ejemplo cuando las listas a ordenar no requieren de mucha memoria."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GQPeIL1bxfG0"
      },
      "source": [
        "### Eso es todo amigxs! Espero hayan disfrutado su caso de estudio :-D"
      ]
    }
  ]
}