Colab_Codes/chapter_python_comparison_sorting.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "chapter_python_comparison_sorting.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/liyin2015/Algorithms-and-Coding-Interviews/blob/master/chapter_python_comparison_sorting.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fdKUnCibJGfe",
        "colab_type": "text"
      },
      "source": [
        "Python offers a variety of built-in functions, modules, and libraries to help with comparison, sorint, and selections."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Js7-4f1M71PF",
        "colab_type": "text"
      },
      "source": [
        "## Comparison operators"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dtlOO7PU_-Wz",
        "colab_type": "code",
        "outputId": "9120041c-ebcd-4082-b61a-48425a1ec45c",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# Compare numericals\n",
        "c1 = 2 < 3\n",
        "c2 = 2.5 > 3\n",
        "c1, c2"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(True, False)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 8
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3SB8i6NE9eMM",
        "colab_type": "code",
        "outputId": "70380bfa-49fe-4611-d0f2-2f6e76ec5be9",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# Compare strings\n",
        "c1 = 'ab' < 'bc'\n",
        "c2 = 'abc' > 'abd'\n",
        "c3 = 'ab' < 'abab'\n",
        "c4 = 'abc' != 'abc'\n",
        "c1, c2, c3, c4"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(True, False, True, False)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5ePi3mnw9stn",
        "colab_type": "code",
        "outputId": "1c05d2d6-89b1-4e9d-f1f1-bf3eb3c838dc",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# Compare Sequences\n",
        "c1 = [1, 2, 3] < [2, 3]\n",
        "c2 = (1, 2) > (1, 2, 3)\n",
        "c3 = [1, 2] == [1, 2]\n",
        "c1, c2, c3"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(True, False, True)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 18
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AYbdgocGCqNt",
        "colab_type": "code",
        "outputId": "71702e44-48ee-4319-e378-91c898bd2309",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 172
        }
      },
      "source": [
        "[1, 2, 3] < (2, 3)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "error",
          "ename": "TypeError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-19-a0c5ae08d1ea>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;31mTypeError\u001b[0m: '<' not supported between instances of 'list' and 'tuple'"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XlA1fZxxCr44",
        "colab_type": "code",
        "outputId": "ffab3de3-5c39-4152-c233-816b3500492c",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 172
        }
      },
      "source": [
        "{1: 'a', 2:'b'} < {1: 'a', 2:'b', 3:'c'}"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "error",
          "ename": "TypeError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-20-a1deefc75892>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;34m{\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;34m'a'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m'b'\u001b[0m\u001b[0;34m}\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;34m'a'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m'b'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m'c'\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;31mTypeError\u001b[0m: '<' not supported between instances of 'dict' and 'dict'"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FHjrUBMvJTqS",
        "colab_type": "text"
      },
      "source": [
        "## max() and min() built-in functions\n",
        "\n",
        "max(iterable, *[, key, default])\n",
        "max(arg1, arg2, *args[, key])\n",
        "    If one positional argument is provided, it should be an iterable. The largest item in the iterable is returned. If two or more positional arguments are provided, the largest of the positional arguments is returned.\n",
        "\n",
        "    There are two optional keyword-only arguments. The key argument specifies a one-argument ordering function like that used for list.sort(). The default argument specifies an object to return if the provided iterable is empty. If the iterable is empty and default is not provided, a ValueError is raised.\n",
        "\n",
        "    If multiple items are maximal, the function returns the first one encountered. This is consistent with other sort-stability preserving tools such as sorted(iterable, key=keyfunc, reverse=True)[0] and heapq.nlargest(1, iterable, key=keyfunc).\n",
        "\n",
        "    New in version 3.4: The default keyword-only argument.\n",
        "\n",
        "    Changed in version 3.8: The key can be None.\n",
        "\n",
        "What is really interesting is that when we pass two iterables such as two lists into the $max$ function, it compares them as they are strings with lexicographical order. This character makes it useful to problem solving sometimes. \n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ysb8M9hNL42Z",
        "colab_type": "code",
        "outputId": "574e135e-f2be-4dd6-d15d-ea5cb914062d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# One iterable\n",
        "lst1 = [4, 8, 9, 20, 3]\n",
        "max([4, 8, 9, 20, 3])"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "20"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Zcr-WC5sMFjc",
        "colab_type": "code",
        "outputId": "72ba2a72-0d14-4411-9f81-a25c06ee3873",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# Two arguments\n",
        "m1 = max(24, 15)\n",
        "m2 = max([4, 8, 9, 20, 3], [6, 2, 8])\n",
        "m3 = max('abc', 'ba')\n",
        "m1, m2, m3"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(24, [6, 2, 8], 'ba')"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ilxRqKv5MygZ",
        "colab_type": "code",
        "outputId": "6201a811-9e8e-4b24-d51f-f9d64eb9e32c",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'ba'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Td_fQvXGM7Ss",
        "colab_type": "code",
        "outputId": "439e70b9-46eb-4fe7-cbb6-c254dd6d6785",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# For dictionary, it defaultly compares with keys, and it returns the key\n",
        "dict1 = {'a': 5, 'b': 8, 'c': 3}\n",
        "k1 = max(dict1)\n",
        "k2 = max(dict1, key=dict1.get)\n",
        "k3 = max(dict1, key =lambda x: dict1[x])\n",
        "k1, k2, k3"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "('c', 'b', 'b')"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 9
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "b2A71c2JTA3r",
        "colab_type": "code",
        "outputId": "898c9b40-bfd5-4625-b69f-d3e009e35ca1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "max([], default=0)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "0"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 2
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0yLoqm8ZyaWM",
        "colab_type": "text"
      },
      "source": [
        "## Rich Comparison"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BJDcW18ry4HS",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from functools import total_ordering\n",
        "\n",
        "@total_ordering\n",
        "class Person(object):\n",
        "    def __init__(self, firstname, lastname):\n",
        "        self.first = firstname\n",
        "        self.last = lastname\n",
        "\n",
        "    def __eq__(self, other):\n",
        "        return ((self.last, self.first) == (other.last, other.first))\n",
        "        \n",
        "    def __ne__(self, other):\n",
        "        return not (self == other)\n",
        "\n",
        "    def __lt__(self, other):\n",
        "        return ((self.last, self.first) < (other.last, other.first))\n",
        "\n",
        "    def __repr__(self):\n",
        "        return \"%s %s\" % (self.first, self.last)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zeww0AgS3p6R",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "c8eec9ba-6623-48cd-a1bc-5e44eafb36f5"
      },
      "source": [
        "p1 = Person('Li', 'Yin')\n",
        "p2 = Person('Bella', 'Smith')\n",
        "p1 > p2"
      ],
      "execution_count": 36,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 36
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "j9da_uDkJYQr",
        "colab_type": "text"
      },
      "source": [
        "## seq.sort() and sorted()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ag6v7yjLmR80",
        "colab_type": "text"
      },
      "source": [
        "### Basics"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fJdwJaQkgc9l",
        "colab_type": "code",
        "outputId": "ab889de3-3fe1-4a0c-a54e-5b8a231f26e4",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# List bulti-in in-place sort\n",
        "lst = [4, 5, 8, 1, 2, 7]\n",
        "lst.sort()\n",
        "lst"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 2, 4, 5, 7, 8]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LvOw_sH9hHG2",
        "colab_type": "code",
        "outputId": "b143c999-8934-42c1-eec3-384c4715fd1a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# sorted() out-of-place sorting\n",
        "lst = [4, 5, 8, 1, 2, 7]\n",
        "new_lst = sorted(lst)\n",
        "new_lst, lst"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "([1, 2, 4, 5, 7, 8], [4, 5, 8, 1, 2, 7])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 9
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "B0qx9rvaser4",
        "colab_type": "code",
        "outputId": "2326e9a9-a761-4d0b-9147-8379baa53e64",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        }
      },
      "source": [
        "# cant sort other iterable with .sort()\n",
        "tup = (3, 6, 8, 2, 78, 1, 23, 45, 9)\n",
        "tup.sort()"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "error",
          "ename": "AttributeError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-10-5630f7e30f40>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0mtup\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m6\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m8\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m78\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m23\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m45\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m9\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mtup\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msort\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m \u001b[0;31m#sorted(tup)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mAttributeError\u001b[0m: 'tuple' object has no attribute 'sort'"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aM1KExWNk33x",
        "colab_type": "code",
        "outputId": "ef49fd48-4c27-4854-e437-9d9c262dea24",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# Sort iterable with sorted()\n",
        "fruit = ('apple', 'pear', 'berry', 'peach', 'apricot')\n",
        "new_fruit = sorted(fruit)\n",
        "new_fruit"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "['apple', 'apricot', 'berry', 'peach', 'pear']"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 11
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ugBtubRqksNR",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "tup = (3, 6, 8, 2, 78, 1, 23, 45, 9)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rVASApvegGrB",
        "colab_type": "code",
        "outputId": "87b4a560-a789-4c33-a500-d8b236dcea18",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "lst = list(tup)\n",
        "lst.sort()\n",
        "lst\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 2, 3, 6, 8, 9, 23, 45, 78]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0DJi8M9N535w",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "## Customize key\n",
        "def cmp(x, y):\n",
        "  return y - x"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "I_X20Gc-58RE",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "af0499e1-3661-4092-f54b-ebd1c660a4e1"
      },
      "source": [
        "from functools import cmp_to_key\n",
        "lst = [4, 5, 8, 1, 2, 7]\n",
        "lst.sort(key=cmp_to_key(cmp))\n",
        "lst"
      ],
      "execution_count": 59,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[8, 7, 5, 4, 2, 1]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 59
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rCWeiCAGnNFP",
        "colab_type": "text"
      },
      "source": [
        "### Arguments"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y5YH4QJRnOtM",
        "colab_type": "code",
        "outputId": "b85028bc-9010-4a44-f05f-b2584a4f7c7b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# Reverse\n",
        "lst = [4, 5, 8, 1, 2, 7]\n",
        "lst.sort(reverse=True)\n",
        "lst"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[8, 7, 5, 4, 2, 1]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 12
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "y_dOIXFqotZA",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class Int(int):\n",
        "  def __init__(self, val):\n",
        "    self.val = val\n",
        "  def __lt__(self, other):\n",
        "    return other.val < self.val"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8qdEy_ctpZcI",
        "colab_type": "code",
        "outputId": "542e0581-00e4-4306-cf72-f43f2c47716f",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "lst = [Int(4), Int(5), Int(8), Int(1), Int(2), Int(7)]\n",
        "lst.sort()\n",
        "lst"
      ],
      "execution_count": 38,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[8, 7, 5, 4, 2, 1]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 38
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HJ-elndv7iDD",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "lst = [(8, 1), (5, 7), (4, 1), (1, 3), (2, 4)]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "v1jkMSha7CeW",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "97317155-9f42-4a78-b6a7-cd8994232721"
      },
      "source": [
        "## Trhough a function\n",
        "def get_key(x):\n",
        "  return x[1]\n",
        "new_lst = sorted(lst, key = get_key)\n",
        "new_lst"
      ],
      "execution_count": 52,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(8, 1), (4, 1), (1, 3), (2, 4), (5, 7)]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 52
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5h4XOS_y7sKM",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "429a0632-f00e-422b-de9f-a846a8718c7d"
      },
      "source": [
        "# Through lambda function\n",
        "new_lst = sorted(lst, key = lambda x: x[1])\n",
        "new_lst"
      ],
      "execution_count": 53,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(8, 1), (4, 1), (1, 3), (2, 4), (5, 7)]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 53
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iVMU4_4a7zjh",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "3ac52a3b-e17e-438b-de1a-119ff040d7d2"
      },
      "source": [
        "new_lst = sorted(lst, key = lambda x: (x[1], x[0]))\n",
        "new_lst"
      ],
      "execution_count": 54,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[(4, 1), (8, 1), (1, 3), (2, 4), (5, 7)]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 54
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eS-KOH4Y_3WO",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# A class\n",
        "class Student(object):\n",
        "    def __init__(self, name, grade, age):\n",
        "        self.name = name\n",
        "        self.grade = grade\n",
        "        self.age = age\n",
        "    \n",
        "    # To support indexing\n",
        "    def __getitem__(self, key):\n",
        "        return (self.name, self.grade, self.age)[key]\n",
        "\n",
        "    def __repr__(self):\n",
        "        return repr((self.name, self.grade, self.age))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cFYLwtZn_-qL",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "36f4f32b-2ee0-47de-e2bb-91e47d8bca08"
      },
      "source": [
        "students = [Student('john', 'A', 15), Student('jane', 'B', 12), Student('dave', 'B', 10)]\n",
        "sorted(students, key=lambda x: x.age)"
      ],
      "execution_count": 75,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 75
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lshxkSOJBLiT",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "b2804f89-de0a-4cc7-c6af-6a7d26676625"
      },
      "source": [
        "# Use operator\n",
        "from operator import attrgetter\n",
        "sorted(students, key=attrgetter('age'))"
      ],
      "execution_count": 77,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 77
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nA1JzPi-CkIB",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "d2fc29e7-7217-41c8-ca77-b974f02feb3e"
      },
      "source": [
        "from operator import attrgetter\n",
        "sorted(students, key=attrgetter('grade', 'age'))"
      ],
      "execution_count": 78,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 78
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mNhR68JvCZJ_",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "bb0937af-e97e-4c5e-f3da-4834129b283e"
      },
      "source": [
        "# Use itemgetter\n",
        "from operator import itemgetter\n",
        "sorted(students, key=itemgetter(2))"
      ],
      "execution_count": 79,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 79
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eA8dMPkksqly",
        "colab_type": "code",
        "outputId": "613cc186-cd57-4439-9f7f-6b122cd3d85b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 71
        }
      },
      "source": [
        "from collections import defaultdict\n",
        "import random\n",
        "dic = defaultdict(lambda: defaultdict(list)) # a dictionary of a dictionary of list dic[a][b] = [3, 1, 2, 4]\n",
        "for i in range(10):\n",
        "  a = random.randint(1, 101)\n",
        "  b = random.randint(1, 101)\n",
        "  dic[a][b] = [random.randint(1, 101) for _ in range(10)]\n",
        "print(dic) \n",
        "sorted_dic = sorted(dic)\n",
        "print(sorted_dic)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "defaultdict(<function <lambda> at 0x7faf20e3c730>, {72: defaultdict(<class 'list'>, {59: [63, 15, 62, 83, 30, 98, 16, 44, 58, 93]}), 82: defaultdict(<class 'list'>, {70: [89, 49, 47, 63, 90, 1, 7, 9, 78, 10]}), 53: defaultdict(<class 'list'>, {62: [10, 99, 35, 78, 74, 44, 82, 32, 32, 52]}), 78: defaultdict(<class 'list'>, {78: [20, 22, 100, 29, 16, 65, 56, 8, 100, 100]}), 13: defaultdict(<class 'list'>, {44: [4, 81, 17, 92, 44, 49, 72, 24, 13, 64]}), 84: defaultdict(<class 'list'>, {47: [76, 94, 36, 56, 60, 87, 72, 47, 75, 33]}), 49: defaultdict(<class 'list'>, {97: [7, 47, 13, 80, 85, 59, 2, 48, 68, 65]}), 87: defaultdict(<class 'list'>, {61: [31, 72, 71, 63, 19, 84, 78, 80, 97, 85]}), 17: defaultdict(<class 'list'>, {92: [29, 53, 20, 14, 16, 84, 57, 40, 4, 19]}), 54: defaultdict(<class 'list'>, {32: [2, 31, 19, 31, 68, 10, 85, 34, 25, 62]})})\n",
            "[13, 17, 49, 53, 54, 72, 78, 82, 84, 87]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VbmDX6yAvYax",
        "colab_type": "code",
        "outputId": "441aa86e-17c6-4cbd-b923-67c1ea41e384",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "'''sort_list_of_tuple()'''\n",
        "\n",
        "lst = [(1, 8, 2), (3, 2, 9), (1, 7, 10), (1, 7, 1), (11, 1, 5), (6, 3, 10), (32, 18, 9)]\n",
        "sorted_lst = sorted(lst, key = lambda x: x[0]) # sort in the order of the first element, and descresing order of the second element, and incresing of the third element\n",
        "print(sorted_lst)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[(1, 8, 2), (1, 7, 10), (1, 7, 1), (3, 2, 9), (6, 3, 10), (11, 1, 5), (32, 18, 9)]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tXDvRwd_047E",
        "colab_type": "code",
        "outputId": "231e3bd1-06df-4e6c-e4e8-ccfc7803ee62",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "lst = [(1, 8, 2), (3, 2, 9), (1, 7, 10), (1, 7, 1), (11, 1, 5), (6, 3, 10), (32, 18, 9)]\n",
        "sorted_lst = sorted(lst, key = lambda x: (x[0], -x[1], x[2])) # sort in the order of the first element, and descresing order of the second element, and incresing of the third element\n",
        "print(sorted_lst)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[(1, 8, 2), (1, 7, 1), (1, 7, 10), (3, 2, 9), (6, 3, 10), (11, 1, 5), (32, 18, 9)]\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}