\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{greatcraic}
\pdfinfo{
  /Title (algoritmica.pdf)
  /Creator (Cheatography)
  /Author (greatcraic)
  /Subject (Algoritmica 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{Algoritmica Cheat Sheet}}}} \\
    \normalsize{by \textcolor{DarkBackground}{greatcraic} via \textcolor{DarkBackground}{\uline{cheatography.com/21020/cs/3866/}}}
\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}greatcraic \\
  \uline{cheatography.com/greatcraic} \\
  \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 12th May, 2016.\\
   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}{p{0.77809 cm} x{1.87657 cm} x{1.92234 cm} }
\SetRowColor{DarkBackground}
\mymulticolumn{3}{x{5.377cm}}{\bf\textcolor{white}{Algoritmi di ordinamento}}  \tn
% Row 0
\SetRowColor{LightBackground}
\seqsplit{ALGORITMO} & Tempo & Spazio \tn 
% Row Count 2 (+ 2)
% Row 1
\SetRowColor{white}
\seqsplit{Selection} Sort & Θ(n\textasciicircum{}2\textasciicircum{}) & sul posto Θ(1) \tn 
% Row Count 5 (+ 3)
% Row 2
\SetRowColor{LightBackground}
\seqsplit{Insertion} Sort * & Ottimo: Θ (n)      Medio:  Θ(n\textasciicircum{}2\textasciicircum{}) Pessimo Θ(n\textasciicircum{}2\textasciicircum{}) & sul posto Θ(1) \tn 
% Row Count 9 (+ 4)
% Row 3
\SetRowColor{white}
\seqsplit{MergeSort} * & Θ (n log n) & Θ(n) \tn 
% Row Count 11 (+ 2)
% Row 4
\SetRowColor{LightBackground}
\seqsplit{QuickSort} & Ottimo Θ(nlogn) Medio:  Θ(nlogn) Pessimo: Θ(n\textasciicircum{}2\textasciicircum{}) & sul posto Θ(1) (ma spazio non costante x ricorsione) \tn 
% Row Count 15 (+ 4)
% Row 5
\SetRowColor{white}
\seqsplit{HeapSort} & Θ (n log n) & sul posto Θ(1) \tn 
% Row Count 17 (+ 2)
% Row 6
\SetRowColor{LightBackground}
\seqsplit{CountingSort} * & Θ (n + k) &  \tn 
% Row Count 20 (+ 3)
% Row 7
\SetRowColor{white}
\seqsplit{RadixSort} * & Θ (d(n+k)) &  \tn 
% Row Count 22 (+ 2)
\hhline{>{\arrayrulecolor{DarkBackground}}---}
\end{tabularx}
\par\addvspace{1.3em}

