[1]

0 and 1 is enough but not practical enough

1. What is Sorting?

Sorting, in mathematical sense, is nothing but process of arranging items in a sequence ordered by some criterion. In many cases, items are real numbers and criterion asks us to rearrange them in non decreasing order. For example, given sequence of 10 real numbers

$\langle -\pi,\ \sqrt{2},\ 0.75,\ e^{\pi},\ \pi^{e},\ -3.14,\ \log_7 15,\ 2,\ 2^{\sqrt{2}},\ 4! \rangle$

(sorry if the numbers are confusing :] ) the correct sorted output of this sequence would be

$\langle -\pi,\ -3.14,\ 0.75,\ \log_7 15,\ \sqrt{2},\ 2,\ 2^{\sqrt{2}},\ \pi^{e},\ e^{\pi},\ 4! \rangle$

In order to sort given sequences, we must perform repeated comparisons between two chosen numbers. These are called comparison sorting.

There are indeed sorting techniques which do not accompany comparisons between numbers, but these algorithms require further restrictions on the input, such as set of integers or evenly distributed over a closed interval something like that. Since we are dealing with inputs with no restrictions on the real line, we must use comparison sorts.

2. Modeling the Process of Sorting

Now, any comparison sorting can be represented using the following diagram.

In detail, it consists of three parts

Input sequence
Output sequence (which is rearrangement in non decreasing order)
A network that actually performs comparisons and rearrangements.

The important part is the network $N$ . How do we specify the structure of $N$ ? It should contain all the information about comparisons we've done. For simplicity, let's look at the simplest network, which rearranges two numbers.

The simplest network produces minimum and maximum of two numbers. This can be modeled as a controller which sends smaller number to the top, and the other one to the bottom. So we define the fundamental network, called comparator , as follows.

For input sequence $\mathbf{a} = (a_1, a_2 ,..., a_n)$ and given integer $i, j \in \left\{ 1, 2, ..., n \right\}$ , comparator is a function $[i, j]$ such that

$[i, j] (\mathbf{a}, k) = \begin{cases} \min(a_{i}, a_{j}) & (k = i) \\ \max(a_{i}, a_{j}) & (k = j) \\ a_{k} & (\text{otherwise}) \end{cases}$

So a comparator is just a network of comparing two numbers $a_i, a_j$ , leaving others unchanged. - [2]

Since sorting is just simultaneous application of comparators, an arbitrary sorting network is modeled as follows.

[3]

where each vertical line segements represent comparators. For example, in the following sorting network you can see that simultaneous application of 5 comparators gives sorted output <1,2,3,4>.

[4]

3. All Possible Inputs?

Suppose we are given a sorting network $N$ , without any information about $N$ itself. That is, we do not know the structure of $N$ ; position of each comparators as well as algorithm behind it. And here comes the question.

How do we know the correctness of $N$ ?

Since we do not know the structure, what we can do is just comparing input - output relationships produced by $N$ .

The total number of orderings such that $n$ length sequence can have is $n!$ , so it is impossible to investigate every input-output relationships if $n$ gets large. Our real question is then,

Is there a smaller collection of input sequences enough to guarantee $N$ is correct ?

The answer is... YES! and this is called 0-1 sorting principle.

4. 0-1 Sorting principle

Now we state the 0-1 sorting principle. - [5]

0-1 Sorting Principle.
If a sorting network sorts every sequence of 0's and 1's (that is $\left\{ 0, 1 \right\}^n$ ) , then it sorts every other arbitrary sequence of length $n$ .

So only $2^{n}$ number of testing is enough. To prove this we need two ingredients. For any $n$ length sequence $\mathbf{a} = (a_1, a_2, ..., a_n)$ , we define

A non-decreasing function $f$ on domain $\left\{ a_1, a_2, ..., a_n \right\}$ and

Multi-valued function $F(\mathbf{a}) = (f(a_1), f(a_2), ..., f(a_n))$ .

Using definition of comparator, we have

