{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sorting Algorithms\n",
    "> Working with Data Structures and manipulating data.\n",
    "\n",
    "- toc: true\n",
    "- categories: []\n",
    "- type: pbl\n",
    "- week: 34"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[wget link](https://raw.githubusercontent.com/nighthawkcoders/APCSP/master/_notebooks/2023-05-15-DS-sorting.ipynb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "numbers = []\n",
    "for i in range(10):\n",
    "    numbers.append(random.randint(0,100))\n",
    "print(\"Random List\")\n",
    "print(numbers)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Warm Up\n",
    "\n",
    "> Discuss with a partner... \n",
    "What are some strategies you would use to sort this list? (Don't worry about writing code for now)\n",
    "- ?"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Explore\n",
    "\n",
    "Get into groups of 3\n",
    "\n",
    "We will be focusing on 4 algorithms today.\n",
    "\n",
    "We will look at the first one together, Bubble Sort\n",
    "\n",
    "![](images/bubble-sort.png)\n",
    "\n",
    "What is happening with this sort?\n",
    "\n",
    "In your groups you will each choose to be an expert on a sorting algorithm. Merge, Selection, and Insertion.\n",
    "Take about 5 minutes to read about your algorithm (Geek for Geeks linked below) and be ready to explain it to your other group members. \n",
    "\n",
    "[Merge](https://www.geeksforgeeks.org/merge-sort/#)\n",
    "\n",
    "[Selection](https://www.geeksforgeeks.org/selection-sort/)\n",
    "\n",
    "[Insertion](https://www.geeksforgeeks.org/insertion-sort/)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Practice\n",
    "\n",
    "[75, 17, 46, 80, 67, 45, 69, 79, 40, 0]\n",
    "\n",
    "How would you sort this list with... \n",
    "- Bubble Sort\n",
    "- Selection Sort\n",
    "> Explain.\n",
    "\n",
    "[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]\n",
    "\n",
    "How would you sort this list with... \n",
    "- Merge Sort\n",
    "- Insertion Sort\n",
    "> Explain.\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sorting Words\n",
    "> Sorting strings works in the same way as integers. Using your expertise algorithm, sort the following list of random words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Random List\n",
      "['cleanse', 'insure', 'monomineral', 'aculeated', 'Baalitical', 'wiredrawn', 'unnabbed', 'Imperata', 'parakinetic', 'sequester']\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[nltk_data] Downloading package words to\n",
      "[nltk_data]     /Users/johnmortensen/nltk_data...\n",
      "[nltk_data]   Package words is already up-to-date!\n"
     ]
    }
   ],
   "source": [
    "import nltk\n",
    "import random\n",
    "from nltk.corpus import words\n",
    "nltk.download('words')  # Download the word list (only required once)\n",
    "english_words = words.words()\n",
    "\n",
    "def new_words():\n",
    "    # You can now use the 'english_words' list in your code\n",
    "    random_words = []\n",
    "    for i in range(10):\n",
    "        random_words.append(english_words[random.randint(0,len(english_words))])\n",
    "    return random_words\n",
    "        \n",
    "\n",
    "print(\"Random List\")\n",
    "print(new_words())"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bubble Sort Poopcorn Hack\n",
    "> Mortensen did this hack in class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['semihyperbolical', 'samesome', 'paradoxidian', 'pyruline', 'gangliocyte', 'reckoning', 'intertubular', 'copelate', 'cered', 'amyloid']\n",
      "['amyloid', 'cered', 'copelate', 'gangliocyte', 'intertubular', 'paradoxidian', 'pyruline', 'reckoning', 'samesome', 'semihyperbolical']\n"
     ]
    }
   ],
   "source": [
    "words = new_words()\n",
    "print(words)\n",
    "def bubbleSort(list):\n",
    "    n = len(list) - 1  # list are indexed 0 to n-1, len is n\n",
    "    \n",
    "    # Traverse through list with i index\n",
    "    for i in range(n):\n",
    "        swapped = False  # optimize code, so it exits if now swaps on inner loop\n",
    "\n",
    "        # Inner traversal using j index\n",
    "        for j in range(n-i):  # n-i as positions on right are in order in bubble\n",
    " \n",
    "            # Swap if the element KeyN is greater KeyN1\n",
    "            keyN = list[j]\n",
    "            keyN1 = list[j+1]\n",
    "            if keyN > keyN1:\n",
    "                swapped = True\n",
    "                list[j], list[j + 1] = list[j + 1], list[j]  # single line swap\n",
    "         \n",
    "        if not swapped:  # if no swaps on inner pass, list is sorted\n",
    "            return  # exit function\n",
    "        \n",
    "bubbleSort(words)\n",
    "print(words)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Selection Sort Poopcorn Hack\n",
    "> Mortensen did this hack in class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['ainoi', 'accipient', 'marvelry', 'rampageously', 'unpalatial', 'diaminogen', 'Pacht', 'tweak', 'faddism', 'elegant']\n",
      "['Pacht', 'accipient', 'ainoi', 'diaminogen', 'elegant', 'faddism', 'marvelry', 'rampageously', 'tweak', 'unpalatial']\n"
     ]
    }
   ],
   "source": [
    "words = new_words()\n",
    "print(words)\n",
    "def selectionSort(list):\n",
    "    n = len(list)  # length is n\n",
    "    \n",
    "    # List is traversed from index 0 to n-1, n elements\n",
    "    for i in range(n):\n",
    "        smallI = i  # small index is captured\n",
    "        smallV = list[i]\n",
    "\n",
    "        # Inner traversal looks at elements after i\n",
    "        for j in range(i+1, n):\n",
    "            # Save reference if less\n",
    "            keyV = list[j]\n",
    "            if keyV < smallV:\n",
    "                smallI = j  # small index is replaced\n",
    "                smallV = keyV\n",
    "        \n",
    "        # swap smallest to current i positon, sorting left to right\n",
    "        list[i], list[smallI] = list[smallI], list[i]  # single line swap \n",
    "        \n",
    "selectionSort(words)\n",
    "print(words)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Discuss \n",
    "Answer the following with your group.\n",
    "\n",
    "- When should you use each algorithm? What makes an algorithm the right choice?\n",
    "- Given the following lists...\n",
    "    - [0, 2, 6, 4, 8, 10]\n",
    "    - [Elephant, Banana, Cat, Dog, Apple]\n",
    "    - [29, 13, 83, 47, 32, 78, 100, 60, 65, 15, 24, 9, 40, 68, 53, 8, 90, 58, 39, 32, 34, 91, 74, 94, 49, 87, 34, 87, 23, 17, 27, 2, 38, 58, 84, 15, 9, 46, 74, 40, 44, 8, 55, 28, 81, 92, 81, 88, 53, 38, 19, 21, 9, 54, 21, 67, 3, 41, 3, 74, 13, 71, 70, 45, 5, 36, 80, 64, 97, 86, 73, 74, 94, 79, 49, 32, 20, 68, 64, 69, 1, 77, 31, 56, 100, 80, 48, 75, 85, 93, 67, 57, 26, 56, 43, 53, 59, 28, 67, 50]\n",
    "Select the algorithm you believe is best for each, explain."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## HACKS\n",
    "> Provided below is a Bubble Sort Algorithm sorting a list of dictionaries based off of selected key.\n",
    "\n",
    "- Now it's time to do some coding...\n",
    "\n",
    "- Run code and then research and answer these questions...\n",
    "    - Is a list and/or dictionary in python considered a primitive or collection type?  Why?\n",
    "    - Is the list passed into bubble sort \"pass-by-value\" or \"pass-by-reference? Describe why in relation to output.\n",
    "\n",
    "- Implement new cell(s) and/or organize cells to do the following.\n",
    "    - Create your own list\n",
    "    - Use your expertise sorting algorithm (selection, insertion, merge). Note, I got my bubble sort from Geek for Geeks and made modifications. Each student in a group should have a unique algorithm.\n",
    "    - Test your list with my bubble sort\n",
    "    - Test my list with your new sort\n",
    "    - Research analysis on sorting: comparisons, swaps, time.  Build this into your hacks.\n",
    "    - Find a better way to print the data, key first, then other elements in viewable form.\n",
    "\n",
    "Use the code below to help guide your adventure"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "* Creator: Nighthawk Coding Society\n",
    "Bubble Sort of a List of Dictionaries with optimizations, every key in row 0 is used to sort and resort list.\n",
    "\"\"\"\n",
    "\n",
    "# bubble sorts a list of dictionaries, base off of provided key\n",
    "def bubbleSort(list, key):\n",
    "    n = len(list) - 1  # list are indexed 0 to n-1, len is n\n",
    "    \n",
    "    # Traverse through list with i index\n",
    "    for i in range(n):\n",
    "        swapped = False  # optimize code, so it exits if now swaps on inner loop\n",
    "\n",
    "        # Inner traversal using j index\n",
    "        for j in range(n-i):  # n-i as positions on right are in order in bubble\n",
    " \n",
    "            # Swap if the element KeyN is greater KeyN1\n",
    "            keyN = list[j].get(key)\n",
    "            keyN1 = list[j+1].get(key)\n",
    "            if keyN > keyN1:\n",
    "                swapped = True\n",
    "                list[j], list[j + 1] = list[j + 1], list[j]  # single line swap\n",
    "         \n",
    "        if not swapped:  # if no swaps on inner pass, list is sorted\n",
    "            return  # exit function\n",
    "    \n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # list/dictionary sample\n",
    "    list_of_people = [\n",
    "    {\"name\": \"Risa\", \"age\": 18, \"city\": \"New York\"},\n",
    "    {\"name\": \"John\", \"age\": 63, \"city\": \"Eugene\"},\n",
    "    {\"name\": \"Shekar\", \"age\": 18, \"city\": \"San Francisco\"},\n",
    "    {\"name\": \"Ryan\", \"age\": 21, \"city\": \"Los Angeles\"}\n",
    "    ]\n",
    "    \n",
    "    # assuming uniform keys, pick 1st row as source of keys\n",
    "    key_row = list_of_people[0]\n",
    "\n",
    "    # print list as defined\n",
    "    print(\"Original\")\n",
    "    print(list_of_people)\n",
    "    \n",
    "    for key in key_row:  # finds each key in the row\n",
    "        print(key)\n",
    "        bubbleSort(list_of_people, key)  # sort list of people\n",
    "        print(list_of_people)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "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.9.12"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}