Code.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Gj7qIkK42LmB"
   },
   "source": [
    "# Importing All Libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "id": "xqH51h1g2N6q"
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "import csv\n",
    "import random\n",
    "import math\n",
    "from datetime import datetime\n",
    "import multiprocessing\n",
    "import concurrent.futures\n",
    "import matplotlib.pyplot as plt\n",
    "sys.setrecursionlimit(1000000000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "tqSang4y1rbX"
   },
   "source": [
    "# Generating Datasets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "id": "X4kkYlea1tth"
   },
   "outputs": [],
   "source": [
    "def generate_data(size,filename):\n",
    "  try:\n",
    "    data = [int(i) for i in range(1,size+1)]\n",
    "    random.shuffle(data)\n",
    "    f = open('Datasets/'+filename,'w')\n",
    "    for ele in data:\n",
    "      f.write(str(ele))\n",
    "      f.write('\\n')\n",
    "  except:\n",
    "    print('Error Generating ',filename)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "tyT268443uhb",
    "outputId": "1f8844ea-33d4-45e9-dfe4-89c9b0f5216d"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Generating Data Begin\n",
      "Generating Data Done\n",
      "Time Elapsed (Seconds) To Generate Data :  171.467131\n"
     ]
    }
   ],
   "source": [
    "print('Generating Data Begin')\n",
    "start = datetime.now()\n",
    "with concurrent.futures.ProcessPoolExecutor() as executor:\n",
    "  executor.submit(generate_data,100000,'HundredThousand.csv')\n",
    "  executor.submit(generate_data,1000000,'OneMillion.csv')\n",
    "  executor.submit(generate_data,10000000,'TenMillion.csv')\n",
    "  executor.submit(generate_data,50000000,'FiftyMillion.csv')\n",
    "  executor.submit(generate_data,100000000,'HundredMillion.csv')\n",
    "end = datetime.now()\n",
    "print('Generating Data Done')\n",
    "time = end - start\n",
    "print('Time Elapsed (Seconds) To Generate Data : ',time.total_seconds())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "bHWPHdsK2ovp"
   },
   "source": [
    "# Importing Datasets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "giFpkOVW2ppz"
   },
   "outputs": [],
   "source": [
    "def read_data(filename):\n",
    "    try:\n",
    "        with open('Datasets/'+filename, newline='\\n') as f:\n",
    "            reader = csv.reader(f)\n",
    "            data = list(reader)\n",
    "            data = [int(i[0]) for i in data]\n",
    "    except:\n",
    "        data = []\n",
    "    return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "yr2gOMCM3zTT",
    "outputId": "53fcc90c-6432-40dc-f04e-f53dddde8e24"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Importing Datasets\n",
      "Time Elapsed (Seconds) To Import Data :  94.089241\n"
     ]
    }
   ],
   "source": [
    "print('Importing Datasets')\n",
    "start = datetime.now()\n",
    "with concurrent.futures.ProcessPoolExecutor() as executor:\n",
    "  ht = executor.submit(read_data,'HundredThousand.csv')\n",
    "  om = executor.submit(read_data,'OneMillion.csv')\n",
    "  tm = executor.submit(read_data,'TenMillion.csv')\n",
    "  fm = executor.submit(read_data,'FiftyMillion.csv')\n",
    "  hm = executor.submit(read_data,'HundredMillion.csv')\n",
    "  HundredThousand = ht.result()\n",
    "  OneMillion = om.result()\n",
    "  TenMillion = tm.result()\n",
    "  FiftyMillion = fm.result()\n",
    "  HundredMillion = hm.result()\n",
    "end = datetime.now()\n",
    "time = end - start\n",
    "print('Time Elapsed (Seconds) To Import Data : ',time.total_seconds())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "vVKijpG118U6"
   },
   "source": [
    "# Quick Sort & Merge Sort Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "id": "WA8O__1n1__-"
   },
   "outputs": [],
   "source": [
    "'''\n",
    "Quick Sort\n",
    "'''\n",
    "def sub_partition(array, start, end, idx_pivot):\n",
    "    'returns the position where the pivot winds up'\n",
    "    if not (start <= idx_pivot <= end):\n",
    "        raise ValueError('idx pivot must be between start and end')\n",
    "    array[start], array[idx_pivot] = array[idx_pivot], array[start]\n",
    "    pivot = array[start]\n",
    "    i = start + 1\n",
    "    j = start + 1\n",
    "    while j <= end:\n",
    "        if array[j] <= pivot:\n",
    "            array[j], array[i] = array[i], array[j]\n",
    "            i += 1\n",
    "        j += 1\n",
    "    array[start], array[i - 1] = array[i - 1], array[start]\n",
    "    return i - 1\n",
    "\n",
    "def quickSort(array, process, thread, start=0, end=None):\n",
    "    if end is None:\n",
    "        end = len(array) - 1\n",
    "    if end - start < 1:\n",
    "        return\n",
    "    idx_pivot = random.randint(start, end)\n",
    "    i = sub_partition(array, start, end, idx_pivot)\n",
    "    #print array, i, idx_pivot\n",
    "    if process == True and thread==True:\n",
    "      with concurrent.futures.ThreadPoolExecutor() as executor:\n",
    "        executor.submit(quickSort,array,False,True, start, i - 1)\n",
    "        executor.submit(quickSort,array,False,True, i + 1, end)\n",
    "    elif process == False and thread==True:\n",
    "      with concurrent.futures.ThreadPoolExecutor() as executor:\n",
    "        executor.submit(quickSort,array,False,False, start, i - 1)\n",
    "        executor.submit(quickSort,array,False,False, i + 1, end)\n",
    "    elif process==False and thread==False:\n",
    "      quickSort(array,False,False, start, i - 1)\n",
    "      quickSort(array,False,False, i + 1, end)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "id": "AUr4vEAu33ur"
   },
   "outputs": [],
   "source": [
    "'''\n",
    "Sequential Merge Sort\n",
    "'''\n",
    "def mergeSort(myList):\n",
    "    if len(myList) > 1:\n",
    "        mid = len(myList) // 2\n",
    "        left = myList[:mid]\n",
    "        right = myList[mid:]\n",
    "        mergeSort(left)\n",
    "        mergeSort(right)\n",
    "        # Two iterators for traversing the two halves\n",
    "        i = 0\n",
    "        j = 0\n",
    "        # Iterator for the main list\n",
    "        k = 0\n",
    "        while i < len(left) and j < len(right):\n",
    "            if left[i] <= right[j]:\n",
    "              # The value from the left half has been used\n",
    "              myList[k] = left[i]\n",
    "              # Move the iterator forward\n",
    "              i += 1\n",
    "            else:\n",
    "                myList[k] = right[j]\n",
    "                j += 1\n",
    "            # Move to the next slot\n",
    "            k += 1\n",
    "        # For all the remaining values\n",
    "        while i < len(left):\n",
    "            myList[k] = left[i]\n",
    "            i += 1\n",
    "            k += 1\n",
    "        while j < len(right):\n",
    "            myList[k]=right[j]\n",
    "            j += 1\n",
    "            k += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "id": "elRb1CLT-Kzw"
   },
   "outputs": [],
   "source": [
    "'''\n",
    "Parallel Merge Sort\n",
    "'''\n",
    "def merge(*args):\n",
    "    left, right = args[0] if len(args) == 1 else args\n",
    "    left_length, right_length = len(left), len(right)\n",
    "    left_index, right_index = 0, 0\n",
    "    merged = []\n",
    "    while left_index < left_length and right_index < right_length:\n",
    "        if left[left_index] <= right[right_index]:\n",
    "            merged.append(left[left_index])\n",
    "            left_index += 1\n",
    "        else:\n",
    "            merged.append(right[right_index])\n",
    "            right_index += 1\n",
    "    if left_index == left_length:\n",
    "        merged.extend(right[right_index:])\n",
    "    else:\n",
    "        merged.extend(left[left_index:])\n",
    "    return merged\n",
    "\n",
    "def merge_sort(data):\n",
    "    length = len(data)\n",
    "    if length <= 1:\n",
    "        return data\n",
    "    middle = length // 2\n",
    "    left = merge_sort(data[:middle])\n",
    "    right = merge_sort(data[middle:])\n",
    "    return merge(left, right)\n",
    "\n",
    "def merge_sort_parallel(data):\n",
    "    processes = multiprocessing.cpu_count()\n",
    "    pool = multiprocessing.Pool(processes=processes)\n",
    "    size = int(math.ceil(float(len(data)) / processes))\n",
    "    data = [data[i * size:(i + 1) * size] for i in range(processes)]\n",
    "    data = pool.map(merge_sort, data)\n",
    "    while len(data) > 1:\n",
    "        extra = data.pop() if len(data) % 2 == 1 else None\n",
    "        data = [(data[i], data[i + 1]) for i in range(0, len(data), 2)]\n",
    "        data = pool.map(merge, data) + ([extra] if extra else [])\n",
    "    return data[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "F3HskUN93HU8"
   },
   "source": [
    "# Execute Merge Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "8Y2qLI523Ldt",
    "outputId": "76aec9a3-6a8c-44b8-c7af-5de48e293560"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sequential Merge Sort HundredThousand Begin\n",
      "Sequential Merge Sort HundredThousand Done\n",
      "Sequential Merge Sort OneMillion Begin\n",
      "Sequential Merge Sort OneMillion Done\n",
      "Sequential Merge Sort TenMillion Begin\n",
      "Sequential Merge Sort TenMillion Done\n",
      "Sequential Merge Sort FiftyMillion Begin\n",
      "Sequential Merge Sort FiftyMillion Done\n",
      "Sequential Merge Sort HundredMillion Begin\n",
      "Sequential Merge Sort HundredMillion Done\n",
      "Sequential Merge Sort :  {'HundredThousand': 0.583653, 'OneMillion': 7.177781, 'TenMillion': 88.373841, 'FiftyMillion': 502.488433, 'HundredMillion': 1058.762693} \n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Sequential Merge Sort\n",
    "Merge_Sequential = {}\n",
    "try:\n",
    "  print('Sequential Merge Sort HundredThousand Begin')\n",
    "  data = HundredThousand.copy()\n",
    "  start = datetime.now()\n",
    "  mergeSort(data)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Merge_Sequential['HundredThousand'] = time.total_seconds()\n",
    "  print('Sequential Merge Sort HundredThousand Done')\n",
    "except:\n",
    "  Merge_Sequential['HundredThousand'] = 0\n",
    "  print('Sequential Merge Sort HundredThousand Failed')\n",
    "try:\n",
    "  print('Sequential Merge Sort OneMillion Begin')\n",
    "  data = OneMillion.copy()\n",
    "  start = datetime.now()\n",
    "  mergeSort(data)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Merge_Sequential['OneMillion'] = time.total_seconds()\n",
    "  print('Sequential Merge Sort OneMillion Done')\n",
    "except:\n",
    "  Merge_Sequential['OneMillion'] = 0\n",
    "  print('Sequential Merge Sort OneMillion Failed')\n",
    "try:\n",
    "  print('Sequential Merge Sort TenMillion Begin')\n",
    "  data = TenMillion.copy()\n",
    "  start = datetime.now()\n",
    "  mergeSort(data)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Merge_Sequential['TenMillion'] = time.total_seconds()\n",
    "  print('Sequential Merge Sort TenMillion Done')\n",
    "except:\n",
    "  Merge_Sequential['TenMillion'] = 0\n",
    "  print('Sequential Merge Sort TenMillion Failed')\n",
    "try:\n",
    "  print('Sequential Merge Sort FiftyMillion Begin')\n",
    "  data = FiftyMillion.copy()\n",
    "  start = datetime.now()\n",
    "  mergeSort(data)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Merge_Sequential['FiftyMillion'] = time.total_seconds()\n",
    "  print('Sequential Merge Sort FiftyMillion Done')\n",
    "except:\n",
    "  Merge_Sequential['FiftyMillion'] = 0\n",
    "  print('Sequential Merge Sort FiftyMillion Failed')\n",
    "try:\n",
    "  print('Sequential Merge Sort HundredMillion Begin')\n",
    "  data = HundredMillion.copy()\n",
    "  start = datetime.now()\n",
    "  mergeSort(data)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Merge_Sequential['HundredMillion'] = time.total_seconds()\n",
    "  print('Sequential Merge Sort HundredMillion Done')\n",
    "except:\n",
    "  Merge_Sequential['HundredMillion'] = 0\n",
    "print('Sequential Merge Sort : ',Merge_Sequential,'\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "YRZcghQN4ENM",
    "outputId": "22646000-9b91-4f50-8d99-ff0db0215417"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parallel Merge Sort HundredThousand Begin\n",
      "Parallel Merge Sort HundredThousand Done\n",
      "Parallel Merge Sort OneMillion Begin\n",
      "Parallel Merge Sort OneMillion Done\n",
      "Parallel Merge Sort TenMillion Begin\n",
      "Parallel Merge Sort TenMillion Done\n",
      "Parallel Merge Sort FiftyMillion Begin\n",
      "Parallel Merge Sort FiftyMillion Done\n",
      "Parallel Merge Sort HundredMillion Begin\n",
      "Parallel Merge Sort HundredMillion Done\n",
      "Parallel Merge Sort :  {'HundredThousand': 3.518121, 'OneMillion': 5.150112, 'TenMillion': 63.922264, 'FiftyMillion': 364.765004, 'HundredMillion': 773.553118} \n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Parallel Merge Sort\n",
    "Merge_Parallel = {}\n",
    "try:\n",
    "  print('Parallel Merge Sort HundredThousand Begin')\n",
    "  data = HundredThousand.copy()\n",
    "  start = datetime.now()\n",
    "  merge_sort(data)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Merge_Parallel['HundredThousand'] = time.total_seconds()\n",
    "  print('Parallel Merge Sort HundredThousand Done')\n",
    "except:\n",
    "  Merge_Parallel['HundredThousand'] = 0\n",
    "  print('Parallel Merge Sort HundredThousand Failed')\n",
    "try:\n",
    "  print('Parallel Merge Sort OneMillion Begin')\n",
    "  data = OneMillion.copy()\n",
    "  start = datetime.now()\n",
    "  merge_sort(data)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Merge_Parallel['OneMillion'] = time.total_seconds()\n",
    "  print('Parallel Merge Sort OneMillion Done')\n",
    "except:\n",
    "  Merge_Parallel['OneMillion'] = 0\n",
    "  print('Parallel Merge Sort OneMillion Failed')\n",
    "try:\n",
    "  print('Parallel Merge Sort TenMillion Begin')\n",
    "  data = TenMillion.copy()\n",
    "  start = datetime.now()\n",
    "  merge_sort(data)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Merge_Parallel['TenMillion'] = time.total_seconds()\n",
    "  print('Parallel Merge Sort TenMillion Done')\n",
    "except:\n",
    "  Merge_Parallel['TenMillion'] = 0\n",
    "  print('Parallel Merge Sort TenMillion Failed')\n",
    "try:\n",
    "  print('Parallel Merge Sort FiftyMillion Begin')\n",
    "  data = FiftyMillion.copy()\n",
    "  start = datetime.now()\n",
    "  merge_sort(data)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Merge_Parallel['FiftyMillion'] = time.total_seconds()\n",
    "  print('Parallel Merge Sort FiftyMillion Done')\n",
    "except:\n",
    "  Merge_Parallel['FiftyMillion'] = 0\n",
    "  print('Parallel Merge Sort FiftyMillion Failed')\n",
    "try:\n",
    "  print('Parallel Merge Sort HundredMillion Begin')\n",
    "  data = HundredMillion.copy()\n",
    "  start = datetime.now()\n",
    "  merge_sort(data)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Merge_Parallel['HundredMillion'] = time.total_seconds()\n",
    "  print('Parallel Merge Sort HundredMillion Done')\n",
    "except:\n",
    "  Merge_Parallel['HundredMillion'] = 0\n",
    "  print('Parallel Merge Sort HundredMillion Failed')\n",
    "print('Parallel Merge Sort : ',Merge_Parallel,'\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "2BXM6SSN3aWd"
   },
   "source": [
    "# Execute Quick Sort\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "HPxvI6yt3cUE",
    "outputId": "fdff463a-366d-4c4f-d56e-6eafa0c17309"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sequential Quick Sort HundredThousand Begin\n",
      "Sequential Quick Sort HundredThousand Done\n",
      "Sequential Quick Sort OneMillion Begin\n",
      "Sequential Quick Sort OneMillion Done\n",
      "Sequential Quick Sort TenMillion Begin\n",
      "Sequential Quick Sort TenMillion Done\n",
      "Sequential Quick Sort FiftyMillion Begin\n",
      "Sequential Quick Sort FiftyMillion Done\n",
      "Sequential Quick Sort HundredMillion Begin\n",
      "Sequential Quick Sort HundredMillion Done\n",
      "Sequential Quick Sort :  {'HundredThousand': 0.86409, 'OneMillion': 5.759202, 'TenMillion': 73.573393, 'FiftyMillion': 431.178253, 'HundredMillion': 908.592036} \n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Sequential Quick Sort\n",
    "Quick_Sequential = {}\n",
    "try:\n",
    "  print('Sequential Quick Sort HundredThousand Begin')\n",
    "  data = HundredThousand.copy()\n",
    "  start = datetime.now()\n",
    "  quickSort(data,False,False)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Quick_Sequential['HundredThousand'] = time.total_seconds()\n",
    "  print('Sequential Quick Sort HundredThousand Done')\n",
    "except:\n",
    "  Quick_Sequential['HundredThousand'] = 0\n",
    "  print('Sequential Quick Sort HundredThousand Failed')\n",
    "try:\n",
    "  print('Sequential Quick Sort OneMillion Begin')\n",
    "  data = OneMillion.copy()\n",
    "  start = datetime.now()\n",
    "  quickSort(data,False,False)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Quick_Sequential['OneMillion'] = time.total_seconds()\n",
    "  print('Sequential Quick Sort OneMillion Done')\n",
    "except:\n",
    "  Quick_Sequential['OneMillion'] = 0\n",
    "  print('Sequential Quick Sort OneMillion Failed')\n",
    "try:\n",
    "  print('Sequential Quick Sort TenMillion Begin')\n",
    "  data = TenMillion.copy()\n",
    "  start = datetime.now()\n",
    "  quickSort(data,False,False)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Quick_Sequential['TenMillion'] = time.total_seconds()\n",
    "  print('Sequential Quick Sort TenMillion Done')\n",
    "except:\n",
    "  Quick_Sequential['TenMillion'] = 0\n",
    "  print('Sequential Quick Sort TenMillion Failed')\n",
    "try:\n",
    "  print('Sequential Quick Sort FiftyMillion Begin')\n",
    "  data = FiftyMillion.copy()\n",
    "  start = datetime.now()\n",
    "  quickSort(data,False,False)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Quick_Sequential['FiftyMillion'] = time.total_seconds()\n",
    "  print('Sequential Quick Sort FiftyMillion Done')\n",
    "except:\n",
    "  Quick_Sequential['FiftyMillion'] = 0\n",
    "  print('Sequential Quick Sort FiftyMillion Failed')\n",
    "try:\n",
    "  print('Sequential Quick Sort HundredMillion Begin')\n",
    "  data = HundredMillion.copy()\n",
    "  start = datetime.now()\n",
    "  quickSort(data,False,False)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Quick_Sequential['HundredMillion'] = time.total_seconds()\n",
    "  print('Sequential Quick Sort HundredMillion Done')\n",
    "except:\n",
    "  Quick_Sequential['HundredMillion'] = 0\n",
    "  print('Sequential Quick Sort HundredMillion Failed')\n",
    "print('Sequential Quick Sort : ',Quick_Sequential,'\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "VMwppoIE4SLR",
    "outputId": "85c3cdf9-cc34-406e-ac2d-f2cd27672a85"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parallel Quick Sort HundredThousand Begin\n",
      "Parallel Quick Sort HundredThousand Done\n",
      "Parallel Quick Sort OneMillion Begin\n",
      "Parallel Quick Sort OneMillion Done\n",
      "Parallel Quick Sort TenMillion Begin\n",
      "Parallel Quick Sort TenMillion Done\n",
      "Parallel Quick Sort FiftyMillion Begin\n",
      "Parallel Quick Sort FiftyMillion Done\n",
      "Parallel Quick Sort HundredMillion Begin\n",
      "Parallel Quick Sort HundredMillion Done\n",
      "Parallel Quick Sort :  {'HundredThousand': 8.379572, 'OneMillion': 5.792294, 'TenMillion': 78.166659, 'FiftyMillion': 440.790708, 'HundredMillion': 939.984868} \n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Parallel Quick Sort\n",
    "Quick_Parallel = {}\n",
    "try:\n",
    "  print('Parallel Quick Sort HundredThousand Begin')\n",
    "  data = HundredThousand.copy()\n",
    "  start = datetime.now()\n",
    "  quickSort(data,True,True)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Quick_Parallel['HundredThousand'] = time.total_seconds()\n",
    "  print('Parallel Quick Sort HundredThousand Done')\n",
    "except:\n",
    "  Quick_Parallel['HundredThousand'] = 0\n",
    "  print('Parallel Quick Sort HundredThousand Failed')\n",
    "try:\n",
    "  print('Parallel Quick Sort OneMillion Begin')\n",
    "  data = OneMillion.copy()\n",
    "  start = datetime.now()\n",
    "  quickSort(data,True,True)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Quick_Parallel['OneMillion'] = time.total_seconds()\n",
    "  print('Parallel Quick Sort OneMillion Done')\n",
    "except:\n",
    "  Quick_Parallel['OneMillion'] = 0\n",
    "  print('Parallel Quick Sort OneMillion Failed')\n",
    "try:\n",
    "  print('Parallel Quick Sort TenMillion Begin')\n",
    "  data = TenMillion.copy()\n",
    "  start = datetime.now()\n",
    "  quickSort(data,True,True)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Quick_Parallel['TenMillion'] = time.total_seconds()\n",
    "  print('Parallel Quick Sort TenMillion Done')\n",
    "except:\n",
    "  Quick_Parallel['TenMillion'] = 0\n",
    "  print('Parallel Quick Sort TenMillion Failed')\n",
    "try:\n",
    "  print('Parallel Quick Sort FiftyMillion Begin')\n",
    "  data = FiftyMillion.copy()\n",
    "  start = datetime.now()\n",
    "  quickSort(data,True,True)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Quick_Parallel['FiftyMillion'] = time.total_seconds()\n",
    "  print('Parallel Quick Sort FiftyMillion Done')\n",
    "except:\n",
    "  Quick_Parallel['FiftyMillion'] = 0\n",
    "  print('Parallel Quick Sort FiftyMillion Failed')\n",
    "try:\n",
    "  print('Parallel Quick Sort HundredMillion Begin')\n",
    "  data = HundredMillion.copy()\n",
    "  start = datetime.now()\n",
    "  quickSort(data,True,True)\n",
    "  end = datetime.now()\n",
    "  time = end - start\n",
    "  del data\n",
    "  Quick_Parallel['HundredMillion'] = time.total_seconds()\n",
    "  print('Parallel Quick Sort HundredMillion Done')\n",
    "except:\n",
    "  Quick_Parallel['HundredMillion'] = 0\n",
    "  print('Parallel Quick Sort HundredMillion Failed')\n",
    "print('Parallel Quick Sort : ',Quick_Parallel,'\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "N12-ymA54XJ_"
   },
   "source": [
    "# Plotting the Results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "edp4akd140Rb",
    "outputId": "fa155424-54f8-4b07-b327-e687f05d86cb"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Plotting and Exporting Begin\n"
     ]
    }
   ],
   "source": [
    "print('Plotting and Exporting Begin')\n",
    "\n",
    "x = ['100K','1M','10M','50M','100M']\n",
    "y0 = [0 for _ in range(len(x))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "id": "Q5R7wru44jyJ"
   },
   "outputs": [],
   "source": [
    "# Quick Sort Metrics\n",
    "Quick_Sequential = [Quick_Sequential['HundredThousand'],Quick_Sequential['OneMillion'],Quick_Sequential['TenMillion'],Quick_Sequential['FiftyMillion'],Quick_Sequential['HundredMillion']]\n",
    "Quick_Parallel = [Quick_Parallel['HundredThousand'],Quick_Parallel['OneMillion'],Quick_Parallel['TenMillion'],Quick_Parallel['FiftyMillion'],Quick_Parallel['HundredMillion']]\n",
    "\n",
    "# Merge Sort Metrics\n",
    "Merge_Sequential = [Merge_Sequential['HundredThousand'],Merge_Sequential['OneMillion'],Merge_Sequential['TenMillion'],Merge_Sequential['FiftyMillion'],Merge_Sequential['HundredMillion']]\n",
    "Merge_Parallel = [Merge_Parallel['HundredThousand'],Merge_Parallel['OneMillion'],Merge_Parallel['TenMillion'],Merge_Parallel['FiftyMillion'],Merge_Parallel['HundredMillion']]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 51
    },
    "id": "l9gw_eSOLF43",
    "outputId": "97bdc082-01cc-4ddd-b8df-0c92deeecd92"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "MergeSort.png Exported\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<Figure size 432x288 with 0 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Plotting Merge Sort Metrics\n",
    "plt.plot(x, Merge_Sequential, color='blue', label='Sequential Merge Sort')\n",
    "plt.plot(x, Merge_Parallel, color='green', label='Parallel Merge Sort')\n",
    "plt.xlabel('Number of Integers to Sort')\n",
    "plt.ylabel('Time Taken in Seconds')\n",
    "plt.legend()\n",
    "plt.title('Execution Time of Merge Sort Algorithms')\n",
    "plt.savefig('Plots/MergeSort.png', dpi=150)\n",
    "print('MergeSort.png Exported')\n",
    "plt.clf()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 51
    },
    "id": "guxQC4w94_U8",
    "outputId": "f2032992-c3ac-4a91-8adc-d90f204cf651"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "QuickSort.png Exported\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<Figure size 432x288 with 0 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Plotting Quick Sort Metrics\n",
    "plt.plot(x, Quick_Sequential, color='blue', linestyle='dotted', label='Sequential Quick Sort')\n",
    "plt.plot(x, Quick_Parallel, color='green', linestyle='dotted', label='Parallel Quick Sort')\n",
    "plt.xlabel('Number of Integers to Sort')\n",
    "plt.ylabel('Time Taken in Seconds')\n",
    "plt.legend()\n",
    "plt.title('Execution Time of Quick Sort Algorithms')\n",
    "plt.savefig('Plots/QuickSort.png', dpi=150)\n",
    "print('QuickSort.png Exported')\n",
    "plt.clf()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 51
    },
    "id": "A5owA-dE4Zgb",
    "outputId": "77738d3d-eeb7-4097-ef3c-d9a06dea60be"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sort.png Exported\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<Figure size 432x288 with 0 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Plotting All Metrics In One Graph\n",
    "plt.plot(x, Quick_Sequential, color='blue', linestyle='dotted', label='Sequential Quick Sort')\n",
    "plt.plot(x, Quick_Parallel, color='green', linestyle='dotted', label='Parallel Quick Sort')\n",
    "plt.plot(x, Merge_Sequential, color='blue', label='Sequential Merge Sort')\n",
    "plt.plot(x, Merge_Parallel, color='green', label='Parallel Merge Sort')\n",
    "plt.xlabel('Number of Integers to Sort')\n",
    "plt.ylabel('Time Taken in Seconds')\n",
    "plt.legend()\n",
    "plt.title('Execution Time of All Sorting Algorithms')\n",
    "plt.savefig('Plots/Sort.png', dpi=150)\n",
    "print('Sort.png Exported')\n",
    "plt.clf()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "id": "KqDKF4tw4NBH"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [
    "Gj7qIkK42LmB",
    "tqSang4y1rbX",
    "bHWPHdsK2ovp",
    "vVKijpG118U6",
    "F3HskUN93HU8",
    "2BXM6SSN3aWd",
    "N12-ymA54XJ_"
   ],
   "name": "CS5350.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}