$\begin{align*} [i,j](F(\mathbf{a}), i) &= [i, j]((f(a_1), ...,f(a_n)), i)\ (\because F\text{ definition})\\ &= \min(f(a_i), f(a_j))\ (\because \text{comparator definition}) \\ &= f(\min(a_i, a_j))\ (\because \text{non-decreasing }f) \\ &= f([i,j](\mathbf{a}, i))\ (\because \text{comparator definition}) \end{align*}$

Using function diagram,

$\mathbf{a} \xrightarrow{F} F(\mathbf{a}) \xrightarrow{[i,j]} [i,j](F(\mathbf{a}), i) \\\\ \iff \mathbf{a} \xrightarrow{[i,j]} [i,j](\mathbf{a}, i) \xrightarrow{f} f([i,j](\mathbf{a}, i))$

The meaning of this diagram is simple, that

$f \text{ mapping each component of }\mathbf{a} \rightarrow \text{comparator}$

is equal to

$\text{apply comparator} \rightarrow \text{map each component using map }f$

commutative . For an arbitrary sorting network $N$ (which is a composition of comparators) and a monotonic mapping $f$ we have therefore

$(N \circ F)(\mathbf{a}) = (F \circ N)(\mathbf{a})$

Hardest Part -[5]

Now let $N$ be a sorting network such that sorts all sequence of 0's and 1's correctly, but there exists an input - output relationship $\mathbf{a} \rightarrow \mathbf{b} = N(\mathbf{a})$ which the output is not sorted. Then there is an integer $k$ such that

$b_k > b_{k+1}$

The clever trick is to construct a following non-decreasing function $f$ such that

$f(x) = \begin{cases} 1 & (x \geq b_k) \\ 0 & (x < b_k) \end{cases}$

Surely $f(b_k) = 1, f(b_{k+1}) = 0$ . So

$F(\mathbf{b}) = (f(b_1), ... ,f(b_k) = 1, f(b_{k+1}) = 0,... f(b_n))$

is unsorted sequence. Using commutative relationship,

$F(\mathbf{b}) = F(N(\mathbf{a})) = N(F(\mathbf{a}))$

and since we assumed that $N$ sorts 0-1 sequence correctly, we get the contradiction because $F(\mathbf{a})$ is by definition, a 0-1 sequence.

5. Application ? - Hmm...

So in the case of unknown sorting network (or algorithm), $2^{n}$ number of all 0-1 sequences give the answer for correctness. But is $2^{n}$ small enough to be tested? Well,

It is definitely smaller than $n!$ for $n \geq 4$ , (in fact, $\lim_{n \rightarrow \infty} 2^{n}/n! = 0$ )
but $2^n$ itself is also exponential!

Try $n=30$ . If you want to test the correctness of algorithm that sorts length 30 sequence, you should investigate 1,073,741,824 in-out relationships, which exceeds 1 billion ...

Surely it is correct but not practical for real world applications... Also, the sad fact is that $2^n$ is actually tight bound for testing the correctness. Testing less than $2^n$ does not guarantee the correctness. (This is easy you can verify by yourself).

6. Conclusion

0-1 is enough but not practical enough.

7. Citations

[1] Image Source Link

[2] http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/sortieren.htm (definition citation)

[3] Image Source Link

[4] Image Source Link

[5] D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)

Sort:

Trending

[-]

steemstem (73) 6 years ago

This post has been voted on by the steemstem curation team and voting trail.

There is more to SteemSTEM than just writing posts, check here for some more tips on being a community member. You can also join our discord here to get to know the rest of the community!

$0.00

utopian-io (71) 6 years ago

Hi @mathsolver!

Your post was upvoted by utopian.io in cooperation with steemstem - supporting knowledge, innovation and technological advancement on the Steem Blockchain.

Contribute to Open Source with utopian.io

Learn how to contribute on our website and join the new open source economy.

Want to chat? Join the Utopian Community on Discord https://discord.gg/h52nFrV

[CS and Math #14] Binary to Arbitrary, 0-1 Sorting Principle