From 67393f42f41ab92219deb549f711121c4dab845b Mon Sep 17 00:00:00 2001
From: Nguyễn Gia Phong <vn.mcsinyx@gmail.com>
Date: Sun, 15 Dec 2019 10:34:58 +0700
Subject: [usth/ICT2.2] Object Oriented Programming

---
 usth/ICT2.2/midterm/report/report.tex | 928 ++++++++++++++++++++++++++++++++++
 1 file changed, 928 insertions(+)
 create mode 100644 usth/ICT2.2/midterm/report/report.tex

(limited to 'usth/ICT2.2/midterm/report/report.tex')

diff --git a/usth/ICT2.2/midterm/report/report.tex b/usth/ICT2.2/midterm/report/report.tex
new file mode 100644
index 0000000..627530a
--- /dev/null
+++ b/usth/ICT2.2/midterm/report/report.tex
@@ -0,0 +1,928 @@
+\documentclass[a4paper,12pt]{article}
+\usepackage[english,vietnamese]{babel}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{booktabs}
+\usepackage{lmodern}
+\usepackage{graphicx}
+\usepackage{hyperref}
+\usepackage{lmodern}
+\usepackage{forest}
+\usepackage{textcomp}
+\usepackage[nottoc,numbib]{tocbibind}
+
+\renewcommand{\thefootnote}{\fnsymbol{footnote}}
+
+\begin{document}
+\setcounter{page}{0}
+\thispagestyle{empty}
+\vspace*{\stretch{1}}
+\begin{flushright}
+  \setlength{\baselineskip}{1.4\baselineskip}
+\textbf{\Huge Midterm Report\\Sorting and Searching}
+  \noindent\rule{\textwidth}{5pt}
+  \emph{\Large Object Oriented Programming}
+  \vspace{\stretch{1}}
+
+  \textbf{by Nguyễn Công Thành, Nguyễn Gia Phong\\
+          Nguyễn Văn Tùng, Trần Minh Vương and Trần Hồng Minh\\}
+  \selectlanguage{english}
+  \today
+\end{flushright}
+\vspace*{\stretch{2}}
+\pagebreak
+
+\selectlanguage{english}
+\tableofcontents
+\pagebreak
+
+\section{Introduction}
+\subsection{Brief Description}
+Since the dawn of computer science, sorting and searching algorithms
+have drawn a significant amount of attention from researchers,
+due to their broad applications in solving a huge number of problems
+and sub-problems in many fields.  In spite of their straightforward, familiar
+statements, these algorithm link with a variety of important programming
+concepts, namely data structures, divide and conquer technique and of course
+complexity analysis and time–space tradeoffs.
+
+In this report, we only discuss some of the most basic searching
+and sorting algorithms.  While trying to implement them, we also analyze
+their strengths and weaknesses, as well as the ease and difficulties
+we encounter using the language Java and object-oriented programming in general.
+
+Whilst overall, we follow~\cite{wu}, we also try to make use of newer Java
+features to write more generic and concise code.
+
+This report is licensed under a
+\href{http://creativecommons.org/licenses/by-sa/4.0/}{Creative Commons
+Attribution-ShareAlike 4.0 International License.}
+
+\selectlanguage{vietnamese}
+\subsection{Authors and Credits}
+
+The work has been undertaken by group number 11, whose members are listed
+in the following table, with Nguyễn Công Thành being our leader.
+\begin{center}
+  \begin{tabular}{c c}
+    \toprule
+    Full name & Student ID\\
+    \midrule
+    Nguyễn Công Thành & BI9-210\\
+    Nguyễn Gia Phong & BI9-184\\
+    Nguyễn Văn Tùng & BI9-229\\
+    Trần Minh Vương & BI9-239\\
+    Trần Hồng Minh & BI8-114\\
+    \bottomrule
+  \end{tabular}
+\end{center}
+
+We would like to express our special thanks to Dr. Nghiêm Thị Phương,
+whose lectures gave us basic understanding on the key principles of
+object-oriented programming.  Without her guidance, we might never
+have a chance to take an in-depth exploration on this topic.
+\pagebreak
+
+\selectlanguage{english}
+\section{Searching}
+For the sake of simplicity, we only consider searching operating on array-like
+data structures with constant-time random access and without duplicated entries.
+This affects a few implementation design decision we will be making later on.
+The searching problem is then stated in ~\cite[p.~634]{wu} accordingly:
+\begin{quote}
+  Given a value $x$, return the [zero-based] index of $x$ in the array,
+  if such $x$ exists.  Otherwise, return \verb|NOT_FOUND| (-1).
+\end{quote}
+
+In this section, we will discover two searching algorithms: linear search
+and binary search.  Both of these, albeit being simple, are being used in
+many different programming tasks.
+
+\subsection{Linear Search}
+Linear search, by definition, sequentially checks each element of a list
+until a match is found or the whole list has been searched.  This matches
+the algorithm implemented in \verb|java.util.List.indexOf|~\cite[indexOf]{list}.
+Given
+\begin{verbatim}
+var list = java.util.Arrays.asList(4, 20, 6, 9);
+\end{verbatim}
+where \verb|var| is a Java SE 10 feature for eliding ``the often-unnecessary
+manifest declaration of local variable types''~\cite{var}, which, in this case,
+is \verb|List<Integer>|.
+
+\verb|list.indexOf(6)| would then give 2 and \verb|list.indexOf(7)| returns -1.
+
+For the matter of completeness, we also try to implement the description
+provided by the documentation~\cite[indexOf]{list}
+\begin{verbatim}
+import java.util.List;
+
+public class Search
+{
+  public static final int NOT_FOUND = -1;
+
+  public static linear(List l, Object o)
+  {
+    for (int i = 0; i < l.size(); ++i)
+      if (o == null ? l.get(i) == null : o.equals(l.get(i)))
+        return i;
+    return NOT_FOUND;
+  }
+}
+\end{verbatim}
+
+From this dummy implementation, it is trivial that linear search has,
+as it name suggests, \emph{linear time} complexity.  The nullity check
+every iteration adds a bit of overhead, but if performance is ever concerned,
+the better tested and optimized standard library should be used instead.
+Moving \verb|o == null| to the upper level would require duplicating
+the \verb|for| loop, creating redundancy and making the code less readable
+and less maintainable.
+
+Unsurprisingly, 2 and -1 are returned from
+\verb|Search.linear(list, 6)| and \verb|Search.linear(list, 7)|,
+respectively.
+
+\subsection{Binary Search}
+Binary search find the position of a target value within a sorted array by
+``testing the middle of an interval, eliminating the half of the [array] in
+which the key cannot lie, and then repeating the procedure iteratively''
+\cite{bsearch}.  This could be intuitively implemented using recursion:
+\begin{verbatim}
+// ...
+public class Search
+{
+  // ...
+  private static <T>
+  int binary(List<? extends Comparable<? super T>> list, T key,
+             int low, int high)
+  {
+    if (high < low)
+      return NOT_FOUND;
+    var mid = (low + high) / 2;
+    var cmp = list.get(mid).compareTo(key);
+    if (cmp < 0)
+      return binary(list, key, mid + 1, high);
+    if (cmp > 0)
+      return binary(list, key, low, mid - 1);
+    return mid;
+  }
+}
+\end{verbatim}
+
+\verb|Search.binary| is declared as a \emph{generic method} to allow
+more implicit calls, where the compiler will \emph{infer} the type of \verb|key|
+as well as that of each element of \verb|list|~\cite{infer}.  This makes
+the method work on any type of argument that is a subclass of \verb|Comparable|,
+which is required for \verb|Comparable.compareTo|.  In fact,
+\verb|java.util.Collections.binarySearch|'s declaration follows
+the same strategy~\cite[binarySearch]{collections}.
+
+Instead of directly exposing this method where users need to provide
+the lower and higher bound of the indices, we overload it with a wrapper
+to ensure encapsulation:
+\begin{verbatim}
+// ...
+public class Search
+{
+  // ...
+  public static <T>
+  int binary(List<? extends Comparable<? super T>> list, T key)
+  {
+    return binary(list, key, 0, list.size());
+  }
+}
+\end{verbatim}
+
+To test our implementation, we first need \verb|list| to be sorted.
+By providing \verb|null| to its \verb|sort| method, we can sort it
+in the elements' natural (ascending) order~\cite[sort]{list}.
+As \verb|list| is now [4, 6, 9, 20], \verb|Search.binary(list, 6)|
+and \verb|Search.binary(list, 7)| return 1 and -1 respectively.
+
+\verb|java.util.Collections.binarySearch(list, 7)| gives -3, however,
+due to its slightly different behavior:
+\begin{quote}
+  [If \verb|key| is not in the list, returns] \verb|(-(insertion point) - 1)|.
+  The insertion point is defined as the point at which the key would be
+  inserted into the list: the index of the first element greater than the key,
+  or \verb|list.size()| if all elements in the list are less than
+  the specified key.~\cite[binarySearch]{collections}
+\end{quote}
+
+Since the algorithm only give up the search until the array is bisected to
+a nonpositive length (\verb|high < low|), the time-complexity of binary search
+is asymptotic to $\log_2 n$, where $n$ is the size of the array.
+In other words, on modern 64-bit computers with support for at most 18EB
+of address space, the running time is still negligible (64 comparisons).
+Despite the use of \verb|List| interface in the implementation,
+\verb|Search.binary| is not $\Theta(\lg n)$\footnote{The notation
+$f = \Theta(g)$ indicates that $f$ grows at the same rate as $g$.}
+on \verb|LinkedList|, which has $\Theta(n)$ random access.
+
+Since the algorithm only works on ordered lists, it is not
+suitable for iteratively inserting to a sorted list, as for linear
+data structures, either random access or middle insertion has to be
+$\Omega(n)$\footnote{The notation $f = \Omega(g)$ indicates that $f$ grows at
+least as as fast as $g$.}.  In that case, self-balancing binary search tree
+should be used instead.
+\pagebreak
+
+\section{Sorting}
+The sorting problem is stated in~\cite[p. 638]{wu} as
+\begin{quote}
+  Given an array of $n$ values, arrange the values into ascending order.
+\end{quote}
+
+This section discusses only three sorting algorithms,
+namely selection sort, bubble sort and heapsort.
+
+\subsection{Selection Sort}
+Selection sort could be performed by iterating through every position and select
+the minimum element from the current one to the end of the array.  The in-place
+algorithm could be implemented in Java as follows:
+\begin{verbatim}
+import java.util.List;
+
+import static java.util.Collections.swap;
+
+public class Sort
+{
+  public static <T extends Comparable<? super T>>
+  void selection(List<T> list)
+  {
+    int i, j, m, n = list.size();
+    for (i = 0; i < n; ++i)
+      {
+        for (m = j = i; j < n; ++j)
+          if (list.get(j).compareTo(list.get(m)) < 0)
+            m = j;
+        swap(list, i, m);
+      }
+  }
+}
+\end{verbatim}
+
+Since only atomic \verb|int|'s are introduced, the space complexity is
+$\Theta(1)$.  The time complexity is, in term of swaps, $\Theta(n)$
+and, in term of comparisons,
+\[T(n) = \sum_{i=0}^{n-1}\sum_{j=i}^{n-1}1
+       = \sum_{i=0}^{n-1}(n - i)
+       = \sum_{i=1}^{n}i
+       = \frac{n^2 + n}{2}
+       = \Theta(n^2)\]
+
+One could micro-optimize by tweaking \verb|i|'s and \verb|j|'s
+bounds by an unit but that does not make the algorithm
+any faster asymptotically.
+
+Just to make sure everything works correctly, we do a simple check
+\begin{verbatim}
+var list = java.util.Arrays.asList("foo", "bar", "baz");
+Sort.selection(list);
+System.out.println(list);
+\end{verbatim}
+and get \verb|[bar, baz, foo]| printed to \verb|stdout| as expected.
+
+\subsection{Bubble Sort}
+In~\cite[p. 646]{wu}, the author praised bubble sort to finish sooner than
+selection sort on average and best cases.  Whilst the latter is true,
+we will try to explain why the former is generally incorrect.
+
+To do this, we first need to understand what bubble sort is.
+As defined in~\cite[p. 40]{clrs}, the code below operating on
+an array \verb|a| of size \verb|n| qualifies as bubble sort.
+\begin{verbatim}
+for (int i = n - 1; i > 0; --i)
+  for (int j = 1; j < i; ++j)
+    if (a[j] < a[j - 1])
+      swap(a, j, j - 1);
+\end{verbatim}
+
+This naïve version, like selection sort, has the time complexity $\Theta(n^2)$
+in term of comparisons (it underperform selection sort in term of swaps
+however--this will be discussed right after the implementation is completed).
+Though, as pointed out in~\cite{bubblebad},
+\begin{quote}
+  Nearly every description of bubble sort describes
+  how to terminate the sort early if the vector becomes sorted.
+\end{quote}
+
+Hence, we \emph{upgrade} the pseudocode to
+\begin{verbatim}
+boolean swapped;
+do
+  {
+    swapped = false;
+    for (int j = 1; j < n; ++j)
+      if (a[j] < a[j - 1])
+        {
+          swap(a, j, j - 1);
+          swapped = true;
+        }
+  }
+while (swapped);
+\end{verbatim}
+
+We can do further optimization avoiding comparing the last $t - 1$ items
+when running for the $t$-th time of the outer loop, as after iteration $t - 1$,
+these have already \emph{bubbled up} to its final place~\cite{wikibubble}.
+With this in mind, we write our final implementation:
+\begin{verbatim}
+// ...
+public class Sort
+{
+  // ...
+  public static <T extends Comparable<? super T>>
+  void bubble(List<T> list)
+  {
+    for (int n = list.size(), m = 0; n > 1; n = m, m = 0)
+      for (int i = 1; i < n; ++i)
+        if (list.get(i).compareTo(list.get(i - 1)) < 0)
+          swap(list, m = i, i - 1);
+  }
+}
+\end{verbatim}
+
+In the best case where the list is already sorted, during the first iteration
+of the outer loop, \verb|m| remains zero, which is then assigned to \verb|n|
+to break the loop, hence the time complexity is that of the inner loop
+or $n - 1 = \Omega(n)$.  Otherwise, denote $S$ as a subset of all
+positive integers not greater than \verb|list.size()|.  The time complexity
+would then be
+\[T(n) = \sum_{n\in S}\Theta(n)\]
+On random data, $\#S = \Theta(n)$ and thus $T(n) = \Theta(n^2)$.
+
+As demonstrated in~\cite{bubblebad}, selection sort outperforms bubble sort
+on average cage, despite their asymptotically equivalent time complexity:
+\begin{center}
+  \includegraphics[width=0.57\textwidth]{bubbleplot.jpg}
+\end{center}
+
+Looking back at~\cite[p. 646]{wu}, we are now able to spot Wu's misconception:
+\begin{quote}
+  On average, we expect the bubble sort to finish sorting sooner than
+  the selection sort, \emph{because there will be more data movements for
+  the same number of comparisons}, and there is a test to exit the method
+  when the array gets sorted.
+\end{quote}
+
+While bubble sort may take advantage of the pre-sorted parts of the array
+to do fewer comparisons, the number of swaps is $\Theta(n^2)$, which grows
+strictly faster than selection sort's $\Theta(n)$.  Consequently, instead of
+swapping more to finish faster, the bubble variant does more unnecessary
+data movements.  Furthermore, write operations on memory are usually slower
+than reading, which makes swaps much costlier than comparisons.  Finally,
+it could be summarized by a quote from Donald Knuth~\cite{peculiar},
+\begin{quote}
+  In fact, one of Demuth's main results was that in a certain sense
+  `bubble sorting' is the optimum way to sort.  [...]  It turns out that
+  [all other sorting methods studied] are always better in practice,
+  in spite of the fact that Demuth has proved the optimality of bubble sorting
+  on a certain peculiar type of machine. 
+\end{quote}
+
+\subsection{Heapsort}
+Heapsort could be viewed as an improved version of selection sort, where
+the selection is done on the right data structure: the heap~\cite{heapselect}.
+To sort an array ascendingly in place, we use a binary max-heap to keep track
+of the largest element in the unsorted region and move it to the beginning
+of the sorted one, iteratively.
+
+The binary heap is an array object $A$ which resembles a nearly completely
+filled binary tree, except possibly the lowest level.  This kind of heap has
+two attributes: $length$ of the array and $size$ of the heap,
+where $0 \le size \le length$ and valid elements of the heap only reside
+within the $[0, size)$ index interval of the array~\cite[p. 151]{clrs}.
+
+We choose \verb|java.util.List| as the interface for the inner representation
+of heap and come up with the following declaration:
+\begin{verbatim}
+import java.util.List;
+
+public class Heap<T extends Comparable<? super T>>
+{
+  private List<T> list;
+  private int size;
+  public int getSize()
+  {
+    return size;
+  }
+
+  public int getLength()
+  {
+    return list.size();
+  }
+
+  public T get(int i)
+  {
+    return list.get(i);
+  }
+}
+\end{verbatim}
+
+Since the elements are of the type \verb|Comparable|, \verb|Heap| is a max-heap
+in a purely conceptual sense.  That is, the order totally depends on
+\verb|T.compareTo|, which could be defined or overridden by the users.
+The max-heap property is then defined as that for every node $i$ other than
+the root $A_0$, $A_{\mathrm{parent}(i)} \ge A_i$, where the indices of a node's
+parent, left child and right child are given by
+\[\begin{array}{ll}
+  \mathrm{parent}(i) &= \left\lfloor\dfrac{i - 1}{2}\right\rfloor\\
+  \mathrm{left}(i) &= 2i + 1\\
+  \mathrm{right}(i) &= 2i + 2
+\end{array}\]
+
+To maintain this property at node $i$, with the assumption that
+the binary trees rooted at left($i$) and right($i$) are already max-heaps,
+we use \verb|heapify|, which sift the value at $A_i$ down the heap if it is
+smaller than its children:
+\begin{verbatim}
+// ...
+import static java.util.Collections.swap;
+
+public class Heap<T extends Comparable<? super T>>
+{
+  // ...
+  public void heapify(int i)
+  {
+    int right = i + 1 << 1;
+    int left = right - 1;
+    int largest = i;
+    if (left < size && get(left).compareTo(get(largest)) > 0)
+      largest = left;
+    if (right < size && get(right).compareTo(get(largest)) > 0)
+      largest = right;
+    if (largest != i)
+      {
+        swap(list, i, largest);
+        heapify(largest);
+      }
+  }
+}
+\end{verbatim}
+
+At each call, the index of the greatest element among $A_i$,
+$A_{\mathrm{left}(i)}$ and $A_{\mathrm{right}(i)}$ is assigned
+to \verb|largest|.  In case $A_i$ is greatest, the subtree rooted at $A_i$
+is already a max-heap and the method terminates.  Otherwise, $A_i$ is swapped
+with $A_{\mathtt{largest}}$, which makes node $i$ and its children to satisfy
+the max-heap property.  The subtree rooted at \verb|largest|, though,
+\emph{might} violate the property so \verb|heapify| needs to be called on it.
+For instance, given $i$ points to the subtree on the left, then \verb|heapify|
+would step-by-step turn it to the one on the right:
+\begin{center}
+  \begin{forest}
+    for tree={circle,draw}
+    [,phantom [4,fill=yellow [9 [0] [6]] [8 [3] [,phantom]]]
+              [9 [4,fill=yellow [0] [6]] [8 [3] [,phantom]]]
+              [9 [6 [0] [4,fill=yellow]] [8 [3] [,phantom]]]]
+  \end{forest}
+\end{center}
+
+The running time of \verb|heapify| on a subtree of height (number of edges
+between the root and the furthest leaf) $h$ is the time $\Theta(1)$) to make
+$A_i$, $A_{\mathrm{left}(i)}$ and $A_{\mathrm{right}(i)}$ a max-heap, plus
+the time to run \verb|heapify| on one of its children if necessary:
+\[T(h) \le T(h - 1) + \Theta(1)
+       \le T(0) + \sum_{i=1}^{h}\Theta(1) = T(0) + \Theta(h)\]
+Since $T(0)$ is obviously $\Theta(1)$,
+\[T(h) \leq \Theta(h) \Longrightarrow T(h) = O(h)\footnotemark\]
+A binary tree of size $n$ may have at maximum height of
+$h = \lfloor\log_2 n\rfloor$, thus the time complexity with respect to
+the size of the subtree is $O(\log_2 n)$.
+\footnotetext{The notation $f = O(g)$ indicates that $f$ grows
+at most as as fast as $g$.}
+
+Noticeably, $\forall i \ge \lfloor n/2\rfloor,\; 2i + 2 > 2i + 1 \ge n
+\iff \mathrm{right}(i) > \mathrm{left}(i) \ge n$.  In other words,
+only nodes of indices less than $\lfloor n/2\rfloor$ have children.
+Therefore, a heap could be constructed as follows
+\begin{verbatim}
+// ...
+public class Heap<T extends Comparable<? super T>>
+{
+  // ...
+  public Heap(List<T> a)
+  {
+    list = a;
+    size = a.size();
+    for (int i = size >> 1; i-- > 0;)
+      heapify(i);
+  }
+}
+\end{verbatim}
+
+Before the construction, each node from $\lfloor n/2\rfloor$ (\verb|size >> 2|)
+to $n - 1$ is a leaf and a trivial heap on its own.  Consider the iteration
+where \verb|heapify| is called on node $i$ and assume every node after $i$
+is the root of a heap beforehand, then after the iteration, all nodes from $i$
+to $n - 1$ are foots of max-heaps.  Consequently, by mathematical induction,
+after the construction, the whole array becomes a heap.  According
+to~\cite[p. 159]{clrs}, this constructor runs in linear time ($O(n)$).
+
+Heapsort uses the max-heap to select the next largest element to move it
+to the start of the sorted region.  This in-place movement could be implemented
+as the method \verb|pop|, which also return the largest element to make
+the method make sense on its own.
+\begin{verbatim}
+// ...
+public class Heap<T extends Comparable<? super T>>
+{
+  // ...
+  public T pop() throws RuntimeException
+  {
+    if (size < 1)
+      throw new RuntimeException("heap underflow");
+    swap(list, 0, --size);
+    heapify(0);
+    return get(size);
+  }
+}
+\end{verbatim}
+
+Choosing the $n - 1$ largest element, we are left with the minimum value at
+the beginning of the list and the rest of the list are all greater or equal to
+the first element.
+\begin{verbatim}
+// ...
+public class Sort
+{
+  // ...
+  public static <T extends Comparable<? super T>>
+  void heap(List<T> list)
+  {
+    var heap = new Heap<T>(list);
+    for (int i = 1; i < list.size(); ++i)
+      heap.pop();
+  }
+}
+\end{verbatim}
+
+The step-by-step selection from the example heap is shown below as
+an illustration.  One may notice that the result qualifies as a min-heap.
+\begin{center}
+  \begin{forest}
+    for tree={circle,draw}
+    [,phantom [9 [6 [0] [4]] [8 [3] [,phantom]]]
+              [8 [6 [0] [4]] [3 [9,edge=dotted] [,phantom]]]
+              [6 [4 [0] [8,edge=dotted]] [3 [9,edge=dotted] [,phantom]]]]
+  \end{forest}
+\end{center}
+\begin{center}
+  \begin{forest}
+    for tree={circle,draw}
+    [,phantom [4 [0 [6,edge=dotted] [8,edge=dotted]]
+                 [3 [9,edge=dotted] [,phantom]]]
+              [3 [0 [6,edge=dotted] [8,edge=dotted]]
+                 [4,edge=dotted [9,edge=dotted] [,phantom]]]
+              [0 [3,edge=dotted [6,edge=dotted] [8,edge=dotted]]
+                 [4,edge=dotted [9,edge=dotted] [,phantom]]]]
+  \end{forest}
+\end{center}
+
+The running time of \verb|Sort.heap| is that of \verb|Heap| constructor,
+plus $n - 1$ times that of \verb|Heap.pop|, which is
+\begin{align*}
+  T(n) &= O(n) + (n - 1)(\Theta(1) + O(\log_2 n))\\
+       &= O(n) + \Theta(n)O(\log_2 n)\\
+       &= O(n) + O(n\log_2 n)\\
+       &= O(n\log_2 n)
+\end{align*}
+This is a huge improvement from selection sort's and bubble sort's $O(n^2)$.
+\pagebreak
+
+\section{Comparing}\label{sec:cmp}
+Our implementations of searching and sorting algorithms in Java work on
+any collection of data whose \emph{natural} order is specified, that is,
+where elements implement \verb|Comparable|.  However, they does not cover
+the case \emph{another} order is required, there is not any option to use
+our current library other than subclassing every item with a different
+\verb|compareTo| method, which, in every sense, is counter-intuitive.
+
+In~\cite{wu}, Wu dedicated a whole ``Sample Development'' section to address
+this issue and came up with the final solution of using the standard interface
+\verb|java.util.Comparator|~\cite{cmp} which declare the method \verb|compare|.
+We start with refactoring \verb|Sort.selection| to comply with this facility:
+\begin{verbatim}
+// ...
+import java.util.Comparator;
+
+public class Sort
+{
+  public static <T>
+  void selection(List<T> list, Comparator<T> comparator)
+  {
+    int i, j, m, n = list.size();
+    for (i = 0; i < n; ++i)
+      {
+        for (m = j = i; j < n; ++j)
+          if (comparator.compare(list.get(j), list.get(m)) < 0)
+            m = j;
+        swap(list, i, m);
+      }
+  }
+}
+\end{verbatim}
+
+To sort in reversed order, we can subclass \verb|Comparator|
+anonymously~\cite{anon}
+\begin{verbatim}
+var list = java.util.Arrays.asList(4, 2, 0, 6, 9);
+Sort.selection(list, new java.util.Comparator<Integer>()
+{
+  public int compare(Integer a, Integer b)
+  {
+    return -a.compareTo(b);
+  }
+});
+System.out.println(list);
+\end{verbatim}
+
+As expected, the snippet above prints \verb|[9, 6, 4, 2, 0]| to \verb|stdout|.
+
+In order to maintain backward-comparability, we write a helper class extracting
+the natural order from any \verb|Comparable| to a \verb|Comparator|:
+\begin{verbatim}
+import java.util.Comparator;
+
+public class Compare<T extends Comparable<? super T>>
+implements Comparator<T>
+{
+  public int compare(T a, T b)
+  {
+    return a.compareTo(b);
+  }
+}
+\end{verbatim}
+and wrap the current \verb|Sort.selection| with
+\begin{verbatim}
+// ...
+public class Sort
+{
+  // ...
+  public static <T extends Comparable<? super T>>
+  void selection(List<T> list)
+  {
+    selection(list, new Compare<T>());
+  }
+}
+\end{verbatim}
+
+\verb|Sort.bubble| can be refactored similarly, but since \verb|Sort.heap|
+does all the comparisons in \verb|Heap|, we are required to make \verb|Heap|
+work with \verb|Comparator|'s
+\begin{verbatim}
+// ...
+import java.util.Comparator;
+
+public class Heap<T>
+{
+  // ...
+  private Comparator<T> cmp;
+
+  public void heapify(int i)
+  {
+    int right = i + 1 << 1;
+    int left = right - 1;
+    int largest = i;
+    if (left < size && cmp.compare(get(left), get(largest)) > 0)
+      largest = left;
+    if (right < size && cmp.compare(get(right), get(largest)) > 0)
+      largest = right;
+    if (largest != i)
+      {
+        swap(list, i, largest);
+        heapify(largest);
+      }
+  }
+
+  public Heap(List<T> a, Comparator<T> c)
+  {
+    list = a;
+    size = a.size();
+    cmp = c;
+    for (int i = size >> 1; i-- > 0;)
+      heapify(i);
+  }
+}
+\end{verbatim}
+and re-write \verb|Sort.heap| to use the new \verb|Heap|
+\begin{verbatim}
+// ...
+public class Sort
+{
+  // ...
+  public static <T>
+  void heap(List<T> list, Comparator<T> comparator)
+  {
+    var heap = new Heap<T>(list, comparator);
+    for (int i = 1; i < list.size(); ++i)
+      heap.pop();
+  }
+
+  public static <T extends Comparable<? super T>>
+  void heap(List<T> list)
+  {
+    heap(list, new Compare<T>());
+  }
+}
+\end{verbatim}
+
+For the next example, we use a minimal, read-only version of the \verb|Person|
+class from~\cite[p. 666]{wu}, which is ordered by \verb|name| by default:
+\begin{verbatim}
+public class Person implements Comparable<Person>
+{
+  private String name;
+  private Integer age;
+  private Character gender;
+
+  public Person(String name, Integer age, Character gender)
+  {
+    this.name = name;
+    this.age = age;
+    this.gender = gender;
+  }
+
+  public int compareTo(Person other)
+  {
+    return this.name.compareTo(other.name);
+  }
+
+  public String toString()
+  {
+    return String.format("%s (%d%c)", name, age, gender);
+  }
+
+  public String getName()
+  {
+    return name;
+  }
+
+  public Integer getAge()
+  {
+    return age;
+  }
+ 
+  public Character getGender()
+  {
+    return gender;
+  }
+}
+\end{verbatim}
+
+We use a list of the oldest current state leaders~\cite{old} for this test
+\begin{verbatim}
+var list = java.util.Arrays.asList(
+  new Person("Mahathir Mohamad", 94, 'M'),
+  new Person("Elizabeth II", 93, 'F'),
+  new Person("Sheikh Sabah Al-Ahmad Al-Jaber Al-Sabah", 90, 'M'),
+  new Person("Paul Biya", 86, 'M'),
+  new Person("Michel Aoun", 84, 'M'),
+  new Person("Mahmoud Abbas", 83, 'M'),
+  new Person("Francis", 82, 'M'));
+Sort.heap(list);
+list.forEach(System.out::println);
+\end{verbatim}
+and get
+\begin{verbatim}
+Elizabeth II (93F)
+Francis (82M)
+Mahathir Mohamad (94M)
+Mahmoud Abbas (83M)
+Michel Aoun (84M)
+Paul Biya (86M)
+Sheikh Sabah Al-Ahmad Al-Jaber Al-Sabah (90M)
+\end{verbatim}
+
+It would neither be challenging to re-sort this list by their ages:
+\begin{verbatim}
+var ageComparator = new java.util.Comparator<Person>()
+{
+  public int compare(Person a, Person b)
+  {
+    return a.getAge().compareTo(b.getAge());
+  }
+};
+Sort.heap(list, ageComparator);
+list.forEach(System.out::println);
+\end{verbatim}
+which gives us
+\begin{verbatim}
+Francis (82M)
+Mahmoud Abbas (83M)
+Michel Aoun (84M)
+Paul Biya (86M)
+Sheikh Sabah Al-Ahmad Al-Jaber Al-Sabah (90M)
+Elizabeth II (93F)
+Mahathir Mohamad (94M)
+\end{verbatim}
+
+Linear search is able to run without any modification: we would still receive
+4 from \verb|Search.linear(list, list.get(4))|.  Binary search, however,
+would not work correctly if the order of the list is not \emph{natural}.
+One with \verb|Comparator| support may be implemented as follows.
+\begin{verbatim}
+import java.util.List;
+import java.util.Comparator;
+
+public class Search
+{
+  // ...
+  private static <T>
+  int binary(List<? extends T> list, T key,
+             Comparator<? super T> c, int low, int high)
+  {
+    if (high < low)
+      return NOT_FOUND;
+    var mid = (low + high) / 2;
+    var cmp = c.compare(list.get(mid), key);
+    if (cmp < 0)
+      return binary(list, key, c, mid + 1, high);
+    if (cmp > 0)
+      return binary(list, key, c, low, mid - 1);
+    return mid;
+  }
+
+  public static <T>
+  int binary(List<? extends T> list, T key,
+             Comparator<? super T> c)
+  {
+    return binary(list, key, c, 0, list.size());
+  }
+}
+\end{verbatim}
+
+Now \verb|Search.binary(list, list.get(5), ageComparator)| would return
+the right index 5 instead of -1 like \verb|Search.binary(list, list.get(5))|.
+\pagebreak
+
+\section{Conclusion}
+Albeit searching and sorting belong to the category of algorithms,
+by implementing them, we were still able to recognize a variety of
+object-oriented concepts, namely:
+\begin{enumerate}
+  \item Through encapsulation of the inner representations
+    and behaviors, we can create intuitive programming interfaces,
+    whilst keeping the code clear and concise.  Notable examples are
+    the implementation of binary search and the heap data structure.
+  \item Through polymorphism, generic and convenient libraries can be written,
+    which allow more \emph{code reuse} and thus facilitate more effective
+    development.  We wrote all of the classes and methods with this principle
+    in mind.
+  \item Through inheritance, it is possible to extend the functionalities of
+    each object.  Together with polymorphism (which defines the behavioral
+    interfaces), it enable us to generalize our codebase one step further,
+    as shown in section~\ref{sec:cmp}, without spending too much energy
+    on refactoring.
+\end{enumerate}
+
+Generally, though, we find shoving every self-contained function into a class
+as a static method rather redundant.
+\pagebreak
+
+\begin{thebibliography}{99}
+  \bibitem{wu} C. Thomas Wu.
+    ``Chapter 11: Sorting and Searching''.
+    \emph{An Introduction to Object-Oriented Programming with Java}, 5 ed.
+    McGraw-Hill, 2010.  ISBN 978–0–07–352330–9.
+  \bibitem{list} \href{https://docs.oracle.com/javase/8/docs/api/java/util/List.html}{List (Java Platform SE 8)}.
+    \emph{Oracle}.
+  \bibitem{var} \href{http://openjdk.java.net/jeps/286}{JEP 286: Local-Variable Type Inference}.
+    \emph{OpenJDK}.
+  \bibitem{bsearch} \href{http://mathworld.wolfram.com/BinarySearch.html}{Binary Search}.
+    \emph{Wolfram WathWorld}.
+  \bibitem{infer} \href{https://docs.oracle.com/javase/tutorial/java/generics/methods.html}{Generic Methods}.
+    \emph{Oracle}.
+  \bibitem{collections} \href{https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html}{Collections (Java Platform SE 8)}.
+    \emph{Oracle}.
+  \bibitem{clrs} Thomas H. Cormen, Charles E. Leiserson,
+                 Ronald L. Rivest and Clifford Stein.
+    \emph{Introduction to Algorithms}, 3 ed.
+    MIT Press, 2009.  ISBN 978-0-262-03384-8.
+  \bibitem{bubblebad} Owen Astrachan.
+    \emph{\href{https://users.cs.duke.edu/~ola/bubble/bubble.html}{Bubble Sort: An Archaeological Algorithmic Analysis}}.
+    Duke University.
+  \bibitem{wikibubble} \href{https://en.wikipedia.org/wiki/Bubble_sort#Optimizing_bubble_sort}{Bubble sort}.
+    \emph{Wikipedia}.
+    Section 2.2: \emph{Optimizing bubble sort}.
+  \bibitem{peculiar} Donald E. Knuth.  The Dangers of Computer-Science Theory.
+    \emph{Studies in Logic and the Foundations of Mathematics}, vol. 74.
+    Elsevier, 1973.
+    doi:\href{https://doi.org/10.1016/S0049-237X(09)70357-X}{10.1016/S0049-237X(09)70357-X}.
+  \bibitem{heapselect} Steven Skiena.
+    ``Searching and Sorting''.
+    \emph{The Algorithm Design Manual}, p. 109.
+    Springer, 2008.
+    doi:\href{https://doi.org/10.1007/978-1-84800-070-4_4}{10.1007/978-1-84800-070-4{\_}4}.
+    ISBN 978-1-84800-069-8.
+  \bibitem{cmp} \href{https://docs.oracle.com/javase/8/docs/api/java/util/mparator.html}{Comparator (Java Platform SE 8)}.
+    \emph{Oracle}.
+  \bibitem{anon} \href{https://docs.oracle.com/javase/tutorial/java/javaOO/anonymousclasses.html}{Anonymous Classes}.
+    \emph{Oracle}.
+  \bibitem{old} \href{https://en.wikipedia.org/wiki/Lists_of_state_leaders_by_age#10_oldest_currently_serving_state_leaders}{Lists of state leaders by age}.
+    \emph{Wikipedia}.
+    Section 1: \emph{10 oldest currently serving state leaders}.
+\end{thebibliography}
+\end{document}
-- 
cgit 1.4.1

