Grading and Sorting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is no sort primitive in APL, although sorting can be easily achieved with the use of `⍋` (grade up) or `⍒` (grade down).\n",
    "\n",
    "`⍋` takes an array and returns the indices of the major cells in ascending order. From the least major cell to the greatest major cell. It is easiest to understand with an example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2 4 1 3 5\n",
       "</span>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V←3 1 4 1 5\n",
    "⍋V"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This means that the smallest element is the second one (`1`), then the forth (also `1`), then the first (`3`), etc.\n",
    "\n",
    "So, we can use this to sort the array:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 1 3 4 5\n",
       "</span>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V[⍋V]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It works on arrays of any rank greater than 0:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2 7\n",
       "1 8\n",
       "2 8\n",
       "</span>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M←3 2⍴2 7 1 8 2 8\n",
    "M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2 1 3\n",
       "</span>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⍋M"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So the first is row 2 (`1 8`) then row 1 (`2 7`) then row 3 (`2 8`). This is a lexicographic ordering - The cells are compared item by item, until there is a difference.\n",
    "\n",
    "Characters are compared using their Unicode codepoints:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">He\n",
       "ll\n",
       "oW\n",
       "or\n",
       "ld\n",
       "</span>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Greeting←5 2⍴'HelloWorld'\n",
    "Greeting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 5 2 3 4\n",
       "</span>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⍋Greeting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">He\n",
       "ld\n",
       "ll\n",
       "oW\n",
       "or\n",
       "</span>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Greeting[⍋Greeting;]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To sort an array of any rank, one can define a function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 1 1 1 4 5 6 7\n",
       "</span>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortUp←{(⊂⍋⍵)⌷⍵}\n",
    "sortUp 1 4 1 5 1 6 1 7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`⍒` is grade down. It behaves in the same way as `⍋` but grade in descending order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">23 19 17 13 11 7 5 3 2\n",
       "</span>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortDown←{(⊂⍒⍵)⌷⍵}\n",
    "sortDown 11 5 3 23 7 17 2 13 19"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As of version 17, you can grade **any** array (as long as it doesn't contain refs). The rules for this are complicated and can be found [on the Dyalog web help for Total Array Ordering](http://help.dyalog.com/latest/#RelNotes17.0/Total%20Array%20Ordering.htm)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───┬─────┬──────┬─────┬────┐\n",
       "│car│cards│carpet│train│tram│\n",
       "└───┴─────┴──────┴─────┴────┘\n",
       "</span>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sortUp 'carpet' 'car' 'cards' 'train' 'tram'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌───┬───────┬───────┬────┬───┬──┐\n",
       "│2 5│2 5 1 3│2 5 1 3│2513│abc│xx│\n",
       "│1 3│       │       │    │   │xx│\n",
       "│   │       │       │    │   │  │\n",
       "│   │       │       │    │   │xx│\n",
       "│   │       │       │    │   │xx│\n",
       "│   │       │       │    │   │  │\n",
       "│   │       │       │    │   │xx│\n",
       "│   │       │       │    │   │xx│\n",
       "└───┴───────┴───────┴────┴───┴──┘\n",
       "</span>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢ (2 2⍴2 5 1 3) (2 5 1 3) (1 4⍴2 5 1 3) '2513' 'abc' (3 2 2⍴'x')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Grading can be used for more than just sorting. To get the index of the maximum value in an array, you use `⊃⍒`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">5\n",
       "</span>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊃⍒6 3 2 1 88 32 6 10.7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`{⍋⍋⍵}` is another useful function. While `⍋⍵` gives the indices that sort `⍵`, `⍋⍋⍵` gives the positions that each element of `⍵` would occupy after sorting. You can also think of `⍋` as inverting the permutation you give it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">3 5 6 1 2 4\n",
       "</span>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A←4 6 8 1 2 4\n",
    "⍋⍋A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first element (`4`) is the third smallest element, the second element (`6`) is the fifth smallest, and so on. It is fairly common to use `⍋⍋` to *normalise* a vector, `V`, to a permutation of `⍳≢V` which has the same ordering as `V`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dyadic Grade\n",
    "\n",
    "Grade can also be used dyadically for character arrays. `{⍺⍋⍵}` will grade `⍵` according to the alphabet `⍺`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2 5 7 10 1 3 4 9 8 6\n",
       "</span>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'aeioubcdfghjklmnpqrstvwxyz'⍋'helloworld'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">eoodhlllrw\n",
       "</span>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{⍵['aeioubcdfghjklmnpqrstvwxyz'⍋⍵]}'helloworld'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There we sorted the vowels before the consonants. If characters are missing from the alphabet, they will be considered after the alphabet, and equivalent:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2 1 3 4\n",
       "</span>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'abcdefgh'⍋'hawl'"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Dyalog APL",
   "language": "apl",
   "name": "dyalog-kernel"
  },
  "language_info": {
   "file_extension": ".apl",
   "mimetype": "text/apl",
   "name": "APL"
  },
  "tryapl": {
   "category": "Closer Looks at Some Functions",
   "description": "Grading and sorting with Grade Up and Grade Down",
   "name": "Grading and Sorting: ⍋ ⍒"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}