diff options
Diffstat (limited to 'usth/ICT2.2/midterm/report/report.tex')
| -rw-r--r-- | usth/ICT2.2/midterm/report/report.tex | 928 |
1 files changed, 928 insertions, 0 deletions
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} |