SelectionSort.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lab 1 : Sorting Algorithm\n",
    "---\n",
    "## Selection Sort\n",
    "- Divide the list to sorted list and unsorted list.\n",
    "- Find the minimum / maximum value (up to criteria of sorting) from unsorted list.\n",
    "- Swap it with the first element of unsorted list.\n",
    "- Expand sorted list 1 element.\n",
    "\n",
    "> Ref. CPE231 Module 1 Week 3 : Sorting Algorithm, KMUTT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sample Test\n",
    "CharList = ['M', 'O', 'N', 'G', 'K', 'U', 'T']\n",
    "\n",
    "# For Runtime Compare Experiment\n",
    "cmpRound = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findMin (arr):\n",
    "    n = len(arr)\n",
    "    # index of minimum number in unsorted list\n",
    "    min = 0\n",
    "\n",
    "    # For Runtime Compare Experiment\n",
    "    count = 0\n",
    "\n",
    "    for i in range(1, n):\n",
    "        # count when compare\n",
    "        count += 1\n",
    "        if arr[i] < arr[min]:\n",
    "            min = i\n",
    "    return min, count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection (arr):\n",
    "    n = len(arr)\n",
    "    print(\"initial list :\", arr)\n",
    "\n",
    "    # For Runtime Compare Experiment\n",
    "    count = 0\n",
    "\n",
    "    for i in range(n):\n",
    "        # order round of swap\n",
    "        print(i+1, \") \", end = \"\")\n",
    "        # select minimum number from unsorted sublist\n",
    "        min, temp = findMin(arr[i:])\n",
    "        min += i  # index of minimum number in list\n",
    "\n",
    "        # count when compare (inside findMin function)\n",
    "        count += temp\n",
    "\n",
    "        # swap arr[i] with arr[min]\n",
    "        arr[i], arr[min] = arr[min], arr[i]\n",
    "        print(\"swap\", arr[i], \"<=>\", arr[min])\n",
    "        print(\"\\t\", arr)\n",
    "    return arr, count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "initial list : ['M', 'O', 'N', 'G', 'K', 'U', 'T']\n",
      "1 ) swap G <=> M\n",
      "\t ['G', 'O', 'N', 'M', 'K', 'U', 'T']\n",
      "2 ) swap K <=> O\n",
      "\t ['G', 'K', 'N', 'M', 'O', 'U', 'T']\n",
      "3 ) swap M <=> N\n",
      "\t ['G', 'K', 'M', 'N', 'O', 'U', 'T']\n",
      "4 ) swap N <=> N\n",
      "\t ['G', 'K', 'M', 'N', 'O', 'U', 'T']\n",
      "5 ) swap O <=> O\n",
      "\t ['G', 'K', 'M', 'N', 'O', 'U', 'T']\n",
      "6 ) swap T <=> U\n",
      "\t ['G', 'K', 'M', 'N', 'O', 'T', 'U']\n",
      "7 ) swap U <=> U\n",
      "\t ['G', 'K', 'M', 'N', 'O', 'T', 'U']\n"
     ]
    }
   ],
   "source": [
    "sortedArr, cmpRound = selection(CharList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['G', 'K', 'M', 'N', 'O', 'T', 'U']\n",
      "Compare round <C(n)> = 21\n"
     ]
    }
   ],
   "source": [
    "print(sortedArr)\n",
    "print(\"Compare round <C(n)> =\", cmpRound)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.5 64-bit",
   "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.5"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "369f2c481f4da34e4445cda3fffd2e751bd1c4d706f27375911949ba6bb62e1c"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}