\problemdata
{S00 ps4.5}
{computational processes}
{NSort}

\begin{problem}
%[[[New problem]]]
The nondeterministic algorithm $NSort$ starts with a sequence $S$ of $n$
distinct integers, initially in any order.
$NSort$ describes how to sort the sequence, in place, into increasing order.
What it does is to choose, arbitrarily, any pair of adjacent numbers
that appear in the wrong order, that is, that form an ``inversion'',
as in Problem \ref{puzzleProblem}.
It corrects this inversion by interchanging these two numbers, leaving
the rest of the sequence $S$ unchanged.
$NSort$ repeats this step until no further steps can be applied.

\begin{problemparts}
\problempart
Model this as a state machine.

\solution{
The state is represented by a string:
\begin{center}
$Q = \{ x_1 x_2 x_3 \cdots x_n $ such that $x_i \in \integers$ and the 
$x_i$ are all 
distinct $\}$
\end{center}

The possible start states are any random string so:
\[ Q_0 = Q \]
In other words, any state can be a starting state.

The set of transitions 
$\delta \subseteq Q \times Q$ is:
\begin{center}
$\{(q_1, q_2)\}$ such that $q_2$ is exactly the
same as $q_1$ except two adjacent positions are swapped. 
In $q_1$ these positions were
out of order (the greater one had lower index) but in $q_2$ the order is
correct.
\end{center}
\end{solution}
}

\problempart
Prove that $NSort$ eventually terminates with $S$ completely sorted.

\solution{
Let us define three quantities:
\begin{description}
\item[~$N_{total}$:] Total number of out of order pairs in the string 
\item[~~~$N_{adj}$:] Number of out of order {\em adjacent} pairs in the string 
\item[$N_{nonadj}$:] Number of out of order {\em non-adjacent} pairs in the string
\end{description}
Notice that since adjacent or non-adjacent is an exhaustive set of
possibilities for a pair, for any state:
\[N_{total} = N_{adj} + N_{nonadj}\] 
Also, notice that all three quantities are by definition in $\naturals$.
The following lemma is very helpful: 

\begin{lemma}
$N_{total} = 0 \Longleftrightarrow N_{adj} = 0$
\end{lemma}

\begin{proof}

$\Longrightarrow$. For contradiction suppose $N_{adj} \neq 0$ but $N_{total}
= 0$. Then $N_{nonadj} = - N_{adj}$. Since both $N_{adj}$ and $N_{nonadj}$
are nonnegative, they must both be 0. Contradiction.

$\Longleftarrow$. For contradiction, suppose $N_{adj} = 0$ but $N_{total}
\neq 0$. Then there exists $i, j \leq n$ such that $i < j$ and $x_i >
x_j$. Let us pick $i$ and $j$ to minimize their difference. In other words,
out of the pairs that are inverted, let's pick the pair that is closest.
Since $N_{adj} =
0$, these two entries cannot be adjacent so $j > i + 1$. 
So there is some entry, $x_{i+1}$ adjacent to $x_i$. Since
no adjacent pairs are out of order,  $x_i < x_{i+1}$. Also, since $x_i$ and
$x_j$ were the closest inverted pair, $x_{i+1}$ and $x_j$ cannot be
inverted. Therefore, $x_{i+1} < x_j$. This means that $x_i < x_{i+1} < x_j$
which is a contradiction.
\end{proof}


First, we can use this lemma to prove {\bf correctness}. That is, we need to
show that when the algorithm terminates, the string is completely sorted. We
know that our algorithm terminates when there are no adjacent inverted
pairs. Applying our lemma, this means that there are no inverted pairs at
all. A string with no inverted pairs is a sorted string. QED.

Second, we can use this lemma to prove {\bf termination}. Consider the
following facts:
\begin{enumerate}
\item

$N_{total}$ decrease with every transition. {\em (Note that $N_{adj}$ does NOT
decrease with every transition.)}
We can show this by examining our transition. 
The exchange itself decreases the number of inversions by one. However,
it may produce ``new'' adjacent inversions. But the key fact is that it can form
no {\em new} inversions. The only thing that can happen is that a previously
non-adjacent inversion can become adjacent. This is because the only items
that move are the ones being exchanged, and they are being ordered
correctly. As far as all the other items in the string are concerned, the
two items are in the same place. Thus, the total number of inversions
decreases by 1 at every transition.

\item

$N_{total}$ will eventually reach 0 in any live execution. This is because
$N_{total}$ is a nonnegative integer by definition. By the well ordering
principle, and the fact that it is decreasing at every transition, it will
eventually reach 0. 

\item

When $N_{total}$ reaches 0, the algorithm will stop. We show this by
applying our lemma. If $N_{total} = 0$ then $N_{adj} = 0$ so the algorithm
terminates by definition.
\end{enumerate}

Thus the algorithm will terminate. Also, at termination, 
$N_{total} = N_{adj} = 0$ so the string is sorted.
\end{solution}
}

\problempart
Give a good upper bound on the number of steps that $NSort$ can take
until it terminates. 

\solution{

Two possibilities are:
\begin{description}
\item[Loose upper bound: ]

Every item can be exchanged with every other item at most once. So for all
$n$ items, there are $n-1$ other items that they could be exchanged with. So
$n(n-1) = O(n^2)$ is an upper bound.

\item[Tight upper bound: ]

$N_{total}$ is definitely an upper bound since it decreases by 1 at every
step until it reaches 0. Also, $N_{total}$ is upper bounded by the total
number of combinations of elements of the string. This is $\left(
\begin{array}{c} n \\ 2 \end{array} \right)$ or $\frac{n(n-1)}{2}$. Notice
that this is the same as the loose bound except it recognizes that every
pair in the loose bound is actually being counted twice.

\end{description}

}

\problempart
For the special case where n = 4, give an example execution that takes
the maximum number of steps to terminate. 

\solution{
\begin{solution}
The following execution takes $\frac{n(n-1)}{2} = \frac{4*3}{2} = 6$ steps:
\[
\begin{array}{rccccccc}
Start  \longrightarrow & 4 & 3 & 2 & 1 \\
Step~1 \longrightarrow & 3 & 4 & 2 & 1 \\
Step~2 \longrightarrow & 3 & 2 & 4 & 1 \\
Step~3 \longrightarrow & 3 & 2 & 1 & 4 \\
Step~4 \longrightarrow & 2 & 3 & 1 & 4 \\
Step~5 \longrightarrow & 2 & 1 & 3 & 4 \\
Step~6 \longrightarrow & 1 & 2 & 3 & 4 
\end{array}
\]
}

\end{problemparts}
\end{problem}

