To-Do (Sorting and Searching).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "jT-t2zlnHEll"
   },
   "source": [
    "## Write the Python code for the following problems:\n",
    "**<font color='red'>[MUST MAINTAIN VARIABLE NAMING CONVENTIONS FOR ALL THE TASKS]</font>**\n",
    "\n",
    "### Task 1\n",
    "\n",
    "Suppose you have a list named my_list as given below. <br/>\n",
    "my_list = [10,1,20,3,6,2,5,11,15,2,12,14,17,18,29] <br/>\n",
    "Now use bubble sort to sort my_list into ascending order.\n",
    "\n",
    "**Output**<br/>\n",
    "[1, 2, 2, 3, 5, 6, 10, 11, 12, 14, 15, 17, 18, 20, 29]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "id": "7qXVakLgHElm"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 2, 3, 5, 6, 10, 11, 12, 14, 15, 17, 18, 20, 29]\n"
     ]
    }
   ],
   "source": [
    "#todo - Bubble sort starts arranging the elements from the top\n",
    "def newsort(my_list):\n",
    "    #my_list = [10,1,20,3,6,2,5,11,15,2,12,14,17,18,29]\n",
    "    for i in range(len(my_list)-1):\n",
    "        for j in range(0,len(my_list)-i-1):#as last one becomes fixed by sorting in built\n",
    "            if my_list[j]>my_list[j+1]:\n",
    "                temp=my_list[j]#10..20..6\n",
    "                my_list[j]=my_list[j+1]\n",
    "                my_list[j+1]=temp\n",
    "    return my_list\n",
    "print(newsort([1,2,2,3,5,6,10,11,12,14,15,17,18,20,29]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "w1QgeWd2HElp"
   },
   "source": [
    "### Task 2\n",
    "\n",
    "Suppose you have a list named my_list as given below. <br/>\n",
    "my_list = [10,1,20,3,6,2,5,11,15,2,12,14,17,18,29] <br/>\n",
    "Now use selection sort to sort my_list into ascending order.\n",
    "\n",
    "**Output**<br/>\n",
    "[1, 2, 2, 3, 5, 6, 10, 11, 12, 14, 15, 17, 18, 20, 29]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 2, 3, 5, 6, 10, 11, 12, 14, 15, 17, 18, 20, 29]\n"
     ]
    }
   ],
   "source": [
    "#todo Selection sort starts arranging the elements from the bottom\n",
    "my_list = [10,1,20,3,6,2,5,11,15,2,12,14,17,18,29]\n",
    "\n",
    "for i in range(len(my_list)):\n",
    "    minindex=i\n",
    "    for j in range(i+1,len(my_list)):\n",
    "        if my_list[j]<my_list[minindex]:\n",
    "            minindex=j#10\n",
    "    temp=my_list[minindex]#1\n",
    "    my_list[minindex]=my_list[i]#10 to 1\n",
    "    my_list[i]=temp#1 to 10\n",
    "    #rint(my_list)\n",
    "print(my_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "j4ffr2CAHElt"
   },
   "source": [
    "### Task  3\n",
    "\n",
    "Suppose you have a list named my_list as given below <br/>\n",
    "my_list=[10,1,20,3,6,2,5,11,15,2,12,14,17,18,29] <br/>\n",
    "Now use any of the two sorting techniques you have used above to sort the list in descending order.\n",
    "\n",
    "**Output**<br/>\n",
    "[29, 20, 18, 17, 15, 14, 12, 11, 10, 6, 5, 3, 2, 2, 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "n2X3YR-_HElt"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[29, 20, 18, 17, 15, 14, 12, 11, 10, 6, 5, 3, 2, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "my_list = [10,1,20,3,6,2,5,11,15,2,12,14,17,18,29]\n",
    "\n",
    "for i in range(len(my_list)):\n",
    "    main_index=i\n",
    "    for j in range(i+1,len(my_list)):\n",
    "        if my_list[j]>my_list[main_index]:\n",
    "            main_index=j\n",
    "    temp=my_list[main_index]\n",
    "    my_list[main_index]=my_list[i]\n",
    "    my_list[i]=temp\n",
    "print(my_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "9iYiiTWWHElw"
   },
   "source": [
    "### Task 4\n",
    "\n",
    "Suppose you have a sitting arrangement of the students who will give the final exam in a list. The list contains the last two digits of their student ID as given below.<br/>\n",
    "\n",
    "sitting_list = [10,30,20,70,11,15,22,16,58,100,12,56,70,80] <br/>\n",
    "\n",
    "Now you want to organize the sitting arrangement of the students in your own way. You decide to sort all the students in the even indices of the list in ascending order and all the students in the odd indices of the list in descending order.  <br/>\n",
    "\n",
    "So, write a python program that organizes the list for you in this way.<br/>\n",
    "\n",
    "\n",
    "**Sample Output**<br/>\n",
    "[10, 100, 11, 80, 12, 70, 20, 56, 22, 30, 58, 16, 70, 15]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 100, 11, 80, 12, 70, 20, 56, 22, 30, 58, 16, 70, 15]\n"
     ]
    }
   ],
   "source": [
    "my_list = [10,30,20,70,11,15,22,16,58,100,12,56,70,80]\n",
    "new=[]\n",
    "new2=[]\n",
    "final=[]\n",
    "for i in range(len(my_list)):\n",
    "    if i%2==0:\n",
    "        new.append(my_list[i])\n",
    "    else:\n",
    "        new2.append(my_list[i])\n",
    "for i in range(len(new)):\n",
    "    minimum=new[i]\n",
    "    for j in range(i+1,len(new)):\n",
    "        if new[j]<minimum:\n",
    "            temp=new[i]#10\n",
    "            #temp=my_list[j]\n",
    "            minimum=new[j]#1\n",
    "            new[i]=minimum#10 to 1\n",
    "            new[j]=temp#1 to 10\n",
    "#print(new)\n",
    "for i in range(len(new2)):\n",
    "    maximum=new2[i]\n",
    "    for j in range(i+1,len(new2)):\n",
    "        if new2[j]>maximum:\n",
    "            temp=new2[i]#10\n",
    "            #temp=my_list[j]\n",
    "            maximum=new2[j]#1\n",
    "            new2[i]=maximum#10 to 1\n",
    "            new2[j]=temp#1 to 10\n",
    "#print(new2)\n",
    "for i in range(len(new)):\n",
    "    final.append(new[i])\n",
    "    final.append(new2[i])\n",
    "    #print(final)\n",
    "print(final)\n",
    "#output-[10, 100, 11, 80, 12, 70, 20, 56, 22, 30, 58, 16, 70, 15]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "oVR1Tsa0HElz"
   },
   "source": [
    "### Task 5\n",
    "\n",
    "Suppose a list contains marks earned in the courses CSE110, PHY111, and MAT110 of each student consecutively in a nested list form. Your task is to take a course name as input from the user and sort the list based on the marks obtained in that course in order to finally print the names of the students in descending order of marks obtained i.e. from the student who earned the highest marks to the student who earned the lowest. <br/>\n",
    "\n",
    "For example, the list may look like <br/>\n",
    "lst = [ [\"Alan\", 95, 87, 91], [\"Turing\", 92, 90, 83], [\"Elon\", 87, 92, 80], [\"Musk\", 85, 94, 90] ] <br/>\n",
    "where for each nested list, 1st index holds the name of the student, 2nd index is total marks earned in the CSE110 course, 3rd index is PHY111 marks and 4th index is MAT110 marks. \n",
    "\n",
    "=====================================================\n",
    "\n",
    "**Hint:**<br/>\n",
    "You may create a function for sorting, then call it every time when needed instead of rewriting the code.\n",
    "\n",
    "You may get the data in the individual lists from the given nested list.\n",
    "\n",
    "=====================================================\n",
    "\n",
    "**Sample Input 1**<br/>\n",
    "MAT110\n",
    "\n",
    "**Sample Output 1**<br/>\n",
    "Alan <br/>\n",
    "Musk <br/>\n",
    "Turing <br/>\n",
    "Elon\n",
    "\n",
    "**Explanation:**<br/>\n",
    "Here the user gives us \"MAT110\" as the course name. Now, the students Alan, Turing, Elon and Musk earned 91, 83, 80 and 90 marks respectively in this course. If we sort it, Alan got the highest marks of 91 followed by Musk with 90 marks and Turing with 83 marks. Among these 4 students, Elon obtained the lowest marks in the MAT110 course with 80 marks. All of these has been illustrated in our sample output.\n",
    "\n",
    "=====================================================\n",
    "\n",
    "**Sample Input 2**<br/>\n",
    "PHY111\n",
    "\n",
    "**Sample Output 2**<br/>\n",
    "Musk <br/>\n",
    "Elon <br/>\n",
    "Turing <br/>\n",
    "Alan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "id": "539b2P1NHElz"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alan\n",
      "Musk\n",
      "Turing\n",
      "Elon\n"
     ]
    }
   ],
   "source": [
    "lst =[ [\"Alan\", 95, 90, 91], [\"Turing\", 92, 90, 83], [\"Elon\", 87, 92, 80], [\"Musk\", 85, 94, 90] ]\n",
    "sub=input(\"Enter subject name: \").upper()\n",
    "if sub==\"CSE110\":\n",
    "    z=1\n",
    "if sub==\"PHY111\":\n",
    "    z=2\n",
    "if sub==\"MAT110\":\n",
    "    z=3\n",
    "for i in range(len(lst)):\n",
    "    #print(lst[i])\n",
    "    maxindex=i\n",
    "    for j in range(i+1,len(lst)):\n",
    "        if lst[j][z]>lst[maxindex][z]:\n",
    "            #print(j)\n",
    "            maxindex=j\n",
    "            \n",
    "    temp=lst[i]\n",
    "    lst[i]=lst[maxindex]\n",
    "    lst[maxindex]=temp\n",
    "#print(lst)\n",
    "for i in range(len(lst)):\n",
    "    print(lst[i][0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "B0Rqbyi4HEl2"
   },
   "source": [
    "### Task 6\n",
    "\n",
    "Suppose you have a list named my_list as given below. Your task is to sort the list in ascending order and print the count of numbers that have changed their positions in the process of sorting. <br/>\n",
    "\n",
    "my_list = [4, 2, 3, 1, 6, 5] <br/>\n",
    "\n",
    "Sorted list would be [1, 2, 3, 4, 5, 6] where 4 numbers (4, 1, 6 and 5) have changed their positions. Therefore our sample output here would be 4. Please check if your code is working correctly by changing the above list and using the knowledge given here to verify whether your code gives correct output for all different lists.\n",
    "\n",
    "\n",
    "**Sample Output for the above list**<br/>\n",
    "4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "my_list = [4, 2, 3, 1, 6, 5]\n",
    "count=0\n",
    "\n",
    "for i in range(len(my_list)):\n",
    "    minindex=i\n",
    "    for j in range(i+1,len(my_list)):\n",
    "        if my_list[j]<my_list[minindex]:\n",
    "            \n",
    "            minindex=j\n",
    "            \n",
    "    if minindex!=i:\n",
    "        temp=my_list[minindex]\n",
    "        my_list[minindex]=my_list[i]\n",
    "        my_list[i]=temp\n",
    "        count+=2\n",
    "\n",
    "print(count)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "iIH5n0sJHEl5"
   },
   "source": [
    "### Task 7\n",
    "\n",
    "Write a python program that takes two lists from the user, merges the two lists, sorts the resulting list, and then finds the median of the elements in the two lists.\n",
    "\n",
    "=====================================================\n",
    "\n",
    "\n",
    "**Sample Input 1**<br/>\n",
    "list_one = [1, 2, 1, 4] <br/>\n",
    "list_two = [5, 4, 1]\n",
    "\n",
    "\n",
    "**Sample Output 1**<br/>\n",
    "Sorted list = [1, 1, 1, 2, 4, 4, 5] <br/>\n",
    "Median = 2\n",
    "\n",
    "=====================================================\n",
    "\n",
    "\n",
    "**Sample Input 2**<br/>\n",
    "list_one = [1, 7, 9, 10] <br/>\n",
    "list_two = [2, 7, 6, 5]\n",
    "\n",
    "\n",
    "**Sample Output 2**<br/>\n",
    "Sorted list = [1, 2, 5, 6, 7, 7, 9, 10] <br/>\n",
    "Median = 6.5\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "id": "KsFxC7XbHEl6"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sorted list = [1, 2, 5, 6, 7, 7, 9, 10]\n",
      "Median =  6.5\n"
     ]
    }
   ],
   "source": [
    "list_one = [1, 7, 9, 10]\n",
    "list_two = [2, 7, 6, 5]\n",
    "list_three=[]\n",
    "for i in list_one:\n",
    "    list_three.append(i)\n",
    "for i in list_two:\n",
    "    list_three.append(i)\n",
    "\n",
    "\n",
    "list_three.sort()\n",
    "newsorted=list_three\n",
    "\n",
    "\n",
    "if len(newsorted)%2!=0:\n",
    "    middle_index=int(len(newsorted)/2)\n",
    "    median=newsorted[middle_index]\n",
    "elif len(newsorted)%2==0:\n",
    "    middle_value1=newsorted[int(len(newsorted)/2)]\n",
    "    middle_value2=newsorted[int((len(newsorted)/2)-1)]\n",
    "    median=(middle_value1+middle_value2)/2\n",
    "   \n",
    "print(\"Sorted list =\",newsorted)\n",
    "print(\"Median = \", median)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "-XKiwBR1HEl8"
   },
   "source": [
    "### Task 8\n",
    "\n",
    "\n",
    "Write a python program that takes a list from user containing both positive and negative numbers. The program then finds two pairs of values whose summation is closest to zero.\n",
    "\n",
    "=====================================================\n",
    "\n",
    "**Sample Input 1**<br/>\n",
    "list_one = [-10, 15, 2, 4, -4, 7, -8] \n",
    "\n",
    "\n",
    "**Sample Output 1**<br/>\n",
    "Two pairs which have the smallest sum = 4 and -4\n",
    "\n",
    "=====================================================\n",
    "\n",
    "\n",
    "**Sample Input 2**<br/>\n",
    "list_one = [1, -8, 4, -7, -20, 26, 70, -85]\n",
    "\n",
    "\n",
    "**Sample Output 2**<br/>\n",
    "Two pairs which have the smallest sum = 4 and -7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "5ORSGa5GHEl9"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Two pairs which have the smallest sum = 4 and -7\n"
     ]
    }
   ],
   "source": [
    "list_one = [1, -8, 4, -7, -20, 26, 70, -85]\n",
    "zer=9999\n",
    "for i in range(len(list_one)):\n",
    "    for j in range(len(list_one)):\n",
    "        if list_one[i]!=list_one[j]:\n",
    "            sum1=list_one[i]+list_one[j]\n",
    "            sum1=abs(sum1)\n",
    "            if sum1<zer:\n",
    "                zer=sum1\n",
    "                min_i=list_one[i]\n",
    "                min_j=list_one[j]\n",
    "print(\"Two pairs which have the smallest sum =\",min_i,\"and\",min_j)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "CSE110 Lab Assignment 7 (Sorting and Searching).ipynb",
   "provenance": []
  },
  "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}