Day 2 - Programming.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "caa32fd6",
   "metadata": {},
   "source": [
    "# Bubble Sort\n",
    "### Time complexity Best case-O(n) Worst & Avg case-O(n^2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "0e53fed8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', 'f', 'k', 'l', 'q']\n"
     ]
    }
   ],
   "source": [
    "arr = ['f','k','l','q','a'] # 23145\n",
    "for i in range(len(arr)):   #5\n",
    "    for j in range(len(arr)-i-1): #4 #3\n",
    "        if(arr[j]>arr[j+1]):       #2>3 3>1 #2>1 2>3 \n",
    "            arr[j],arr[j+1]=arr[j+1],arr[j] #21345 #12345\n",
    "print(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c24d407e",
   "metadata": {},
   "source": [
    "# Merge Sort\n",
    "### Time Complexity O(nlog(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "ba4bd7aa",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 10, 34, 42, 56, 90]\n"
     ]
    }
   ],
   "source": [
    "def merge_sort(arr):\n",
    "    if len(arr)>1:\n",
    "        mid = len(arr)//2\n",
    "        l_half = arr[:mid]\n",
    "        r_half = arr[mid:]\n",
    "        \n",
    "        merge_sort(l_half)\n",
    "        merge_sort(r_half)\n",
    "        \n",
    "        i = j = k =0\n",
    "        \n",
    "        while i<len(l_half) and j<len(r_half):\n",
    "            if(l_half[i] < r_half[j]):\n",
    "                arr[k] = l_half[i]\n",
    "                i+=1\n",
    "            else:\n",
    "                arr[k] = r_half[j]\n",
    "                j+=1\n",
    "            k+=1\n",
    "            \n",
    "        while i<len(l_half):\n",
    "            arr[k] = l_half[i]\n",
    "            i+=1\n",
    "            k+=1\n",
    "         \n",
    "        while j<len(r_half):\n",
    "            arr[k] = r_half[j]\n",
    "            j+=1\n",
    "            k+=1\n",
    "        return arr\n",
    "            \n",
    "arr=[10,56,90,0,1,34,42]\n",
    "print(merge_sort(arr))\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bbdf019a",
   "metadata": {},
   "source": [
    "# Quick Sort\n",
    "### Time Complexity Avg & Best - O(n log(n)) Worst - O(n^2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "0346d8f5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 11, 22, 44]\n"
     ]
    }
   ],
   "source": [
    "def quick_sort(arr):\n",
    "    if(len(arr)<=1):\n",
    "        return arr\n",
    "    pivot = arr[len(arr)//2]\n",
    "    left = [x for x in arr if x < pivot]\n",
    "    middle = [x for x in arr if x == pivot] \n",
    "    right = [x for x in arr if x > pivot]\n",
    "    \n",
    "    return quick_sort(left) + middle + quick_sort(right)\n",
    "\n",
    "arr= [22,44,11,0]\n",
    "s = quick_sort(arr) \n",
    "print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c7e25da",
   "metadata": {},
   "source": [
    "# Factorial of a number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "16fcc668",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "720\n"
     ]
    }
   ],
   "source": [
    "# Recursive method\n",
    "def facto(n):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return n*facto(n-1)\n",
    "\n",
    "n = 6\n",
    "print(facto(n))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "46df4a65",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "120\n"
     ]
    }
   ],
   "source": [
    "#Iterative Method\n",
    "def factorial(n):\n",
    "    result=1\n",
    "    for i in range(1,n+1):\n",
    "        result *= i \n",
    "    return result\n",
    "    \n",
    "n = 5\n",
    "print(factorial(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1a1956b",
   "metadata": {},
   "source": [
    "# Armstrong Number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "d2959198",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "153\n",
      "armstrong\n"
     ]
    }
   ],
   "source": [
    "n = int(input())\n",
    "string = str(n)\n",
    "slen = len(string)\n",
    "ans = sum(int(digit)**slen for digit in string)\n",
    "if n ==ans:\n",
    "    print(\"armstrong\")\n",
    "else:\n",
    "    print(\"Oh no\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "a8262103",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[22, 44, 11, 0]\n"
     ]
    }
   ],
   "source": [
    "print(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "95b99c3a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "11 0 22 44\n"
     ]
    }
   ],
   "source": [
    "#Performing Rotation\n",
    "rot = int(input())\n",
    "print(*arr[rot:],*arr[:rot])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c469f5d5",
   "metadata": {},
   "source": [
    "# Sum of natural numbers "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "93c60fed",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "15\n"
     ]
    }
   ],
   "source": [
    "# using Recursion\n",
    "num = int(input())\n",
    "s= 0\n",
    "for i in range(1,num+1):\n",
    "    s += i\n",
    "print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "001d5561",
   "metadata": {},
   "source": [
    "# Check a const is Vowel or not?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "bc4a24d4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "w\n",
      "Consonant\n"
     ]
    }
   ],
   "source": [
    "s = ['a','e','i','o','u']\n",
    "ch = input()\n",
    "if ch in s:\n",
    "    print(\"Vowel\")\n",
    "else:\n",
    "    print(\"Consonant\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83021e36",
   "metadata": {},
   "source": [
    "# Find the ASCII value of a character"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "e5083dd4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A\n",
      "65\n"
     ]
    }
   ],
   "source": [
    "cha = input()\n",
    "print(ord(cha))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "f75520da",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[22, 44, 11, 0]\n"
     ]
    }
   ],
   "source": [
    "print(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e600c539",
   "metadata": {},
   "source": [
    "# to print smallest ele in arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "2e58d91a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "for i in range(len(arr)):\n",
    "    mini = i\n",
    "    for j in range(i+1,len(arr)):\n",
    "        if (arr[mini]>arr[j]):\n",
    "            mini = j\n",
    "        arr[i],arr[mini], = arr[mini],arr[i]\n",
    "print(arr[0])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "24981f47",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-9\n"
     ]
    }
   ],
   "source": [
    "ar = [-9,9,1,-2,8,7,0]\n",
    "mini = ar[0]\n",
    "for i in range(1,len(ar)):\n",
    "    if(mini>ar[i]):\n",
    "        mini = ar[i]\n",
    "        \n",
    "print(mini)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87759197",
   "metadata": {},
   "source": [
    "# Reverse elements in the array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "1eaf745c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0-->4-->2-->1-->8-->9-->"
     ]
    }
   ],
   "source": [
    "br = [9,8,1,2,4,0]\n",
    "a =len(br)\n",
    "for j in range(len(br)):\n",
    "    rem = (a)%10\n",
    "    \n",
    "    print(br[rem-1],end=\"-->\")\n",
    "    a -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a0c9c093",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.10.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}