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); } } |

This site is a digital habitat of Sameer Borate, a freelance web developer working in PHP, MySQL and WordPress. I also provide web scraping services, website design and development and integration of various Open Source API's. Contact me at metapix[at]gmail.com for any new project requirements and price quotes.

## 2 Responses

1

Xr

January 9th, 2009 at 2:23 am

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.

As for your algorithm:

– You don’t make the difference between strictly increasing (resp. strictly decreasing) and simply non-decreasing (resp. non-increasing).

– AFAIK, it is only valid for arrays indexed by consecutive integers. A foreach would be better suited, keeping the previous element in a temporary variable (which could be more efficient than an array access as PHP does copy-on-write. This should be tested).

– I’d rather use multiple functions than a single parametrized one. This eliminates the need for a constant and limitates the needed logic.

Cheers.

2

Sameer Borate’s Blog: Finding if an array is ordered : Dragonfly Networks

January 9th, 2009 at 3:58 am

[...] the CodeDiesel.com blog today Sameer has posted a quick code snippet that lets you see if a numeric array is already ordered correctly (useful for something like unit [...]