Selection sort explained

Selection Sort.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Selection Sort\n",
    "\n",
    "+ an in-place comparison sort\n",
    "\n",
    "**Note: Don't panic if you didn't get it. Its my job to explain you**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm\n",
    "\n",
    "1. Set MIN to location 0\n",
    "2. Search the minimum element in the list\n",
    "3. Swap with value at location MIN\n",
    "4. Increment MIN to point to next element\n",
    "5. Repeat until list is sorted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Psuedo Code\n",
    "\n",
    "**SELECTION-SORT(A)**\n",
    "\n",
    "_suppose we have an array of `n` length_\n",
    "\n",
    "    for j ← 1 to n-1\n",
    "        smallest ← j\n",
    "        for i ← j + 1 to n\n",
    "            if A[ i ] < A[ smallest ]\n",
    "                smallest ← i\n",
    "        Exchange A[ j ] ↔ A[ smallest ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [1,3,5,4,2,9,6] # defining sample list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(array: list) -> list:\n",
    "    # traversing the array from 0 to n\n",
    "    for i in range(len(array) - 1): \n",
    "\n",
    "        # getting smallest index\n",
    "        min_index = i\n",
    "#         print(\"assumed smallest index {} -> {}\".format( min_index, array[min_index]) )\n",
    "        \n",
    "        # traversing the array from i + 1 to n\n",
    "        for j in range(i + 1, len(array)): \n",
    "            # check if assumend small is greater than element in range(i+1, n)\n",
    "            if array[min_index] > array[j]:\n",
    "                # storing new minimun index\n",
    "                min_index = j\n",
    "#                 print(\"actual smallest index {} -> {}\".format( min_index, array[min_index]))\n",
    "                \n",
    "        # swapping\n",
    "        array[i], array[min_index] = array[min_index], array[i]\n",
    "#         print(array)\n",
    "        \n",
    "    return array # return array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 9]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    " selection_sort(arr) # running the algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I hope now the term `in-place comparison` is clear"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}