{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyOXCUxue3l/rW2zf/IDiTD+",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/financieras/campus/blob/main/pilas/Radix_Sort.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0t6k2WKKkXjH",
        "outputId": "c4cac6c4-4e04-4e54-d302-e574188ff4b0"
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[2, 24, 45, 66, 75, 90, 170, 802]"
            ]
          },
          "metadata": {},
          "execution_count": 1
        }
      ],
      "source": [
        "# https://www.geeksforgeeks.org/radix-sort\n",
        "# Python program for implementation of Radix Sort\n",
        "# A function to do counting sort of arr[] according to the digit represented by exp.\n",
        "\n",
        "def countingSort(arr, exp1):\n",
        "    n = len(arr)\n",
        "    output = [0]*n   # inicializamos el vector de salida ya ordenado    \n",
        "    count = [0]*10   # inicializamos un contador en forma de array\n",
        "\n",
        "    # Store count of occurrences in count[]\n",
        "    for i in range(0, n):\n",
        "        index = arr[i] // exp1\n",
        "        count[index % 10] += 1\n",
        "\n",
        "    # Change count[i] so that count[i] now contains actual\n",
        "    # position of this digit in output array\n",
        "    for i in range(1, 10):\n",
        "        count[i] += count[i - 1]\n",
        "  \n",
        "    # Build the output array\n",
        "    i = n - 1\n",
        "    while i >= 0:\n",
        "        index = arr[i] // exp1\n",
        "        output[count[index % 10] - 1] = arr[i]\n",
        "        count[index % 10] -= 1\n",
        "        i -= 1\n",
        "  \n",
        "    # Copying the output array to arr[],\n",
        "    # so that arr now contains sorted numbers\n",
        "    i = 0\n",
        "    for i in range(0, len(arr)):\n",
        "        arr[i] = output[i]\n",
        "  \n",
        "# Method to do Radix Sort\n",
        "def radixSort(arr):\n",
        "  \n",
        "    # buscando el número máximo para saber el número de dígitos\n",
        "    max1 = max(arr)\n",
        "  \n",
        "    # Do counting sort for every digit. \n",
        "    # Note that instead of passing digit number, exp is passed. exp is 10^i where i is current digit number\n",
        "    exp = 1\n",
        "    while max1 / exp >= 1:\n",
        "        countingSort(arr, exp)\n",
        "        exp *= 10\n",
        "  \n",
        "  \n",
        "\n",
        "arr = [170, 45, 75, 90, 802, 24, 2, 66]\n",
        "radixSort(arr)\n",
        "arr"
      ]
    }
  ]
}