\documentclass[10pt,a4paper]{article}

% Packages
\usepackage{fancyhdr}           % For header and footer
\usepackage{multicol}           % Allows multicols in tables
\usepackage{tabularx}           % Intelligent column widths
\usepackage{tabulary}           % Used in header and footer
\usepackage{hhline}             % Border under tables
\usepackage{graphicx}           % For images
\usepackage{xcolor}             % For hex colours
%\usepackage[utf8x]{inputenc}    % For unicode character support
\usepackage[T1]{fontenc}        % Without this we get weird character replacements
\usepackage{colortbl}           % For coloured tables
\usepackage{setspace}           % For line height
\usepackage{lastpage}           % Needed for total page number
\usepackage{seqsplit}           % Splits long words.
%\usepackage{opensans}          % Can't make this work so far. Shame. Would be lovely.
\usepackage[normalem]{ulem}     % For underlining links
% Most of the following are not required for the majority
% of cheat sheets but are needed for some symbol support.
\usepackage{amsmath}            % Symbols
\usepackage{MnSymbol}           % Symbols
\usepackage{wasysym}            % Symbols
%\usepackage[english,german,french,spanish,italian]{babel}              % Languages

% Document Info
\author{Jianmin Feng (taotao)}
\pdfinfo{
  /Title (java-searching-and-sorting.pdf)
  /Creator (Cheatography)
  /Author (Jianmin Feng (taotao))
  /Subject (Java Searching and Sorting Cheat Sheet)
}

% Lengths and widths
\addtolength{\textwidth}{6cm}
\addtolength{\textheight}{-1cm}
\addtolength{\hoffset}{-3cm}
\addtolength{\voffset}{-2cm}
\setlength{\tabcolsep}{0.2cm} % Space between columns
\setlength{\headsep}{-12pt} % Reduce space between header and content
\setlength{\headheight}{85pt} % If less, LaTeX automatically increases it
\renewcommand{\footrulewidth}{0pt} % Remove footer line
\renewcommand{\headrulewidth}{0pt} % Remove header line
\renewcommand{\seqinsert}{\ifmmode\allowbreak\else\-\fi} % Hyphens in seqsplit
% This two commands together give roughly
% the right line height in the tables
\renewcommand{\arraystretch}{1.3}
\onehalfspacing

