Insertion Sort algorithm and sorting dates in PHP

Insertion Sort algorithm and sorting dates in PHP

Created:03 May 2017 14:04:47 , in  Maths,  Web development

When it comes to dealing with dates and times in PHP, one look at the language related manual pages is enough to concolude, there is a daunting number of various functions for all sorts of purposes, from stuff for managing timestamp and timzones to routines for formatting and doing arithmetics on dates, available.

On top of that, since PHP 5.2, there is also DateTime class (with some related classes) available, that provides some quality tools for many of the above tasks. All wrapped in a nice and clean interface. Among other positive changes, DateTime class makes comparisons of times and dates a breeze.

Operators like less than (<) and greater than (>) can be employed for comparing objects of DateTime class now. In turn, sorting of dates ( notwithstanding format they come in ), which is the main theme of this article, can be done in a fairly straightforward and concise way.

Insertion Sort Algorithm

As far as sorting of lists in PHP is concerned, there is this nice little function called usort (I showed how to use it in Sorting objects by their property in PHP). If given a little attention, it can be adapted successfully to pretty much any kind of sorting task in hand. On the other hand, in particular if you feel a little bit more adventurous (or perhaps bored with usort by now), you might fancy writing your own sorting piece of code. Over recent decades many algorithms have been devised for the purpose. One that I've chosen for the needs of this article is called Insertion Sort algorithm.

Insertion Sort algorithm has quadratic running time for both average and worst input case. This makes it suboptimal for sorting large lists of items. At the same time, it is one of the fastest known algorithms for ordering small lists (up to 10 items) - coincidentally, this is exactly what I need here now.

The algorithm is fairly uncomplicated to understand and code. As for it's workings, Insertion Sort algorithm sorts list items by shifting them to the left of the list and in their final positions sequentially and one at a time. It uses two nested loops to achieve its goal.

It is the inner loop of the algorithm, that I found more interesting of the two. What it does is, shifts items that are larger than the item under consideration to the right of the item in the list. This operation was something that I scratched my head over how to code when trying to implement the algorithm for the first time.

In short, shifting items by one place to the right can be achieved by iterating over the list starting from its end and overwriting current item in it by preceding one. Below is a static class method that shifts all list items by one place to the right:


/* 
   Class: Shift - shift all items in array by one place to the right
   Author : Sylwester Wojnowski
   WWW : wojnowski.net.pl
   
   Parameters: 
     $a array - items (integers, strings, arrays, objects) 
   Return value: 
     array
*/
class Shift{
  public static function right($a){
    $c = count($a); 
    if($c < 1){ return $a; }
    $i = $c - 1;
    while($i > 0){
      $a[$i] = $a[$i - 1];
      $i--; 
    }
    $a[0] = NULL;
    return $a;
  }
}

Now let's call the method on list $a:

 
$a = array('a','b','c','d');
Shift::right($a);

=> (NULL,'a','b','c')

Often, you need not no NULL values in the list like this. Here is a small trick that makes it easy to deal with the issue and tidies up list keys at the same time. It uses unset and array_values PHP functions:


array_values(unset($a[0]));
=> (0 => 'a', 1 => 'b', 2 => 'c')

Going back to Insertion Sort algorithm, here is my implementation:


/* 
   Class: Sort - sort algorithms container
   Author : Sylwester Wojnowski
   WWW : wojnowski.net.pl
    
   Methods: 
     public static insertion($a, $compare)
       Description:
         sort items in $list using insertion sort algorithm  
       Parameters: 
         $a array - items (integers, strings, arrays, objects)
         [$compare] - optional anonymous function - function used for comparisons,
           accepts two arguments, compares them and returns bool true or false.         
       Return value
         array - sorted $a
*/

class Sort{
  public static function insertion($a,$compare = false){
    $compare = $compare && is_callable($compare) ? $compare : function($str1,$str2){
      return $str1 > $str2;
    };
    $i = 1;
    while( $i < count($a) ){
      $c = $a[$i];
      $j = $i;
      while($j > 0 && $compare($a[$j - 1],$c) ){ 
        $a[$j] = $a[$j - 1];
        $j--;
      }
      $a[$j] = $c;
      $i++;
    }
    return $a;
  }
}  

