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 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 [...]