World's most popular travel blog for travel bloggers.

[Answers] Sorting array with two elements - in place and minimal number of comparisons, lower bound

, ,
Problem Detail:

Algorithm must be in place.
I would like to find lower bound for comparison algorithm. Algorithm will sort array with only two elements - without loss of generality let assume that there are only \$1s\$ and \$0s\$.

Decision tree give us lower bound \$\log(n+1)\$. It is to weak, because we know lower bound for findiing minimum, hence our algorithm must do at least \$n-1\$ comparisons. If it is lower bound ? I don't, but I think that it is \$n\$.

Why Do I think that lower bound is equal to \$n\$ ?

Let consider array \$|a|=n\$ such that \$a=a=...=a[n-1]=0\$ and \$a[n]=1\$.

It is needed at least \$n-2\$ comparisons to check that there is \$n-1\$ equal elements. And additional \$2\$ comparisons to check that \$1\$ is greater then rest of elements.

What is it real lower bound? What about my justification ?

Edit: We assume model computation as comparison \$\le\$.

\$n-1\$ comparisons are necessary and sufficient. To show that \$n-1\$ comparisons are necessary, we consider an adversary that always answers "EQUAL". Suppose that an algorithm makes at most \$n-2\$ comparisons. Construct a comparison graph whose vertices are the array elements and whose edges are the comparisons. Since the graph has at most \$n-2\$ edges, it is not connected. Let \$C_1,C_2\$ be two connected components. It is consistent that the value of all elements in \$C_1\$ is \$0\$ and that the value of all elements in \$C_2\$ is \$1\$. It is also consistent that all elements in \$C_1\$ are \$1\$ whereas all elements in \$C_2\$ are \$0\$. No monotone ordering of the array is consistent with both options, showing that the algorithm is incorrect.

To show that \$n-1\$ comparisons are sufficient, consider the algorithm that compares the first element to all other elements. There are three cases to consider:

1. The first element is equal to all other elements. In this case the array is already sorted.

2. The first element equals the elements in \$S\$ and is smaller than the elements in \$T\$. Thus the first element and the elements in \$S\$ have the value \$0\$ and the elements in \$T\$ have the value \$1\$, and we can sort the array accordingly.

3. The first element equals the elements in \$S\$ and is larger than the elements in \$T\$. This is symmetric to the previous case.