Counting Sort Algo

Counting Sort.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unsorted List\n",
      "[12, 13, 1, 8, 16, 15, 12, 9, 15, 11]\n",
      "\n",
      "Sorted list using basic counting sort\n",
      "[1, 8, 9, 11, 12, 12, 13, 15, 15, 16]\n"
     ]
    }
   ],
   "source": [
    "import random, math\n",
    "\n",
    "\n",
    "def basic_counting_sort(tlist, k):\n",
    "    \"\"\" Counting sort algo with sort in place. Only for positive integer.\n",
    "        Args: \n",
    "            tlist: target list to sort\n",
    "            k: max value assume known before hand\n",
    "        Disadv:\n",
    "            It only does for positive integer and unable to handle more complex sorting (sort by str, negative integer etc)\n",
    "            It straight away retrieve all data from count_list using count_list index as its ordering.\n",
    "            Do not have the additional step to modify count_list to capture the actual index in output.\n",
    "    \"\"\"\n",
    "    \n",
    "    # Create a count list and using the index to map to the integer in tlist.\n",
    "    count_list = [0]*(k)\n",
    "    \n",
    "    # loop through tlist and increment if exists\n",
    "    for n in tlist:\n",
    "        count_list[n] = count_list[n] + 1\n",
    "    \n",
    "    # Sort in place, copy back into original list\n",
    "    i=0\n",
    "    for n in range(len(count_list)):\n",
    "        while count_list[n] > 0:\n",
    "            tlist[i] = n\n",
    "            i+=1\n",
    "            count_list[n] -= 1\n",
    "            \n",
    "## Create random list for demo counting sort.\n",
    "random.seed(0)\n",
    "tgt_list = [random.randint(0,20) for n in range(10)]\n",
    "print(\"Unsorted List\")\n",
    "print(tgt_list)\n",
    "\n",
    "## Perform the counting sort.\n",
    "print(\"\\nSorted list using basic counting sort\")\n",
    "basic_counting_sort(tgt_list, max(tgt_list)+1)\n",
    "print(tgt_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unsorted List\n",
      "[12, 13, 1, 8, 16, 15, 12, 9, 15, 11]\n",
      "\n",
      "Sorted list using basic counting sort\n",
      "[1, 8, 9, 11, 12, 12, 13, 15, 15, 16]\n"
     ]
    }
   ],
   "source": [
    "import random, math\n",
    "\n",
    "def get_sortkey(n):\n",
    "    \"\"\" Define the method to retrieve the key \"\"\"\n",
    "    return n\n",
    "\n",
    "def counting_sort(tlist, k, get_sortkey):\n",
    "    \"\"\" Counting sort algo with sort in place.\n",
    "        Args: \n",
    "            tlist: target list to sort\n",
    "            k: max value assume known before hand\n",
    "            get_sortkey: function to retrieve the key that is apply to elements of tlist to be used in the count list index.\n",
    "            map info to index of the count list.\n",
    "        Adv:\n",
    "            The count (after cum sum) will hold the actual position of the element in sorted order\n",
    "            Using the above, \n",
    "            \n",
    "    \"\"\"\n",
    "\n",
    "    # Create a count list and using the index to map to the integer in tlist.\n",
    "    count_list = [0]*(k)\n",
    "\n",
    "    # iterate the tgt_list to put into count list\n",
    "    for n in tlist:\n",
    "        count_list[get_sortkey(n)] = count_list[get_sortkey(n)] + 1  \n",
    "        \n",
    "    # Modify count list such that each index of count list is the combined sum of the previous counts \n",
    "    # each index indicate the actual position (or sequence) in the output sequence.\n",
    "    for i in range(k):\n",
    "        if i ==0:\n",
    "            count_list[i] = count_list[i]\n",
    "        else:\n",
    "            count_list[i] += count_list[i-1]\n",
    " \n",
    "\n",
    "    output = [None]*len(tlist)\n",
    "    for i in range(len(tlist)-1, -1, -1):\n",
    "        sortkey = get_sortkey(tlist[i])\n",
    "        output[count_list[sortkey]-1] = tlist[i]\n",
    "        count_list[sortkey] -=1\n",
    "\n",
    "    return output\n",
    "    \n",
    "## Create random list for demo counting sort.\n",
    "random.seed(0)\n",
    "tgt_list = [random.randint(0,20) for n in range(10)]\n",
    "print(\"Unsorted List\")\n",
    "print(tgt_list)\n",
    "\n",
    "## Perform the counting sort.\n",
    "print(\"\\nSorted list using basic counting sort\")\n",
    "output = counting_sort(tgt_list, max(tgt_list) +1, get_sortkey) # assumption is known the max value in tgtlist  for this case.\n",
    "print(output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unsorted List\n",
      "[-1, 13, 20, 19, -3, 3, -2, 10, 19, 9]\n",
      "\n",
      "Sorted list using counting sort\n",
      "[-3, -2, -1, 3, 9, 10, 13, 19, 19, 20]\n"
     ]
    }
   ],
   "source": [
    "# try for negative number\n",
    "\n",
    "def get_sortkey2(n):\n",
    "    \"\"\" Define the method to retrieve the key \"\"\"\n",
    "    return n +5\n",
    "\n",
    "\n",
    "## Create random list for demo counting sort.\n",
    "random.seed(1)\n",
    "tgt_list = [random.randint(-5,20) for n in range(10)]\n",
    "print(\"Unsorted List\")\n",
    "print(tgt_list)\n",
    "\n",
    "## Perform the counting sort.\n",
    "print(\"\\nSorted list using counting sort\")\n",
    "output = counting_sort(tgt_list, 30, get_sortkey2)\n",
    "print(output)"
   ]
  },
  {
   "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}