# Finding if an array is ordered

I recently wrote a quick code to find if a numeric array is ordered i.e sorted in a ascending or descending order. I needed it to check a sort algorithm I had written. The problem is that the following code has a worst-case running time of O(N). Can we make the running time logarithmic.

```/* orderedArray.php */

define("ORDER_ASC", 1);
define("ORDER_DSC", 0);

function is_array_ordered(\$array, \$sort_order)
{
\$i=0;
\$total_elements = count(\$array);

if(\$sort_order == ORDER_ASC)
{
//Check for ascending order
while(\$total_elements > 1)
{
if(\$array[\$i] < \$array[\$i+1])
{
\$i++;
\$total_elements--;
}
else
{
return false;
}
}
}
elseif(\$sort_order == ORDER_DSC)
{
//Check for descending order
while(\$total_elements > 1)
{
if(\$array[\$i] > \$array[\$i+1])
{
\$i++;
\$total_elements--;
}
else
{
return false;
}
}
}

return true;
}
```

The unit test for the same is given below.

```include 'PHPUnit/Framework.php';
include 'orderedArray.php';

class ArrayTest extends PHPUnit_Framework_TestCase
{
public function testArrayOrder()
{
// Ascending
\$test_array = array(0,1,2,3,4,6,7,8,9,10);
\$this->assertEquals(is_array_ordered(\$test_array, ORDER_ASC), true);

\$test_array = array(10,9,8,7,6,5,4,3,2,1,0);
\$this->assertEquals(is_array_ordered(\$test_array, ORDER_ASC), false);

\$test_array = array(0,1,2,3,4,6,7,8,9,10,1);
\$this->assertEquals(is_array_ordered(\$test_array, ORDER_ASC), false);

\$test_array = array(1,0,1,2,3,4,6,7,8,9,10);
\$this->assertEquals(is_array_ordered(\$test_array, ORDER_ASC), false);

// Descending
\$test_array = array(10,9,8,7,6,5,4,3,2,1,0);
\$this->assertEquals(is_array_ordered(\$test_array, ORDER_DSC), true);

\$test_array = array(0,1,2,3,4,6,7,8,9,10);
\$this->assertEquals(is_array_ordered(\$test_array, ORDER_DSC), false);

\$test_array = array(10,9,8,7,6,5,4,3,2,1,0,1);
\$this->assertEquals(is_array_ordered(\$test_array, ORDER_DSC), false);

\$test_array = array(1,10,9,8,7,6,5,4,3,2,1,0);
\$this->assertEquals(is_array_ordered(\$test_array, ORDER_DSC), false);

}
}
```

## 2 thoughts to “Finding if an array is ordered”

1. Xr says:

You can’t make the time O(log N) since you have to check every element, which is precisely O(N).

Usually, a logarithmic time means O(N log N), which is worse than O(N) but much better than O(N²). For example, the best sorting algorithms have O(N log N) times (Quicksort with possible degeneration, Heap Sort), while naive ones have O(N²) times.