{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### TUTORATO 5 : ALGORITMI DI ORDINAMENTO IN TEMPO LINEARE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### COUNTING SORT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "def counting(A, k):\n",
    "    B = [0] * k # memoria di lavoro temporanea\n",
    "    C = [0] * len(A)  # mantiene l'output ordinato\n",
    "    for i in range(0, len(A)):\n",
    "        # in un array temporaneo di dimensione pari all'intervallo di valori contiamo il numero di occorrenze \n",
    "        # di ciascun valore presente nell'array da ordinare \n",
    "        B[A[i]] += 1\n",
    "    for i in range(1, len(B)):\n",
    "        B[i] = B[i] + B[i-1]\n",
    "    for i in range(len(A)-1, -1, -1):\n",
    "        # poniamo ogni elemento di A[j] nella sua corretta posizione ordinata\n",
    "        C[B[A[i]]-1] = A[i]\n",
    "        B[A[i]] = B[A[i]] - 1\n",
    "    return C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = [1, 3, 3, 1, 2, 2, 7, 7, 12, 0, 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "k = max(A) - min(A) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 1, 1, 2, 2, 3, 3, 7, 7, 12]"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counting(A, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### BUCKET SORT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertion_sort(A):\n",
    "    for i in range(1, len(A)):\n",
    "        j = i\n",
    "        while j > 0 and A[j] < A[j-1]:\n",
    "            A[j], A[j-1] = A[j-1], A[j]\n",
    "            j = j - 1\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bucket_sort(A):\n",
    "    B = []\n",
    "    n = len(A)\n",
    "    for i in range(0, n):\n",
    "        B.append([])\n",
    "    for i in range(0, n):\n",
    "        bucket = int(A[i] * n) \n",
    "        B[bucket].append(A[i])\n",
    "    for i in range(0, n):\n",
    "        B[i] = insertion_sort(B[i])\n",
    "    C = []\n",
    "    for i in range(0, n):\n",
    "        C += B[i]\n",
    "    return C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = [0.1, 0.3, 0.3, 0.1, 0.2, 0.2, 0.7, 0.7, 0, 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 0.1, 0.1, 0.2, 0.2, 0.3, 0.3, 0.7, 0.7]"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bucket_sort(A)"
   ]
  },
  {
   "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}