AA1-Sorting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Bubble Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "According to Wikipedia \"Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller elements \"bubble\" to the top of the list. Although the algorithm is simple, it is too slow and impractical for most problems even when compared to insertion sort. It can be practical if the input is usually in sort order but may occasionally have some out-of-order elements nearly in position[1]."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Run time complexity:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "outer loop: $n$\n",
    "\n",
    "Inner loop for each outer: (n-i-1)\n",
    "\n",
    "In worst case:\n",
    "Total : $ \\sum_{i=0}^{n-1} (n-i-1) = n^{2} -   (\\sum_{i=0}^{n-1}i) - n  = n^{2} - \\frac{n(n-1)}{2} - n $\n",
    "\n",
    "$\\mathbb{O}(n^{2})$\n",
    "\n",
    "###### Auxiliary Space: O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt](./pic/bbsort.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Python program for implementation of Bubble Sort\n",
    " \n",
    "def bubbleSort(arr):\n",
    "    n = len(arr)\n",
    " \n",
    "    # Traverse through all array elements\n",
    "    for i in range(n):\n",
    "        \n",
    "        # Last i elements are already in place\n",
    "        for j in range(0, n-i-1):\n",
    "        \n",
    "            # traverse the array from 0 to n-i-1\n",
    "            # Swap if the element found is greater\n",
    "            # than the next element\n",
    "            if arr[j] > arr[j+1]:\n",
    "                arr[j], arr[j+1] = arr[j+1], arr[j]\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[11, 12, 22, 25, 34, 64, 90]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Driver code to test above\n",
    "arr = [64, 34, 25, 12, 22, 11, 90]\n",
    " \n",
    "sortedarr = bubbleSort(arr)\n",
    "sortedarr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Referrences:\n",
    "1. http://www.cs.toronto.edu/~guerzhoy/180/lectures/W10/lec3/BubbleSortCompl.html\n",
    "2. https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-4.php"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2. Insersion Sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "![alt tag](https://media.geeksforgeeks.org/wp-content/uploads/insertionsort.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Python program for implementation of Insertion Sort\n",
    " \n",
    "# Function to do insertion sort\n",
    "def insertionSort(arr):\n",
    " \n",
    "    # Traverse through 1 to len(arr)\n",
    "    for i in range(1, len(arr)):\n",
    " \n",
    "        key = arr[i]\n",
    " \n",
    "        # Move elements of arr[0..i-1], that are\n",
    "        # greater than key, to one position ahead\n",
    "        # of their current position\n",
    "        j = i-1\n",
    "        while j >=0 and key < arr[j] :\n",
    "                arr[j+1] = arr[j]\n",
    "                j -= 1\n",
    "        arr[j+1] = key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted array is:\n",
      "5\n",
      "6\n",
      "11\n",
      "12\n",
      "13\n"
     ]
    }
   ],
   "source": [
    "# Driver code to test above\n",
    "arr = [12, 11, 13, 5, 6]\n",
    "insertionSort(arr)\n",
    "print (\"Sorted array is:\")\n",
    "for i in range(len(arr)):\n",
    "    print (\"%d\" %arr[i])\n",
    " \n",
    "# This code is contributed by Mohit Kumra\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Time Complexity: O(n*n)\n",
    "2. Auxiliary Space: O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "##### References:\n",
    "1. http://www.geeksforgeeks.org/insertion-sort/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 3. The selection sort \n",
    "\n",
    "This algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.\n",
    "\n",
    "1) The subarray which is already sorted.\n",
    "2) Remaining subarray which is unsorted.\n",
    "\n",
    "In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![img](https://www.w3resource.com/w3r_images/selection-short.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Python program for implementation of Selection \n",
    "# Sort \n",
    "import sys \n",
    "A = [64, 25, 12, 22, 11] \n",
    "  \n",
    "# Traverse through all array elements \n",
    "for i in range(len(A)): \n",
    "      \n",
    "    # Find the minimum element in remaining  \n",
    "    # unsorted array \n",
    "    min_idx = i \n",
    "    for j in range(i+1, len(A)): \n",
    "        if A[min_idx] > A[j]: \n",
    "            min_idx = j \n",
    "              \n",
    "    # Swap the found minimum element with  \n",
    "    # the first element         \n",
    "    A[i], A[min_idx] = A[min_idx], A[i] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted array\n",
      "11\n",
      "12\n",
      "22\n",
      "25\n",
      "64\n"
     ]
    }
   ],
   "source": [
    "# Driver code to test above \n",
    "print (\"Sorted array\") \n",
    "for i in range(len(A)): \n",
    "    print(\"%d\" %A[i]),  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### References:\n",
    "1. Latest Algorithm Collection GitHub:https://github.com/TheAlgorithms/Python\n",
    "2. AI search GitHub book:https://github.com/aimacode\n",
    "3. Algorithm Online Book: https://algs4.cs.princeton.edu/home/\n",
    "4. NetworkX documents: https://networkx.github.io/documentation/latest/index.html\n",
    "5. Network Science Online Book: http://networksciencebook.com/"
   ]
  }
 ],
 "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.7.1"
  },
  "widgets": {
   "state": {},
   "version": "1.1.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}