\begin{tabularx}{5.377cm}{X}
\SetRowColor{DarkBackground}
\mymulticolumn{1}{x{5.377cm}}{\bf\textcolor{white}{SelectionSort}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{for}} i =1 to n-1 \{ \newline    minimo = i; \newline    {\bf{for}} j=i+1 to n \{ \newline       if (a{[}j{]} \textless{} a{[}minimo{]}) minimo = j; \newline    \} \newline    scambia a{[}j{]} e a{[}minimo{]}; \newline \}} \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}{Insertion Sort}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\bf{for}} j = 2 to n \{ \newline    key = a{[}j{]}; \newline    i = j - 1; \newline    {\bf{while}} (i \textgreater{} 0 \&\& a{[}i{]} \textgreater{} key) \{ \newline        a{[}i+1{]} = a{[}i{]}; \newline        i-{}-; \newline    \} \newline a{[}i+1{]} = key; \newline \}} \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}{MergeSort}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\emph{MergeSort(a, sx, dx)}} \newline {\bf{if}} (sx \textless{} dx) \{  \newline    cx = (sx+dx)/2; //parte intera inferiore \newline    {\bf{MergeSort}}(a, sx, cx); \newline    {\bf{MergeSort}}(a, cx+1, dx); \newline    {\bf{Merge}}(a, sx, cx, dx); \newline \} \newline  \newline {\emph{Merge(a, sx, cx, dx)}} \newline n1 = cx - sx + 1; \newline n2 = dx - cx; \newline L = nuovo array di dim n1+1 \newline R = nuovo array di dim n2+1 \newline {\bf{for}}(i = 1; i ≤ n1; i++) L{[}i{]} = a{[}sx+i-1{]}; \newline {\bf{for}}(j = 1; j ≤ n1; j++) R{[}j{]} = a{[}cx+j{]}; \newline L{[}n1+1{]} = ∞ //sentinella \newline R{[}n2+1{]} = ∞ //sentinella \newline i = 1; \newline j = 1; \newline {\bf{for}}(k=sx; k ≤ dx; k++) \{ \newline    {\bf{if}} (L{[}i{]} ≤ r{[}j{]}) \{a{[}k{]} = L{[}i{]}; i++;\} \newline    {\bf{else}} \{a{[}k{]} = R{[}j{]}; j++\} \newline {]}} \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}{QuickSort}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\emph{QuickSort(A, p, r)}} \newline {\bf{if}} (p \textless{} r) \{ \newline    q = partition(A, p, r); \newline    QuickSort(A, p, q-1); \newline    QuickSort(A, q+1, r); \newline \} \newline  \newline {\emph{Partition}}(A, p, r) \{  \newline //nella versione random generare {\bf{i}} = numero //random tra p e r  \newline //e metterlo in fondo \newline    x = A{[}r{]}; \newline    i = p-1; \newline    {\bf{for}} j = p to r -1 \{ \newline       {\bf{if}}(a{[}j{]} ≤ x) \{ \newline          i++; \newline          scambia A{[}i{]} con A{[}j{]}; \newline       \} \newline    \} \newline scambia(A{[}i+1{]}, A{[}r{]}); \newline return i+1;} \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}{Heap}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\emph{Max-Heapify(A, i)}} \newline   l = Left(i); \newline   r = Right(i); \newline   {\bf{if}} l ≤ A.heapsize and A{[}l{]} \textgreater{} A{[}i{]} \newline     massimo = l; \newline   {\bf{else}} massimo = i; \newline   {\bf{if}} r ≤ A.heapsize and A{[}r{]} \textgreater{} A{[}massimo{]} \newline     massimo = r; \newline   {\bf{if}} massimo ≠ i  \newline     scambia A{[}i{]} con A{[}massimo{]}; \newline     Max-Heapify(A, massimo); \newline  \newline {\emph{Build-Max-Heap}} \newline   A.heapsize = A.length; \newline   {\bf{for}} i = A.length/2 downto 1 \newline     Max-Heapify(A, i); \newline  \newline {\emph{Heapsort(A)}} \newline   Build-Max-Heap(A); \newline   {\bf{for}} i = A.length downto 2  \newline     scambia A{[}1{]} con A{[}i{]} \newline     A.heapsize-{}-; \newline     Max-Heapify(A, 1);} \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}{Code di priorità}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\emph{Heap-Maximum(A)}} return A{[}1{]}; \newline  \newline {\emph{Heap-Extract-Max(A)}} \newline   {\bf{if}} A.heap-size \textless{} 1 \newline     {\bf{error}} "underflow dell'heap" \newline   max = A{[}1{]}; \newline   A{[}1{]} = A{[}A.heapsize{]} \newline   A.heapsize-{}-; \newline   Max-Heapify(A, 1); \newline   {\bf{return}} max; \newline  \newline {\emph{Heap-Increase-Key (A, i, key)}} \newline   {\bf{if}} key \textless{} A{[}i{]} \newline     {\bf{error}} "la nuova chiave è più piccola di  \newline            quella corrente"; \newline   A{[}i{]} = key; \newline   {\bf{while}} i \textgreater{} 1 and A{[}Parent(i){]} \textless{} A{[}i{]} \newline     scambia A{[}i{]} con A{[}Parent(i){]}; \newline     i = Parent(i); \newline  \newline {\emph{Max-Heap-Insert(A, key)}} \newline   A.heapsize++; \newline   A{[}A.heapsize{]} = -∞; \newline   Heap-Increase-key (A, A.heapsize, key)} \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}{CountingSort}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\emph{CountingSort (A, k)}} \newline C{[}0..k{]} nuovo array di dimensione k  \newline //nota che qui conto da 0 \newline {\bf{for}} i = 0 to k \newline   C{[}i{]} = 0; \newline {\bf{for}} i = 0 to n  \newline   C{[}A{[}i{]}{]}++; \newline {\bf{for}} i = 1 to k \newline   C{[}i{]} = C{[}i-1{]} + C{[}i{]}; \newline {\bf{for}} i = n downto 1 \{ \newline   B{[}C{[}A{[}i{]}{]}{]} = A{[}i{]}; \newline   C{[}A{[}i{]}{]}-{}-; \newline \}} \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}{RadixSort}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\emph{RadixSort(A, d)}} \newline {\bf{for}} i = 1 to d \newline    usa un ordinamento stabile per ordinare  \newline    l'array A sulla cifra i} \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}{Ricerca Binaria (tempo log n)}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{{\emph{RicercaBinaria(a, sx, dx, k)}} \newline   {\bf{if}} (sx \textgreater{} dx) return -1; \newline   cx = sx + dx / 2; \newline   {\bf{if}} (a{[}cx{]} == k) return cx; \newline   {\bf{if}} (a{[}cx{]} \textgreater{} k)  \newline     return RicercaBinaria(a, sx, cx-1, k); \newline   {\emph{else}} \newline     return RicercaBinaria(a, cx+1, dx, k); \newline  \newline {\emph{RicercaBinariaSx(a, sx, dx, k)}} \newline   {\bf{if}} (sx \textgreater{} dx) return -1; \newline   {\bf{if}} (sx == dx) \{ \newline     {\bf{if}} (a{[}sx{]} == k) return sx; \newline     {\bf{else}} return -1; \newline   \} \newline   cx = sx + dx / 2; \newline   {\bf{if}} (a{[}cx{]} ≥ k)  \newline     return RicercaBinaria(a, sx, cx, k); \newline   {\emph{else}} \newline     return RicercaBinaria(a, cx+1, dx, k);} \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}{Randomized-Select (QuickSelect)}}  \tn
\SetRowColor{LightBackground}
\mymulticolumn{1}{x{5.377cm}}{//Trova la i-esima occorrenza + piccola in //tempo atteso lineare \newline {\emph{Randomized-Select(A, p, r, i)}} \newline   {\bf{if}} (p == r) \newline     return A{[}p{]}; \newline   q = Randomized-Partition(A, p, r); //vedi  \newline                                      //quicksort \newline   k = q - p + 1; \newline   {\bf{if}} (i == k) // il valore del pivot è la  \newline               // soluzione \newline      {\bf{return}} A{[}q{]}; \newline   {\bf{else if}} (i \textless{} k) \newline     {\bf{return}} Randomized-Select(a, p, q-1, i) \newline   {\bf{else}} \newline     {\bf{return}} Randomized-Select(a, q+1, r, i-k)} \tn 
\hhline{>{\arrayrulecolor{DarkBackground}}-}
\end{tabularx}
\par\addvspace{1.3em}


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

\end{document}