{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0493b35a-55c4-422f-b101-9dd443fd03af",
   "metadata": {},
   "source": [
    "# Quicksort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "2292b8e5-ebc5-4aae-8d56-bee47ed9b4a8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val part : int * int list * int list * int list -> int list * int list =\n",
       "  <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val quick : int list -> int list = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec part (a,l,r,xs) : int list * int list =\n",
    "   match xs with\n",
    "        | [] -> (l, r)\n",
    "        | x::xs ->\n",
    "            if (x <= a) then\n",
    "              part (a,(x::l), r, xs)\n",
    "            else\n",
    "              part (a, l, (x::r), xs)\n",
    "\n",
    "\n",
    "let rec quick : int list -> int list = function\n",
    "  | [] -> []\n",
    "  | [x] -> [x]\n",
    "  | a::bs ->\n",
    "      \n",
    "      let (l, r) = part (a,[],[],bs) in\n",
    "      (quick l) @ (a :: (quick r))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "aaadcd03-5538-476f-9d09-c6cb256691ea",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quick is now traced.\n"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#trace quick"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "48f7e83c-e230-4d87-8cb8-e756eaf80f3e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quick <-- [4; 2; 5; 3; 6; 1; 7; 8]\n",
       "quick <-- [8; 7; 6; 5]\n",
       "quick <-- []\n",
       "quick --> []\n",
       "quick <-- [5; 6; 7]\n",
       "quick <-- [7; 6]\n",
       "quick <-- []\n",
       "quick --> []\n",
       "quick <-- [6]\n",
       "quick --> [6]\n",
       "quick --> [6; 7]\n",
       "quick <-- []\n",
       "quick --> []\n",
       "quick --> [5; 6; 7]\n",
       "quick --> [5; 6; 7; 8]\n",
       "quick <-- [1; 3; 2]\n",
       "quick <-- [2; 3]\n",
       "quick <-- [3]\n",
       "quick --> [3]\n",
       "quick <-- []\n",
       "quick --> []\n",
       "quick --> [2; 3]\n",
       "quick <-- []\n",
       "quick --> []\n",
       "quick --> [1; 2; 3]\n",
       "quick --> [1; 2; 3; 4; 5; 6; 7; 8]\n",
       "- : int list = [1; 2; 3; 4; 5; 6; 7; 8]\n"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quick [4;2;5;3;6;1;7;8]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "967bb34e-1e21-4d63-a6e5-d5853da250fa",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val part : int * int list * int list * int list -> int list * int list =\n",
       "  <fun>\n"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "val quick : int list -> int list = <fun>\n"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec part (a,l,r,xs) : int list * int list =\n",
    "        match xs with\n",
    "        | [] -> (l, r)\n",
    "        | x::xs ->\n",
    "            if (x <= a) then\n",
    "              part (a, (x::l), r, xs)\n",
    "            else\n",
    "              part (a, l, (x::r), xs)\n",
    "\n",
    "let rec quick = function\n",
    "  | [] -> []\n",
    "  | [x] -> [x]\n",
    "  | a::bs ->\n",
    "      let (l, r) = part (a, [], [], bs) in \n",
    "      (quick l) @ (a :: quick r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "99b372c9-9d42-4e0b-8bbf-2f02c225a218",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quick is now traced.\n"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "part is now traced.\n"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#trace quick\n",
    "#trace part"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "debb0c54-17f0-46be-a26a-5a49d5471290",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quick <-- [4; 6; 2; 1; 3; 5; 8; 7]\n",
       "part <-- (4, [], [], [6; 2; 1; 3; 5; 8; 7])\n",
       "part <-- (4, [], [6], [2; 1; 3; 5; 8; 7])\n",
       "part <-- (4, [2], [6], [1; 3; 5; 8; 7])\n",
       "part <-- (4, [1; 2], [6], [3; 5; 8; 7])\n",
       "part <-- (4, [3; 1; 2], [6], [5; 8; 7])\n",
       "part <-- (4, [3; 1; 2], [5; 6], [8; 7])\n",
       "part <-- (4, [3; 1; 2], [8; 5; 6], [7])\n",
       "part <-- (4, [3; 1; 2], [7; 8; 5; 6], [])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "quick <-- [7; 8; 5; 6]\n",
       "part <-- (7, [], [], [8; 5; 6])\n",
       "part <-- (7, [], [8], [5; 6])\n",
       "part <-- (7, [5], [8], [6])\n",
       "part <-- (7, [6; 5], [8], [])\n",
       "part --> ([6; 5], [8])\n",
       "part --> ([6; 5], [8])\n",
       "part --> ([6; 5], [8])\n",
       "part --> ([6; 5], [8])\n",
       "quick <-- [8]\n",
       "quick --> [8]\n",
       "quick <-- [6; 5]\n",
       "part <-- (6, [], [], [5])\n",
       "part <-- (6, [5], [], [])\n",
       "part --> ([5], [])\n",
       "part --> ([5], [])\n",
       "quick <-- []\n",
       "quick --> []\n",
       "quick <-- [5]\n",
       "quick --> [5]\n",
       "quick --> [5; 6]\n",
       "quick --> [5; 6; 7; 8]\n",
       "quick <-- [3; 1; 2]\n",
       "part <-- (3, [], [], [1; 2])\n",
       "part <-- (3, [1], [], [2])\n",
       "part <-- (3, [2; 1], [], [])\n",
       "part --> ([2; 1], [])\n",
       "part --> ([2; 1], [])\n",
       "part --> ([2; 1], [])\n",
       "quick <-- []\n",
       "quick --> []\n",
       "quick <-- [2; 1]\n",
       "part <-- (2, [], [], [1])\n",
       "part <-- (2, [1], [], [])\n",
       "part --> ([1], [])\n",
       "part --> ([1], [])\n",
       "quick <-- []\n",
       "quick --> []\n",
       "quick <-- [1]\n",
       "quick --> [1]\n",
       "quick --> [1; 2]\n",
       "quick --> [1; 2; 3]\n",
       "quick --> [1; 2; 3; 4; 5; 6; 7; 8]\n",
       "- : int list = [1; 2; 3; 4; 5; 6; 7; 8]\n"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quick [4;6;2;1;3;5;8;7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "e970e74e-da32-4599-be79-cbc706eb1377",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val quik : int list * int list -> int list = <fun>\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec quik = function\n",
    "  | ([], sorted) -> sorted\n",
    "  | ([x], sorted) -> x::sorted\n",
    "  | a::bs, sorted ->\n",
    "     let (l, r) = part (a, [], [], bs) in \n",
    "     quik (l, a :: quik (r, sorted))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "e2bd5c41-3bab-4a60-9b63-2b8bf414ab86",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quik is now traced.\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#trace quik"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "96fbb34c-fa08-4393-8d31-6e8c7125d6f3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "quik <-- ([4; 6; 2; 1; 3; 5; 8; 7], [])\n",
       "part <-- (4, [], [], [6; 2; 1; 3; 5; 8; 7])\n",
       "part <-- (4, [], [6], [2; 1; 3; 5; 8; 7])\n",
       "part <-- (4, [2], [6], [1; 3; 5; 8; 7])\n",
       "part <-- (4, [1; 2], [6], [3; 5; 8; 7])\n",
       "part <-- (4, [3; 1; 2], [6], [5; 8; 7])\n",
       "part <-- (4, [3; 1; 2], [5; 6], [8; 7])\n",
       "part <-- (4, [3; 1; 2], [8; 5; 6], [7])\n",
       "part <-- (4, [3; 1; 2], [7; 8; 5; 6], [])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "part --> ([3; 1; 2], [7; 8; 5; 6])\n",
       "quik <-- ([7; 8; 5; 6], [])\n",
       "part <-- (7, [], [], [8; 5; 6])\n",
       "part <-- (7, [], [8], [5; 6])\n",
       "part <-- (7, [5], [8], [6])\n",
       "part <-- (7, [6; 5], [8], [])\n",
       "part --> ([6; 5], [8])\n",
       "part --> ([6; 5], [8])\n",
       "part --> ([6; 5], [8])\n",
       "part --> ([6; 5], [8])\n",
       "quik <-- ([8], [])\n",
       "quik --> [8]\n",
       "quik <-- ([6; 5], [7; 8])\n",
       "part <-- (6, [], [], [5])\n",
       "part <-- (6, [5], [], [])\n",
       "part --> ([5], [])\n",
       "part --> ([5], [])\n",
       "quik <-- ([], [7; 8])\n",
       "quik --> [7; 8]\n",
       "quik <-- ([5], [6; 7; 8])\n",
       "quik --> [5; 6; 7; 8]\n",
       "quik --> [5; 6; 7; 8]\n",
       "quik --> [5; 6; 7; 8]\n",
       "quik <-- ([3; 1; 2], [4; 5; 6; 7; 8])\n",
       "part <-- (3, [], [], [1; 2])\n",
       "part <-- (3, [1], [], [2])\n",
       "part <-- (3, [2; 1], [], [])\n",
       "part --> ([2; 1], [])\n",
       "part --> ([2; 1], [])\n",
       "part --> ([2; 1], [])\n",
       "quik <-- ([], [4; 5; 6; 7; 8])\n",
       "quik --> [4; 5; 6; 7; 8]\n",
       "quik <-- ([2; 1], [3; 4; 5; 6; 7; 8])\n",
       "part <-- (2, [], [], [1])\n",
       "part <-- (2, [1], [], [])\n",
       "part --> ([1], [])\n",
       "part --> ([1], [])\n",
       "quik <-- ([], [3; 4; 5; 6; 7; 8])\n",
       "quik --> [3; 4; 5; 6; 7; 8]\n",
       "quik <-- ([1], [2; 3; 4; 5; 6; 7; 8])\n",
       "quik --> [1; 2; 3; 4; 5; 6; 7; 8]\n",
       "quik --> [1; 2; 3; 4; 5; 6; 7; 8]\n",
       "quik --> [1; 2; 3; 4; 5; 6; 7; 8]\n",
       "quik --> [1; 2; 3; 4; 5; 6; 7; 8]\n",
       "- : int list = [1; 2; 3; 4; 5; 6; 7; 8]\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quik ([4;6;2;1;3;5;8;7],[])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml 4.14",
   "language": "OCaml",
   "name": "ocaml-jupyter"
  },
  "language_info": {
   "codemirror_mode": "text/x-ocaml",
   "file_extension": ".ml",
   "mimetype": "text/x-ocaml",
   "name": "OCaml",
   "nbconverter_exporter": null,
   "pygments_lexer": "OCaml",
   "version": "4.14.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}