% Commands
\newcommand{\SetRowColor}[1]{\noalign{\gdef\RowColorName{#1}}\rowcolor{\RowColorName}} % Shortcut for row colour
\newcommand{\mymulticolumn}[3]{\multicolumn{#1}{>{\columncolor{\RowColorName}}#2}{#3}} % For coloured multi-cols
\newcolumntype{x}[1]{>{\raggedright}p{#1}} % New column types for ragged-right paragraph columns
\newcommand{\tn}{\tabularnewline} % Required as custom column type in use

% Font and Colours
\definecolor{HeadBackground}{HTML}{333333}
\definecolor{FootBackground}{HTML}{666666}
\definecolor{TextColor}{HTML}{333333}
\definecolor{DarkBackground}{HTML}{A3A3A3}
\definecolor{LightBackground}{HTML}{F3F3F3}
\renewcommand{\familydefault}{\sfdefault}
\color{TextColor}

% Header and Footer
\pagestyle{fancy}
\fancyhead{} % Set header to blank
\fancyfoot{} % Set footer to blank
\fancyhead[L]{
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{C}
    \SetRowColor{DarkBackground}
    \vspace{-7pt}
    {\parbox{\dimexpr\textwidth-2\fboxsep\relax}{\noindent
        \hspace*{-6pt}\includegraphics[width=5.8cm]{/web/www.cheatography.com/public/images/cheatography_logo.pdf}}
    }
\end{tabulary}
\columnbreak
\begin{tabulary}{11cm}{L}
    \vspace{-2pt}\large{\bf{\textcolor{DarkBackground}{\textrm{Java Searching and Sorting Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{Jianmin Feng (taotao)} via \textcolor{DarkBackground}{\uline{cheatography.com/79308/cs/19310/}}}
\end{tabulary}
\end{multicols}}

\fancyfoot[L]{ \footnotesize
\noindent
\begin{multicols}{3}
\begin{tabulary}{5.8cm}{LL}
  \SetRowColor{FootBackground}
  \mymulticolumn{2}{p{5.377cm}}{\bf\textcolor{white}{Cheatographer}}  \\
  \vspace{-2pt}Jianmin Feng (taotao) \\
  \uline{cheatography.com/taotao} \\
  \end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Cheat Sheet}}  \\
   \vspace{-2pt}Not Yet Published.\\
   Updated 17th May, 2019.\\
   Page {\thepage} of \pageref{LastPage}.
\end{tabulary}
\vfill
\columnbreak
\begin{tabulary}{5.8cm}{L}
  \SetRowColor{FootBackground}
  \mymulticolumn{1}{p{5.377cm}}{\bf\textcolor{white}{Sponsor}}  \\
  \SetRowColor{white}
  \vspace{-5pt}
  %\includegraphics[width=48px,height=48px]{dave.jpeg}
  Measure your website readability!\\
  www.readability-score.com
\end{tabulary}
\end{multicols}}




\begin{document}
\raggedright
\raggedcolumns

% Set font size to small. Switch to any value
% from this page to resize cheat sheet text:
% www.emerson.emory.edu/services/latex/latex_169.html
\footnotesize % Small font.

\begin{multicols*}{3}

\begin{tabularx}{5.377cm}{x{2.78712 cm} x{2.18988 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Selection sort}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{select min in array{[}0...{]} and put in array{[}0{]}} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{5.377cm}}{select min in subarray {[}1...{]} \& put in array{[}1{]}} \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{...} \tn 
% Row Count 3 (+ 1)
% Row 3
\SetRowColor{white}
process & n-1 \tn 
% Row Count 4 (+ 1)
% Row 4
\SetRowColor{LightBackground}
worst case=best case=average & n*n = n-1 +n-2+...+2+1 \tn 
% Row Count 6 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{Buble sort: swapping adjacent element, instead select and swap once. slower than selection sort in average, but best case is better ( n instead n*n for select}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{2.23965 cm} x{2.73735 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Insertion sort}}  \tn
% Row 0
\SetRowColor{LightBackground}
a{[}0{]} is treated as sorted part & arr{[}1...{]} is treated as unsorted part \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{5.377cm}}{each unsorted is inserted into sorted part in order} \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
processes & n-1 \tn 
% Row Count 5 (+ 1)
% Row 3
\SetRowColor{white}
worst case(reversed ordered) & n*n \tn 
% Row Count 7 (+ 2)
% Row 4
\SetRowColor{LightBackground}
best case( sorted in order) & n \tn 
% Row Count 9 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{2.28942 cm} x{2.68758 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Merge sort}}  \tn
% Row 0
\SetRowColor{LightBackground}
1 split into 2 part & 2 recursive sort left and right part \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
3 leaf node has 1 or 2 elements & 4 and merge \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
disadvantage & temporary arrays, extra space \tn 
% Row Count 6 (+ 2)
% Row 3
\SetRowColor{white}
advantage & fast \tn 
% Row Count 7 (+ 1)
% Row 4
\SetRowColor{LightBackground}
process & nlog(n) \tn 
% Row Count 8 (+ 1)
% Row 5
\SetRowColor{white}
cost & n*log(n) \tn 
% Row Count 9 (+ 1)
% Row 6
\SetRowColor{LightBackground}
worst case=best case=average & input not affect performance \tn 
% Row Count 11 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{2.14011 cm} x{2.83689 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Quick Sort}}  \tn
% Row 0
\SetRowColor{LightBackground}
partition array by pivot value & recursive sort \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{2}{x{5.377cm}}{scan from both end, swap the bigger on the left to the smaller on the right,until left and right reach the same index, then swap a{[}pivotposition{]} with a{[}0{]}} \tn 
% Row Count 6 (+ 4)
% Row 2
\SetRowColor{LightBackground}
best case & fastest sort \tn 
% Row Count 7 (+ 1)
% Row 3
\SetRowColor{white}
Worst case & split into 0, 1..n-1 always, sorted array using a{[}0{]} as pivot \tn 
% Row Count 10 (+ 3)
% Row 4
\SetRowColor{LightBackground}
 & become recursive selection sort \tn 
% Row Count 12 (+ 2)
% Row 5
\SetRowColor{white}
 & shuffle or select midden of first several element as pivot \tn 
% Row Count 15 (+ 3)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{worst case is very inefficient}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{Compare Sort algorithm}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{for small n, select and insert sort used, n \textasciitilde{}= 7, machine dependent} \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{for larger n, divide and conquer sort used, until reach a small number.} \tn 
% Row Count 4 (+ 2)
% Row 2
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{in Java, sort array with object type requires the object class must have compareTo() overriden} \tn 
% Row Count 6 (+ 2)
% Row 3
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{Sorting evaluation: CPU time, memory used, array size ( Merge sort( larger)-{}-\textgreater{} quick sort(small) -{}-\textgreater{} \textless{}7 select/insert sort)} \tn 
% Row Count 9 (+ 3)
% Row 4
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{sorting process and intermediate results -{}- on test} \tn 
% Row Count 11 (+ 2)
% Row 5
\SetRowColor{white}
\mymulticolumn{1}{x{5.377cm}}{comparison, swap or change, space requirement} \tn 
% Row Count 12 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{3.83229 cm} p{1.14471 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Sequential search}}  \tn
% Row 0
\SetRowColor{LightBackground}
best case & 1 \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
worst case & n \tn 
% Row Count 2 (+ 1)
% Row 2
\SetRowColor{LightBackground}
average & n/2 \tn 
% Row Count 3 (+ 1)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{be careful with the code: index}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{x{2.58804 cm} x{2.38896 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{2}{x{5.377cm}}{\bf\textcolor{white}{Binary Search}}  \tn
% Row 0
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{Array must be sorted in searching key} \tn 
% Row Count 1 (+ 1)
% Row 1
\SetRowColor{white}
if n is not power of two, worst case & log(n) with n round to power(z,n) \tn 
% Row Count 3 (+ 2)
% Row 2
\SetRowColor{LightBackground}
 & \textgreater{}a{[}n-2{]}, \textless{}a{[}1{]} \tn 
% Row Count 4 (+ 1)
% Row 3
\SetRowColor{white}
if n is power(2), worst case & log(n) +1 \tn 
% Row Count 6 (+ 2)
% Row 4
\SetRowColor{LightBackground}
 & \textgreater{}a{[}n-2{]} \tn 
% Row Count 7 (+ 1)
% Row 5
\SetRowColor{white}
 & \textless{}a{[}1{]} is log(n), 1 less \tn 
% Row Count 9 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\SetRowColor{LightBackground}
\mymulticolumn{2}{x{5.377cm}}{fully understand the binary sort passes and cost. \newline The final is either equals an element a{[}middle{]} or not in the range. \newline split subarray does not include a{[}mid{]}}  \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}--}
\end{tabularx}
\par\addvspace{1.3em}


% That's all folks
\end{multicols*}

\end{document}