divide-and-conquer for quicksort-for comparison-bubblesort-for github.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Computer Science: Divide and Conquer: Quicksort from scratch in Python\n",
    "###### by Hamed Shah-Hosseini\n",
    "Explanation in English: https://www.pinterest.com/HamedShahHosseini/\n",
    "<br>Explanation in Persian: https://www.instagram.com/words.persian\n",
    "<br> Python code at: https://github.com/ostad-ai/Computer-Science"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randrange\n",
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# bubblesort, we compare every two adjacent elements,\n",
    "# and swap them, if necessary\n",
    "def bubblesort(items):\n",
    "    n=len(items)\n",
    "    while True:\n",
    "        swapped=False\n",
    "        for i in range(1,n):\n",
    "            if items[i-1]>items[i]:\n",
    "                items[i-1],items[i]=items[i],items[i-1]\n",
    "                swapped=True\n",
    "        if swapped is False: break\n",
    "        else: n-=1\n",
    "    return items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Divide and Conquer for Quicksort\n",
    "# Here, pivot element is chosen randomly\n",
    "#   from the items of the given list\n",
    "# We could simply choose the first element \n",
    "#   of the list as pivot element\n",
    "def quicksort(items):\n",
    "    if len(items)<=1:\n",
    "        sorted_items=items\n",
    "    else:\n",
    "        pivot=items[randrange(0,len(items))]\n",
    "        lessthans=[]\n",
    "        greaterthans=[]\n",
    "        equals=[]\n",
    "        for item in items:\n",
    "            if item<pivot:\n",
    "                lessthans.append(item)\n",
    "            elif item>pivot:\n",
    "                greaterthans.append(item)\n",
    "            else:\n",
    "                equals.append(item)\n",
    "        sorted_items=quicksort(lessthans)+\\\n",
    "            equals+quicksort(greaterthans)\n",
    "    return sorted_items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Quicksort demo.:\n",
      "given list:  [3, 2, 14, -7, 0, 32, -3]\n",
      "sorted list: [-7, -3, 0, 2, 3, 14, 32]\n"
     ]
    }
   ],
   "source": [
    "# A simple example for quicksort\n",
    "items=[3,2,14,-7,0,32,-3]\n",
    "print('Quicksort demo.:')\n",
    "print(f'given list:  {items}')\n",
    "print(f'sorted list: {quicksort(items)}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Time to complete for Quicksort in seconds:  0.06200289726257324\n",
      "Time to complete for Bubblesort in seconds: 14.776024341583252\n"
     ]
    }
   ],
   "source": [
    "# Time comparison between Quicksort and Bubblesort\n",
    "items=[randrange(0,100000) for _ in range(10000)]\n",
    "start=time.time()\n",
    "quicksort(items) # it doesn't change items\n",
    "end=time.time()\n",
    "print(f'Time to complete for Quicksort in seconds:  {end-start}')\n",
    "start=time.time()\n",
    "bubblesort(items) # it does change items\n",
    "end=time.time()\n",
    "print(f'Time to complete for Bubblesort in seconds: {end-start}')"
   ]
  },
  {
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}