Sorting dates in PHP

Done with sorting code, we can take a closer look at some examples of sorting dates in PHP.

DateTime class makes creating dates in given format a trifle:


$dates = array(
  DateTime::createFromFormat('!d/m/Y','20/05/1943'),
  DateTime::createFromFormat('!d/m/Y','15/05/1917'),
  DateTime::createFromFormat('!d/m/Y','10/05/1914'),
  DateTime::createFromFormat('!d/m/Y','03/05/2028'),
);

DateTime class also handles DateTime object comparisons smoothly, which in turn makes sorting them easy:

    
# sort in ascending order
Sort::insertion($dates);

=> array(
        $dates[2], # '10/05/1914'
        $dates[1], # '15/05/1917'
        $dates[0], # '20/05/1943'
        $dates[3]  # '03/05/2028' 
      ); 

DateTime object can be constructed from a string containing date, time and timezone in one of supported formats:


#format: DateTime::W3C with the same timezone
$dates_and_times = array(
  new DateTime('1914-01-30T02:03:00+01:00'),
  new DateTime('1999-02-16T19:20:30+01:00'),
  new DateTime('1973-07-13T14:11:44+01:00'),
  new DateTime('2000-02-29T07:09:12+01:00')
);

Sorting such objects in ascending order can be done using a comparison function as below:

    
#sort the list in descending order using a comparison function
Sort::insertion($dates_and_times,function($a,$b){
  return $a < $b;
});

=>  array(
  $dates_and_times[3], # 2000-02-29T07:09:12+01:00
  $dates_and_times[1], # 1999-02-16T19:20:30+01:00
  $dates_and_times[2], # 1973-07-13T14:11:44+01:00
  $dates_and_times[0]  # 1914-01-30T02:03:00+01:00
)

Finally, sorting objects that have DateTime object as one of their property is a trifle too:


# container for objects
$periods = array();
        
# create some objects with DateTime as one of their properties
# and label them
$yesterday = new stdClass;
$yesterday -> label = 'yesterday';
$yesterday -> dtime = new DateTime('1 day ago');    

$today = new stdClass;
$today -> label = 'today';
$today -> dtime = new DateTime;  

$tomorrow = new stdClass;
$tomorrow -> label = 'tomorrow';
$tomorrow -> dtime = new DateTime('tomorrow');

$next_week = new stdClass;
$next_week -> label = 'next_week';
$next_week -> dtime = new DateTime('+7 days'); 

# store the objects in PHP array
$periods[] = $yesterday;
$periods[] = $today;
$periods[] = $tomorrow;
$periods[] = $next_week;

# shuffle the array
shuffle($periods);

# sort using Insertion Sort algorithm and a comparison function
$sorted = Sort::insertion($periods,function($a,$b){
  return $a -> dtime > $b -> dtime;
});

# check whether objects were sorted correctly in ascending order:
=> $sorted[0] -> label # 'yesterday'
$sorted[1] -> label # 'today'
$sorted[2] -> label # 'tomorrow'
$sorted[3] -> label # 'next_week'

Final thoughts

Concluding, DateTime PHP class is a considerable improvement over the bunch of functions available before its advent. I find it extremely nice designed and very easy to work with, not just for sorting, but also for other date and time related tasks. I hope the examples in this article have made the subject of sorting dates in PHP a little bit clearer for you and that you enjoyed the article.

This post was updated on 25 May 2017 16:20:21

Tags:  php ,  sort 


Author, Copyright and citation

Author

Sylwester Wojnowski

Author of the above article, Sylwester Wojnowski, is sWWW admin and owner.He enjoys doing Maths and studying algorithms, writing code in scripting and command languages, Thrash Metal music and playing electric guitar.

Copyrights

©Copyright, 2017 Sylwester Wojnowski. This article may not be reproduced or published as a whole or in parts without permission from the author. If you share it, please give author credit and do not remove embedded links.

Computer code, if present in the article, is excluded from the above and licensed under GPLv3.

Citation

Cite this article as:

Wojnowski, Sylwester. "Insertion Sort algorithm and sorting dates in PHP." From sWWW - Code For The Web . https://wojnowski.net.pl//main/index/insertion-sort-algorithm-and-sorting-dates-in-php