Finding if an array is ordered


Posted in: algorithms | Save to del.icio.us | Twit This! 8 Jan 2009

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

Share this post

Share on Facebook
Share on Twitter
Share on StumbleUpon
Share on Delicious
Share on Digg
Share on Technorati
Share on Reddit
Feeds RSS Subscribe to site Feed

Other related posts

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

Comment Form

About this blog

This site is a digital habitat of Sameer, a freelance web developer working from Pune.More

On Twitter

Posting tweet...


  • Users Online

    • 3 Users Online
    • 1 Guest, 2 Bots
  • Categories