Pasos promedio de BubbleSort

Lab2Punto3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bubble Sort Average Time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Programa que aplica el algoritmo de ordenamiento de Bubble Sort sin Flag  sobre todas las permutaciones generadas con itertools.permutations:\n",
    "    * Basado en http://disi.unal.edu.co/~algorithms/applets/InsertSortTimePlot/IsortTimePlot.java\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Mejor tiempo teorico, 36\n",
      "Peor tiempo teorico, 120.0\n",
      "Tiempo promedio teorico, 78.0\n",
      "Mejor tiempo experimental, 35\n",
      "Peor tiempo experimental, 63\n",
      "Tiempo promedio experimental, 49\n"
     ]
    }
   ],
   "source": [
    "import itertools\n",
    "import random\n",
    "\n",
    "\n",
    "\n",
    "def randPermutation(n):\n",
    "    #n determina el tamaño del arreglo n = 5 ->[0,1,2,3,4,] \n",
    "    arr = []\n",
    "    for i in range(n):\n",
    "        arr.append([])\n",
    "        arr[i] = i+1\n",
    "    for i in range(n-1):\n",
    "        # i va desde 0,1,2,3\n",
    "        x = random.randint(i, n-1)\n",
    "        # x guarda un numero entre 0-3\n",
    "        temp = arr[i]\n",
    "        # temp almacena el valor del arreglo\n",
    "        arr[i] = arr[x]\n",
    "        #reemplaza el valor del arreglo con el de la posicion aleatoria que obtuvo       \n",
    "        arr[x] = temp\n",
    "        #rellena el valor que reemplazo con el anterior permutando una celda asi\n",
    "    return arr\n",
    "\n",
    "def numInstructions(x):\n",
    "    \n",
    "    alist = []\n",
    "    for i in range(len(x)):\n",
    "        alist.append([])\n",
    "        alist[i] = x[i]\n",
    "        \n",
    "    steps = 0\n",
    "    '''\n",
    "    Implementacion de BubbleSort sin falg de intercambio desde :\n",
    "    \n",
    "    http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBubbleSort.html\n",
    "    \n",
    "    '''\n",
    "    for passnum in range(len(alist)-1,0,-1):\n",
    "        for j in range(passnum):\n",
    "            if alist[j]>alist[j+1]:\n",
    "                temp = alist[j]\n",
    "                alist[j] = alist[j+1]\n",
    "                alist[j+1] = temp\n",
    "                steps += 2\n",
    "            else:\n",
    "                steps += 1\n",
    "        steps += 1\n",
    "    return steps\n",
    "\n",
    "n = 8\n",
    "#determina el tamaño del arreglo\n",
    "best = float(\"inf\")\n",
    "#best inicia en un numero alto para poder compararlo despues y tomar un numero alto \n",
    "worst = 0\n",
    "suma = 0\n",
    "contador = 0\n",
    "arr = []\n",
    "\n",
    "arr = randPermutation(n)\n",
    "#Arreglo con permutacion aleatoria de tamaño n\n",
    "\n",
    "for i in itertools.permutations(arr):\n",
    "    #i corresponde al subarreglo que proviene de la permutacion \n",
    "    x = numInstructions(i)\n",
    "    # x guardara el numero de instrucciones que le toma\n",
    "    \n",
    "    if x < best:\n",
    "        best = x\n",
    "    if x > worst:\n",
    "        worst = x\n",
    "    suma += x\n",
    "    contador +=1\n",
    "\n",
    "print 'Mejor tiempo teorico, ' + str(5 * n - 4)\n",
    "print 'Peor tiempo teorico, ' + str((3.0 / 2.0) * n ** 2 + (7.0 / 2.0) * n - 4)\n",
    "print 'Tiempo promedio teorico, ' + str((3.0/4.0)*n**2 + (17.0/4.0)*n - 4)\n",
    "print 'Mejor tiempo experimental, ' + str(best)\n",
    "print 'Peor tiempo experimental, ' + str(worst)\n",
    "print 'Tiempo promedio experimental, ' + str(suma / contador)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Programa que aplica el algoritmo de ordenamiento de Bubble Sort sin Flag  sobre algunas permutaciones escogidas al\n",
    "azar generadas con itertools.permutations:\n",
    "\n",
    "    * Basado en http://disi.unal.edu.co/~algorithms/applets/InsertSortTimePlot/IsortTimePlot.java"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Mejor tiempo teorico, 36\n",
      "Peor tiempo teorico, 120.0\n",
      "Tiempo promedio teorico, 78.0\n",
      "Mejor tiempo experimental, 38\n",
      "Peor tiempo experimental, 58\n",
      "Tiempo promedio experimental, 48\n"
     ]
    }
   ],
   "source": [
    "import itertools\n",
    "import random\n",
    "\n",
    "\n",
    "\n",
    "def randPermutation(n):\n",
    "    #n determina el tamaño del arreglo n = 5 ->[0,1,2,3,4,] \n",
    "    arr = []\n",
    "    for i in range(n):\n",
    "        arr.append([])\n",
    "        arr[i] = i+1\n",
    "    for i in range(n-1):\n",
    "        # i va desde 0,1,2,3\n",
    "        x = random.randint(i, n-1)\n",
    "        # x guarda un numero entre 0-3\n",
    "        temp = arr[i]\n",
    "        # temp almacena el valor del arreglo\n",
    "        arr[i] = arr[x]\n",
    "        #reemplaza el valor del arreglo con el de la posicion aleatoria que obtuvo       \n",
    "        arr[x] = temp\n",
    "        #rellena el valor que reemplazo con el anterior permutando una celda asi\n",
    "    return arr\n",
    "\n",
    "def numInstructions(x):\n",
    "    \n",
    "    alist = []\n",
    "    for i in range(len(x)):\n",
    "        alist.append([])\n",
    "        alist[i] = x[i]\n",
    "        \n",
    "    steps = 0\n",
    "    '''\n",
    "    Implementacion de BubbleSort sin falg de intercambio desde :\n",
    "    \n",
    "    http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBubbleSort.html\n",
    "    \n",
    "    '''\n",
    "    for passnum in range(len(alist)-1,0,-1):\n",
    "        for j in range(passnum):\n",
    "            if alist[j]>alist[j+1]:\n",
    "                temp = alist[j]\n",
    "                alist[j] = alist[j+1]\n",
    "                alist[j+1] = temp\n",
    "                steps += 2\n",
    "            else:\n",
    "                steps += 1\n",
    "        steps += 1\n",
    "    return steps\n",
    "\n",
    "n = 8\n",
    "#determina el tamaño del arreglo\n",
    "best = float(\"inf\")\n",
    "#best inicia en un numero alto para poder compararlo despues y tomar un numero alto \n",
    "worst = 0\n",
    "suma = 0\n",
    "contador = 0\n",
    "arr = []\n",
    "\n",
    "arr = randPermutation(n)\n",
    "\n",
    "sampleSize = 100\n",
    "#se define el tamaño de la muestra que se tomara de permutaciones\n",
    "\n",
    "\n",
    "objects = list(itertools.permutations(arr))\n",
    "#Arreglo con permutacion aleatoria de tamaño n\n",
    "\n",
    "for i in range(sampleSize):\n",
    "    x = numInstructions(objects[random.randint(1,len(objects))])\n",
    "    # x guardara el numero de instrucciones que le toma de una permutacion elegida al azar\n",
    "    if x < best:\n",
    "        best = x\n",
    "    if x > worst:\n",
    "        worst = x\n",
    "    suma += x\n",
    "    contador +=1\n",
    "\n",
    "print 'Mejor tiempo teorico, ' + str(5 * n - 4)\n",
    "print 'Peor tiempo teorico, ' + str((3.0 / 2.0) * n ** 2 + (7.0 / 2.0) * n - 4)\n",
    "print 'Tiempo promedio teorico, ' + str((3.0/4.0)*n**2 + (17.0/4.0)*n - 4)\n",
    "print 'Mejor tiempo experimental, ' + str(best)\n",
    "print 'Peor tiempo experimental, ' + str(worst)\n",
    "print 'Tiempo promedio experimental, ' + str(suma / contador)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}