Sorting Algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d08e5ca8",
   "metadata": {},
   "source": [
    "# Sorting Algorithms in Python\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39f3455f",
   "metadata": {},
   "source": [
    "# examples:\n",
    "1. school assembly: students arrangements\n",
    "2. dictionary (words are arranged alphabetically)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "643c8363",
   "metadata": {},
   "source": [
    "- increasing order: every successive element is greater than its previous element (1,2,3,4,5)\n",
    "- decreasing order: every successive element is lesser than its previous element (5,4,3,2,1)\n",
    "- non-increasing order: every successive element is greater than or equal to its previous element (1,2,3,3,4,5)\n",
    "- non-decreasing order: every successive element is lesser than or equal to its previous element (5,4,3,3,2,1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "906f5bef",
   "metadata": {},
   "source": [
    "# BUBBLE SORT\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e97fcf8",
   "metadata": {},
   "source": [
    "Sequence: 2, 23, 10, 1\n",
    "\n",
    "First Iteration\n",
    "\n",
    "(2, 23, 10, 1) –> (2, 23, 10, 1), Here the first 2 elements are compared and remain the same because they are already in ascending order.\n",
    "\n",
    "(2, 23, 10, 1) –> (2, 10, 23, 1), Here 2nd and 3rd elements are compared and swapped(10 is less than 23) according to ascending order."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "414d8591",
   "metadata": {},
   "source": [
    "(2, 10, 23, 1) –> (2, 10, 1, 23), Here 3rd and 4th elements are compared and swapped(1 is less than 23) according to ascending order\n",
    "\n",
    "At the end of the first iteration, the largest element is at the rightmost position which is sorted correctly.\n",
    "\n",
    "Second Iteration\n",
    "\n",
    "(2, 10, 1, 23) –> (2, 10, 1, 23), Here again, the first 2 elements are compared and remain the same because they are already in ascending order.\n",
    "\n",
    "(2, 10, 1, 23) –> (2, 1, 10, 23), Here 2nd and 3rd elements are compared and swapped(1 is less than 10) in ascending order.\n",
    "\n",
    "At the end of the second iteration, the second largest element is at the adjacent position to the largest element.\n",
    "\n",
    "Third Iteration\n",
    "\n",
    "(2, 1, 10, 23) –> (1, 2, 10, 23), Here the first 2 elements are compared and swap according to ascending order.\n",
    "\n",
    "The remaining elements are already sorted in the first and second Iterations. After the three iterations, the given array is sorted in ascending order. So the final result is 1, 2, 10, 23."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ab8d3458",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "34\n",
      "65\n",
      "76\n"
     ]
    }
   ],
   "source": [
    "def bubble_sort(arr):\n",
    "    \n",
    "# [2, 10, 1, 23]\n",
    "# [10, 20]  j=1, 2-0-1=1\n",
    "#[10, 30, 20] i=0, j=2 (n-i-1): 3-0-1=2\n",
    "#               i =1 j=1  (n-i-1): 3-1-1 = 1\n",
    "\n",
    "        \n",
    "    \n",
    "    n = len(arr)\n",
    "    \n",
    "    for i in range(n):\n",
    "        for j in range(0, n-1):\n",
    "            \n",
    "            if arr[j] > arr[j+1]:\n",
    "                # swap the elements                       a=10, b=20=> a=20, b=10\n",
    "#                 temp = arr[j]                             #temp = 10   temp = a\n",
    "#                 arr[j] = arr[j+1]                          #a = 20     a = b\n",
    "#                 arr[j+1] = temp                            #b = 10     b = temp\n",
    "                \n",
    "                arr[j], arr[j+1] = arr[j+1], arr[j]\n",
    "        \n",
    "# run program\n",
    "arr = [2, 10, 1, 23, 4, 43, 35, 73]\n",
    "arr = [2, 34, 65, 76]\n",
    "bubble_sort(arr)\n",
    "for i in range(len(arr)):\n",
    "    print(\"%d\" %  arr[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f42e0f7e",
   "metadata": {},
   "source": [
    "## bubble sort time complexity: O(n^2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6cb55aab",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0bbfdef6",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "28e1a4b0",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "435495f9",
   "metadata": {},
   "source": [
    "# SELECTION SORT "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7559dfc",
   "metadata": {},
   "source": [
    "Lets consider the following array as an example: arr[] = {64, 25, 12, 22, 11}\n",
    "\n",
    "First pass:\n",
    "\n",
    "For the first position in the sorted array, the whole array is traversed from index 0 to 4 sequentially. The first position where 64 is stored presently, after traversing whole array it is clear that 11 is the lowest value.\n",
    "   64   \t   25   \t   12   \t   22   \t   11   \n",
    "Thus, replace 64 with 11. After one iteration 11, which happens to be the least value in the array, tends to appear in the first position of the sorted list.\n",
    "   11   \t   25   \t   12   \t   22   \t   64   \n",
    "Second Pass:\n",
    "\n",
    "For the second position, where 25 is present, again traverse the rest of the array in a sequential manner.\n",
    "   11   \t   25   \t   12   \t   22   \t   64   \n",
    "After traversing, we found that 12 is the second lowest value in the array and it should appear at the second place in the array, thus swap these values.\n",
    "   11   \t   12   \t   25   \t   22   \t   64   \n",
    "Third Pass:\n",
    "\n",
    "Now, for third place, where 25 is present again traverse the rest of the array and find the third least value present in the array.\n",
    "   11   \t   12   \t   25   \t   22   \t   64   \n",
    "While traversing, 22 came out to be the third least value and it should appear at the third place in the array, thus swap 22 with element present at third position.\n",
    "   11   \t   12   \t   22   \t   25   \t   64   \n",
    "Fourth pass:\n",
    "\n",
    "Similarly, for fourth position traverse the rest of the array and find the fourth least element in the array \n",
    "As 25 is the 4th lowest value hence, it will place at the fourth position.\n",
    "   11   \t   12   \t   22   \t   25   \t   64   \n",
    "Fifth Pass:\n",
    "\n",
    "At last the largest value present in the array automatically get placed at the last position in the array\n",
    "The resulted array is the sorted array.\n",
    "   11   \t   12   \t   22   \t   25   \t   64   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4fa61e2e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 64, 25, 12, 22, 11\n",
    "\n",
    "# i=0   ; min_value = 64 #25 #12 #11   a[i] = min_value   [11, 25, 12, 22, 64]\n",
    "# i=1   : min_value = 25 #12           a[i] = min_value   [11, 12, 25, 22, 64]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80545680",
   "metadata": {},
   "source": [
    "steps:\n",
    "    \n",
    "- initialize minimum_value to location 0\n",
    "- traverse the array to find the minimum element in the array\n",
    "- while traversing, if any element is smaller than min_value is found then swap both the values\n",
    "- then, increment position of next element\n",
    "- repeat the steps until array is sorted"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "29feddd1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "34\n",
      "65\n",
      "76\n"
     ]
    }
   ],
   "source": [
    "def selection_sort(arr):       # [2,34,65,76] #[2,65, 34, 76] #[2, 34, 65, 74]\n",
    "    \n",
    "    n = len(arr)                 #n=4\n",
    "    \n",
    "    for i in range(n):          #i=0                 #i=1\n",
    "        min_idx = i             #min_idx:0           #min_idx:1\n",
    "        for j in range(i+1, n):   #(1,4) #j:2 #j:3    (2,4)\n",
    "            if arr[min_idx] > arr[j]:               ##a[1]>a[2] #a[2]>a[]\n",
    "                min_idx = j                         #min_idx=2\n",
    "                \n",
    "        \n",
    "        # swap the found minimum element with the first element\n",
    "        arr[i], arr[min_idx] = arr[min_idx], arr[i] #a[0], a[0] =a[0],a[0] #a[1], a[2]\n",
    "        \n",
    "\n",
    "# run program\n",
    "arr = [2, 10, 1, 23, 4, 43, 35, 73]\n",
    "arr = [2, 34, 65, 76]\n",
    "selection_sort(arr)\n",
    "for i in range(len(arr)):\n",
    "    print(\"%d\" %  arr[i])\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a5a42b1",
   "metadata": {},
   "source": [
    "time complexity: O(n^2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "86ed9f35",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dea3386d",
   "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}