Sorting Algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorting Via Bubble Sort:\n",
      "Random List= [14, 1, 16, 8, 19, 12, 6, 3, 10, 14, 18, 4, 1, 3, 3, 1, 2, 19, 7, 3]\n",
      "Sorted List= [1, 1, 1, 2, 3, 3, 3, 3, 4, 6, 7, 8, 10, 12, 14, 14, 16, 18, 19, 19]\n",
      "Sorting Via Insertion Sort:\n",
      "Random List= [7, 14, 5, 1, 14, 4, 20, 8, 18, 3, 4, 6, 15, 4, 19, 13, 15, 2, 11, 3]\n",
      "Sorted List= [1, 2, 3, 3, 4, 4, 4, 5, 6, 7, 8, 11, 13, 14, 14, 15, 15, 18, 19, 20]\n",
      "Sorting Via Selection Sort:\n",
      "Sorted List= [[1, 2, 3, 3, 4, 4, 4, 5, 6, 7, 8, 11, 13, 14, 14, 15, 15, 18, 19, 20]]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "class sorting:\n",
    "    def __init__(self,lst):\n",
    "        self.lst=lst\n",
    "        \n",
    "# Generating random numbers to sort them\n",
    "        \n",
    "    def GenerateRandom(self,n):\n",
    "        for i in range(n):\n",
    "            x=random.randint(1,n)\n",
    "            self.lst.append(x)\n",
    "        return self.lst\n",
    "    \n",
    "# Bubble Sort \n",
    "\n",
    "    def BubbleSort(self):\n",
    "        n=len(self.lst)\n",
    "        for i in range(n):\n",
    "            for j in range(n-1):\n",
    "                if self.lst[j]>self.lst[j+1]:\n",
    "                    (self.lst[j],self.lst[j+1])=(self.lst[j+1],self.lst[j])\n",
    "        return self.lst  \n",
    "\n",
    "# Insertion Sort\n",
    "    \n",
    "    def InsertionSort(self):\n",
    "        n=len(self.lst)\n",
    "        for i in range(1,n):\n",
    "            j=i-1\n",
    "            x=self.lst[i]\n",
    "            while j>=0 and self.lst[j]>x:\n",
    "                self.lst[j+1]=self.lst[j]\n",
    "                j=j-1\n",
    "            self.lst[j+1]=x\n",
    "        return self.lst\n",
    "    \n",
    "# Selection Sort\n",
    "    \n",
    "    def SelectionSort(self):\n",
    "        List=[]\n",
    "        n=len(self.lst)\n",
    "        List.append(self.lst)\n",
    "        for i in range(n-1):\n",
    "            min=i\n",
    "            for j in range(i+1,i):\n",
    "                if List[j]>List[min]:\n",
    "                    min=j\n",
    "            if min!=i:\n",
    "                  (List[min],List[i])=(List[i],List[min])  \n",
    "        return List\n",
    "\n",
    "    \n",
    "# Driver Code\n",
    "        \n",
    "print(\"Sorting Via Bubble Sort:\")\n",
    "lst=[]\n",
    "ob=sorting(lst)\n",
    "print(\"Random List=\",ob.GenerateRandom(20))\n",
    "print(\"Sorted List=\",ob.BubbleSort())\n",
    "\n",
    "print(\"Sorting Via Insertion Sort:\")\n",
    "List=[]\n",
    "ob1=sorting(List)\n",
    "print(\"Random List=\",ob1.GenerateRandom(20))\n",
    "print(\"Sorted List=\",ob1.InsertionSort())\n",
    "\n",
    "print(\"Sorting Via Selection Sort:\")\n",
    "print(\"Sorted List=\",ob1.SelectionSort())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The Sorted list is:\n",
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "# quickSort in ascending order\n",
    "\n",
    "def partition(array,low,high): \n",
    "    i = ( low-1 )     \n",
    "    y = array[high]    \n",
    "    for j in range(low , high): \n",
    "        if   array[j] <= y: \n",
    "            i = i+1 \n",
    "            array[i],array[j] = array[j],array[i] \n",
    "  \n",
    "    array[i+1],array[high] = array[high],array[i+1] \n",
    "    return ( i+1 ) \n",
    "def quickSort(array,low,high): \n",
    "    if low < high: \n",
    "        x = partition(array,low,high) \n",
    "        quickSort(array, low, x-1) \n",
    "        quickSort(array, x+1, high) \n",
    "# Driver code \n",
    "array = [0,5,3,4,1,2] \n",
    "n = len(array) \n",
    "quickSort(array,0,n-1) \n",
    "print (\"The Sorted list is:\") \n",
    "for i in range(n): \n",
    "    print (array[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The Sorted list is:\n",
      "5\n",
      "4\n",
      "3\n",
      "2\n",
      "1\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "# quickSort in descending order\n",
    "\n",
    "def partition(array,low,high): \n",
    "    i = ( low-1 )     \n",
    "    y = array[high]    \n",
    "    for j in range(low , high): \n",
    "        if   array[j] >= y: \n",
    "            i = i+1 \n",
    "            array[i],array[j] = array[j],array[i] \n",
    "  \n",
    "    array[i+1],array[high] = array[high],array[i+1] \n",
    "    return ( i+1 ) \n",
    "def quickSort(array,low,high): \n",
    "    if low < high: \n",
    "        x = partition(array,low,high) \n",
    "        quickSort(array, low, x-1) \n",
    "        quickSort(array, x+1, high) \n",
    "# Driver code \n",
    "array = [0,5,3,4,1,2] \n",
    "n = len(array) \n",
    "quickSort(array,0,n-1) \n",
    "print (\"The Sorted list is:\") \n",
    "for i in range(n): \n",
    "    print (array[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 3, 5, 6, 8]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Sort & search the index of an element\n",
    "\n",
    "def search(v):\n",
    "    List=[1,6,3,5,8]\n",
    "    for i in List:\n",
    "            if i<=List[0]:\n",
    "                n=len(List)\n",
    "    for i in range(n):\n",
    "            for j in range(n-1):\n",
    "                if List[j]>List[j+1]:\n",
    "                    (List[j],List[j+1])=(List[j+1],List[j])\n",
    "    print( List)  \n",
    "\n",
    "    n=len(List)\n",
    "    low=0\n",
    "    high=n-1\n",
    "    is_item=False\n",
    "    while low<=high and not is_item:\n",
    "            mid=(low+high)//2\n",
    "        \n",
    "            if List[mid]==v:\n",
    "                is_item=True\n",
    "                return mid            \n",
    "            else:            \n",
    "                if v>List[mid]:\n",
    "                    low=mid+1                \n",
    "                else:\n",
    "                    high=mid-1               \n",
    "\n",
    "search(3)"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}