\documentclass[11pt]{article}
\usepackage{url}
\usepackage{epsf}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{setspace}
\doublespacing

\addtolength{\textwidth}{1.2in} \addtolength{\evensidemargin}{-0.9in}
\addtolength{\oddsidemargin}{-0.9in}
\addtolength{\textheight}{1.4in} \addtolength{\topmargin}{-0.7in}

\newcommand{\ABox}{
\raisebox{3pt}{\framebox[6pt]{\rule{6pt}{0pt}}}
}
\newenvironment{proof}{{\bf Proof:}}{\hfill\ABox}

\newcommand{\true}{{\tt TRUE}}

\newtheorem{theorem}{{\bf Theorem}}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{openquestion}[theorem]{Open question}

\newcommand{\bigred}{{\tt RED}}
\newcommand{\e}{\varepsilon}
\newcommand{\R}{\mathcal R}
\newcommand{\K}{\mathcal K}
\newcommand{\MST}{\tt MST}
\newcommand{\MIS}{\tt MIS}
\newcommand{\ssp}{{\tt sp}}

\begin{document}

\centerline{\Large\bf Comments on the timing results}

\noindent

When {\tt bubbleSort} and {\tt improvedBubbleSort} were run on
almost unsorted arrays, the running time grew at more or less the same rate,
though {\tt improvedBubbleSort} was a little slower due to the
overhead of checking whether a swap was performed in a phase.
Note that {\tt improvedBubbleSort} does not save at all in the
number of phases it needs to run.
The two plot corresponding to running the functions on almost
unsorted arrays are shown in the Figure 1.
It is clear that the rate of growth of the functions is faster than linear
and may be qudratic.

\begin{figure}[htpb]
\centerline{\includegraphics[width =
0.8\linewidth]{plot2.ps}}
\caption{Shows the running times of {\tt bubbleSort} and 
{\tt improvedBubbleSort}, when these were run on almost
unsorted arrays.}
\end{figure}

When {\tt bubbleSort} and {\tt improvedBubbleSort} were run on
almost sorted arrays, we get plots that are similar to those
above.
These are shown in Figure 2.
In these plots the running times of the two functions are very close
together, sometimes {\tt bubbleSort} is better and
sometimes {\tt improvedBubbleSort} better.
This may surprising initially, but on examining 
{\tt improvedBubbleSort} carefully, we see that even if the input array
was obtained by taking a sequence that is completely in order and
then swapping the first and the last elements,
{\tt improvedBubbleSort} still requires $n-1$ phases.
In other words, if we start with $n-1, 1, 2, 3, \ldots, n-2, 0$ and
run {\tt improvedBubbleSort}, 0 gets to its correct position in the
very first phase. However, in each phase, $n-1$ moves just one step
to the right, towards its correct position.

\begin{figure}[htpb]
\centerline{\includegraphics[width =
0.8\linewidth]{plot1.ps}}
\caption{Shows the running times of {\tt bubbleSort} and 
{\tt improvedBubbleSort}, when these were run on almost
sorted arrays.}
\end{figure}

A different kind of small perturbation does reveal situations
in which {\tt improvedBubbleSort} is much faster than {\tt bubbleSort}.
Let us start with a sorted sequence and make a bunch of swaps but ensure
that all the swapped elements are in the first 10 slots of the array.
Thus the first 10 elements are disorderly, but the remaining $n-10$
elements in the array are all in their correct positions.
For this version of an almost sorted array, {\tt improvedBubbleSort}
does outperform {\tt bubbleSort} dramatically.
In general, {\tt improvedBubbleSort} performs very well compared
to {\tt bubbleSort} on arrays in
which each element is not too far away from its correct position.
See Figure 3, for plots obtained by running the sorting algorithms
on almost sorted arrays obtained using this different kind of
perturbation.
{\tt improvedBubbleSort} is so fast that its plot is along the
$x$-axis is not too clearly visible.


\begin{figure}[htpb]
\centerline{\includegraphics[width =
0.8\linewidth]{plot3.ps}}
\caption{Shows the running times of {\tt bubbleSort} and {\tt improvedBubbleSort}, when these were run on almost sorted arrays, in which no element is
too far away from its correct place.}
\end{figure}

\end{document}
