Sorting Date Strings in PHP

30 06 2010

Flickr: Irene PerinoFlickr: by Oblong

Here’s yet another technical exercise and you have ten (10) minutes precisely to complete it.

Consider the following array of date strings:

$arrDates = array(
"12/25/2009","01/10/2008","02/12/2000","03/17/1948",
"03/06/1948","11/25/1972","10/23/2009","01/14/2008",
"02/22/2000","03/27/1948","03/16/1948","11/24/1972",
"11/13/2009","11/10/2008","12/12/2000","05/17/1948",
"05/06/1948","10/25/1972","09/23/2009","02/14/2008",
"03/22/2000","04/27/1948","04/16/1948","08/24/1972"
);

Indicate two different ways to go about sorting these “mm/dd/yyyy” formatted strings in ascending order. One way should involve using a PHP built-in function and the other should use an algorithm. You may think that this is yet another one of those technical questions that I’ve received from a prospective employer. Actually, this is my own offering!

How shall we approach this exercise, i.e. do the built-in first or choose an algorithm and implement it in PHP? Working with the algorithm may be easier and instructive, serving as a guide for which PHP function to pick later.

 

Bubbling for Answers

The easiest sorting algorithm, the bubble sort, is one that many a computer science student will be already acquainted with, so let’s use it. Yes, I know the bubble sort is routinely derided for being so slow as to render it impractical for large datasets. But, we’re going to implement it on a very small dataset — 24 items precisely. Incidentally, I got this notion from an online article which suggests using the bubble sort for sorting dates.

So, let’s look at how we might implement the algorithm with PHP:

/**
   * swapValue()
   * @param array $array
   * @param int $dex
   * swap two array values 
**/
function swapValues( $array, $dex ) {
	list($array[$dex],$array[$dex + 1]) = array($array[$dex + 1], $array[$dex]);
	return $array;
}

/**
   * bubbleSort()
   * @param array $array
   * performs bubble sort using traditional bubble sort
**/
function bubbleSort( $array )
{
    $size = count($array) - 1; // zero-based array 'indexing'
    $swapped = 0;
    do
    {
        $swapped = 0;

        for ($x = 0; $x < $size; $x++)
        {
               if ( strtotime($array[ $x ]) > 
                              strtotime($array[ $x + 1]))  
              {
                $array = swapValues($array,$x);
                $swapped = 1;
              }
        }
    } while ($swapped);
	return $array;
}

The bubble sort code above could be optimized if we could get rid of the tracking variable $swapped. Here’s what we could use instead:

/**
   * swapValue2()
   * @param array $array
   * @param int $dex
   *  @param int $dex2
   * swap two array values 
**/
function swapValues2( $array, $dex, $dex2 ) {
	list($array[$dex],$array[$dex2]) = array($array[$dex2], $array[$dex]);
	return $array;
}

/**
   * bubbleSort()
   * @param array $array
   * performs bubble sort using optimized implementation
**/

function bubbleSort( $array)
{
	for( $out=0, $size = count($array); 
                                   $out < $size - 1 ; 
                                            $out++ )
       {
 		for( $in = $out + 1; 
                      $in < $size; 
                      $in++ ) 
               {
		      if (strtotime($array[ $out ]) > 
                               strtotime($array[ $in ])) 
                     {
			    $array = swapValues2($array, $out, $in);
                      }
   		}
  	}
	return $array;	
}

Regardless which bubbleSort() we select, we could use it as follows:

 
var_dump(bubbleSort( $arrDates ));

See live code here and here.

Note that to do the sorting of the date strings, they needed to be converted at least temporarily into a date/time format that results in numerical data. In this case each date string was converted into a unix timestamp using strtotime(). There are other conversions that would have worked too, such as converting the strings into Julian days using the gregoriantojd().

 

Employing Built-In Functions

Now, that we have an idea of what it takes to sort date strings in PHP without using a built-in, let’s see if we can find an appropriate built-in to use. Ideally, sort() would have been nice to use since it is based on the QuickSort algorithm and should perform just as fast or faster than either of our bubble sort implementations. But, sort() would only work if we went to the trouble of converting the date strings to meaningful numerical date values first and then performing the sort on those values and finally converting these back to date strings. Whew! Surely there is a less labor intensive option.

If you investigate PHP’s sort(), you’ll note that there are variations of it also based on the QuickSort algorithm presumably. There is also a listing of the sorting functions from which to choose. My ultimate choice was to use usort(), so as to be able to do the necessary manipulation with strtotime() and then be able to sort the dates.

Here’s the result of that effort:

/**
   * cmp()
   * @param int $a
   * @param int $b
   * date comparison callback 
**/
function cmp($a, $b) {
    if ($a == $b) return 0;
	
	return (strtotime($a) < strtotime($b))? -1 : 1;
}
usort($arrDates, "cmp");
var_dump($arrDates);

See live code here

If the data were slightly different, you might need a solution that involves uasort() which maintains the key associations. Consider the following dataset:

$arrDates = array(
"Tom"      =>  "12/25/2009",
"Jill"     => "01/10/2008",
"Fred"     => "02/12/2000",
"Anne"     => "03/17/1948",
"Steve"    => "03/06/1948",
"Sue"      => "11/25/1972",
"Jack"     => "10/23/2009",
"John"     => "01/14/2008",
"Bethany"  => "02/22/2000",
"George"   => "03/27/1948",
"Nancy"    => "03/16/1948",
"James"    => "11/24/1972",
"Henry"    => "11/13/2009",
"Harriet"  => "11/10/2008",
"Karen"    => "12/12/2000",
"Ken"      => "05/17/1948",
"Clark"    => "05/06/1948",
"Sheila"   => "9/23/2009",
); 

If you wished to discover the eldest in the group, then one would need to maintain key associations for the sorted data. One need only tweak the preceding by replacing usort() with uasort(), as follows:

function cmp($a, $b) {
    if ($a == $b) return 0;
     
    return (strtotime($a) < strtotime($b))? -1 : 1;
}
uasort($arrDates, "cmp");
print_r($arrDates);

See live code.

The solutions above are what I suggest for completing this technical exercise. Maybe you have a different approach — if so, please share your thoughts.

 

Update: April 1, 2016

While today may be April Fools’, the new spaceship operator in PHP 7 is anything but a joke. Its use benefits developers so they may write more comprehensible code, expending less effort as the following example depicts:

<?php
$arrDates = array(
"12/25/2009","01/10/2008","02/12/2000","03/17/1948",
"03/06/1948","11/25/1972","10/23/2009","01/14/2008",
"02/22/2000","03/27/1948","03/16/1948","11/24/1972",
"11/13/2009","11/10/2008","12/12/2000","05/17/1948",
"05/06/1948","10/25/1972","09/23/2009","02/14/2008",
"03/22/2000","04/27/1948","04/16/1948","08/24/1972"
);
/**
   * better_cmp()
   * @param int $a
   * @param int $b
   * date comparison callback 
**/
function better_cmp($a,$b){
    list($a,$b) = [strtotime($a), strtotime($b)];
    return ($a <=> $b); 
}
usort($arrDates,"better_cmp");
print_r($arrDates);

See live code.

This work is licensed under a Creative Commons License
.

Advertisements

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: