Insertion Sort algorithm and sorting dates in PHP

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

An implementation of Insertion Sort algorithm and a word on sorting dates in PHP.

Insertion Sort Algorithm

/* 
   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'

This post was updated on 06 Oct 2021 21:44:30

Tags:  php ,  sort