03 - Counting Sort.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 03 - Counting Sort\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Counting Sort is a sorting algorithm, which means it sorts a list of numbers L from smallest to largest and returns the sorted list S. Here, we restrict ourselves to positive integers (including 0) that have a known maximum value m."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Counting Sort first creates a list C of all potential values (0 to m) and counts for each value how often it occurs in the original list L. Then it goes through this list of counts C and adds each value the appropriate number of times to the sorted list S, which is returned."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We want you to implement the given Counting Sort pseudocode in Python:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<pre>\n",
    "def counting sort(L, m):\n",
    "    initialize S as an empty list\n",
    "    initialize a list C of length m + 1 with every value being 0\n",
    "    for every value v in L do:\n",
    "        Cv ← Cv + 1\n",
    "    for every value c at index i in C do:\n",
    "        do c times:\n",
    "            append the value i to S\n",
    "    return S\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Note:__ Cv is the value of the element at index v in list C."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 9, 2, 4, 1, 1, 5, 1, 0, 0, 9]\n",
      "[2, 3, 1, 0, 2, 1, 0, 0, 0, 2]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[0, 0, 1, 1, 1, 2, 4, 4, 5, 9, 9]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# your code\n",
    "# option 1\n",
    "def counting_sort(L, m):\n",
    "    S = []\n",
    "    C = [0] * (m+1)\n",
    "    print(L)\n",
    "    for v in L:\n",
    "        C[v] = C[v] + 1   # C \n",
    "    print(C)\n",
    "    for i in range( len(C) ):\n",
    "        for j in range( C[i] ):\n",
    "            S.append( i )\n",
    "    return S\n",
    "    \n",
    "    \n",
    "counting_sort([4, 9, 2, 4, 1, 1, 5, 1, 0, 0, 9], 9)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 1, 1, 1, 2, 4, 4, 5, 9, 9]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# option 2\n",
    "\n",
    "def counting_sort(L, m):\n",
    "    S = []\n",
    "    C = [0] * (m+1)\n",
    "    for v in L:\n",
    "        C[v] = C[v] + 1   # C \n",
    "    j = 0\n",
    "    for i in C:\n",
    "        while i>0:\n",
    "            S.append( j ) \n",
    "            i = i-1\n",
    "        j = j+1\n",
    "    return S\n",
    "    \n",
    "counting_sort([4, 9, 2, 4, 1, 1, 5, 1, 0, 0, 9], 9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Test your implementation with the list `[4, 9, 2, 4, 1, 1, 5, 1, 0, 0, 9]`, which has a maximum value of 9."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 1, 1, 1, 2, 4, 4, 5, 9, 9]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# your code\n",
    "counting_sort([4, 9, 2, 4, 1, 1, 5, 1, 0, 0, 9], 9)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "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.9.12 (main, Apr  4 2022, 05:22:27) [MSC v.1916 64 bit (AMD64)]"
  },
  "vscode": {
   "interpreter": {
    "hash": "8d4e63f1bd948baef4bc278445c31d443b4c6d00105819e06ca43613e036dceb"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}