对象数组的排序算法

I'm looking for a smartest solution.

I have a set of array which contains different locations and it has Starting point and ending point.

I want to sort that array so that "Start / From" Point should always start from the previous "To / End" point.

For example:

 Array
(
  [0] => planner\boarding\BoardingPasses Object
    (
        [from] => Gerona Airport
        [to] => Stockholm
    )

  [1] => planner\boarding\BoardingPasses Object
    (
        [from] => Madrid
        [to] => Barcelona
    )

  [2] => planner\boarding\BoardingPasses Object
    (
        [from] => Stockholm
        [to] => New York JFK
    )

  [3] => planner\boarding\BoardingPasses Object
    (
        [from] => Barcelona
        [to] => Gerona Airport
    )

 )

After sorting that array it will look like below.

 Array
 (
  [0] => planner\boarding\BoardingPasses Object
    (
        [from] => Madrid
        [to] => Barcelona
    )

  [1] => planner\boarding\BoardingPasses Object
    (
        [from] => Barcelona
        [to] => Gerona Airport
    )

  [2] => planner\boarding\BoardingPasses Object
    (
        [from] => Gerona Airport
        [to] => Stockholm
    )

  [3] => planner\boarding\BoardingPasses Object
    (
        [from] => Stockholm
        [to] => New York JFK
    )

)

And please have a look at my algorithm which is working perfect but i'm look for more fastest solution instead of using foreach loop inside for / instead of using array_map to get the starting point.

<?php
class SortPlan implements SortInterface
{
public static $cards;

public static $ArrangedArray = [];

public static $items = [];

public static function ArrangePlan($cards)
{
    // TODO: Implement SortPlan() method.

    self::$items = $cards;

    $from = array_map(function($e) { return $e->from; }, self::$items);
    $to = array_map(function($e) {return $e->to;}, self::$items);

    $getDiff = array_diff($from,$to);

    array_push(self::$ArrangedArray,$cards[key($getDiff)]);

    unset(self::$items[key($getDiff)]);

    for($i = 0; $i < count(self::$items); $i++)
    {
        foreach (self::$items as $p) {
            $des = end(self::$ArrangedArray);

            if ($des->to == $p->from) {
                array_push(self::$ArrangedArray, $p);
                unset($cards[key($p)]);
            }
        }
    }

    print_r(self::$ArrangedArray);


    return self::$ArrangedArray;
}
 }
 ?>

I don't know php , so I would be providing a general algorithm. The time complexity of my algorithm woudld be O(nlogn).

First make a different array of all objects named frmarray sorted on the basis of from attribute.

Then make a different array of all objects named toarray sorted on the basis of to attribute.

Till now time taken is O(nlogn) for the sorting.

Now find the object Obj such that Obj.To != any object's From, This can be done easily by considering one object at a time and then applying a binary search on array frmarray

Since binary search takes O(log n) time and we do it for every element , so time still remains O(nlogn).

The object Obj will be the last element of your sorted array.

The second last element can be easily found using a binary search on the array toarray and we will be searching for such object whose To = Obj.From.

Similarly third last element can be found by applying binary search.

Again this step is also O(nlogn). Therefore the total time complexity of my algorithm is O(nlogn).

Requirement: Sort a list of boarding passes with route information so that the 'to' and 'from' of adjacent routes are the same. i.e. An ordered list of destinations.

Demonstration: https://eval.in/662878

The approach I use is to:

  • Create partial lists of routes that match the rules
  • Merge the partial lists each time the opportunity occurs.

To do this we need fast lookup of adjacent routes.

We need:

  • A list of routes keyed by 'from'
  • A list of routes keyed by 'to'
  • Fast access to the 'partial list' the route is currently in.

Processing:

For each route:

  • Add it to the from/to lookup lists
  • Add it to the appropriate 'partial list'

This is where it get interesting:

We check to see if the adjacent routes are already in the list. there can be various possibilities:

Note: Adjacent Routes are really important and make the sorting 'not as quick' as we would like.

The issue is that there is no obvious way by comparing routes against each other, to decide, which is 'before' or 'after' the other. What we can compare is whether they are 'directly adjacent' to each other. i.e. 'From' of one matches the 'To' of the other. Or the other way around.

So, the idea is to build 'partial paths' and merge them when we can do so.

1) No match - start a new 'partial path'.

2) 'From' or 'To' match - add to the appropriate list.

3) 'From' and 'to' both match. This mean we can join two 'partial lists' together!

At the end of all the merging there will be one path (RoutePath) that all the routes will point to.

The Code:

BuildPath

The class the processes individual routes and decide which RoutePath to process:

class BuildPath {

   /**
    *
    * Generate partially sorted lists of boarding passes
    * when adding one at a time to an output list. 
    * 
    * Method: 
    *   o Each route will get appended to the approriate partial list as it processed.
    * 
    *   o When the route will join two partial lists then that are merged
    * 
    * Needed:
    *   o Fast lookup of adjacent routes to find out which list to appended to.
    * 
    *   o Fast lookup of the partial list
    */ 

    /**
    * Initial source array of boarding passes that hold routes
    * 
    * @var array  
    */
    private $boardingPasses = null;


    /**
    * stdClass Route object indexed by 'From' keys
    * 
    * @var array 
    */

    private $keyFrom = array();

    /**
    * stdClass Route object indexed by 'To' keys
    * 
    * @var array 
    */
    private $keyTo  = array();


    /**
    * @return void
    */    
    public function __construct(array $boardingPasses) 
    {
        $this->boardingPasses = $boardingPasses;

        foreach ($boardingPasses as  $key => $pass) {
            $route = current($pass);
            $route->passId = $key; // so I can get as the full data later                    

            $this->addRoute($route);
        }
    }


    public function addRoute($route)
    {
        /*
         *  Can new route be joined to an existing route? 
         */


         // Will this route join two partial lists    
         if (    $this->canAddFrom($route->from)
              && $this->canAddTo($route->to) ) { // join two partial lists together

            $this->keyFrom[$route->from] = $route;
            $this->keyTo[$route->to] = $route;

             // add to one list first - it doesn't matter which
            $this->getAddFromPath($route->from)->add($route);  

            // merge the two partial paths together
            $this->getAddFromPath($route->from)->merge($this->getAddToPath($route->to));


         } elseif ($this->canAddFrom($route->from)) { // add to this ;ist

            $this->keyFrom[$route->from] = $route;
            $this->keyTo[$route->to] = $route;

            $this->getAddFromPath($route->from)->add($route);  

         } elseif ($this->canAddTo($route->to)) { // add to existing path

            $this->keyFrom[$route->from] = $route;
            $this->keyTo[$route->to] = $route;

            $this->getAddToPath($route->to)->add($route);  

         } else { // start a new path

            $this->keyFrom[$route->from] = $route;
            $this->keyTo[$route->to] = $route;

            $path = new \RoutePath(); 

            $route->path = $path; // the path may change later  
            $path->add($route);

//            $this->routes[] = $route;
            return $route;
         }
    }  

    /**
    * The original array in path order
    * 
    * @return array
    */
    public function getSortedRoutes()
    {
        $out = array();
        foreach($this->getPath()->getRoutes() as $route) {
           unset($route->path);
           $out[] = $this->boardingPasses[$route->passId];         
        }

        return $out;
    }

    /*
     *  All routes should point to the same path
     *
     *  Whatever happens:  each route will point to the path it is in :)
     *             
     *  So, a scan of all the routes for different paths will find all the partial paths :)     
     */               
    public function getPath()
    {
        reset($this->keyFrom);
        return current($this->keyFrom)->path;
    }

    // helpers
    public function canAddFrom($from)
    {
        return isset($this->keyTo[$from]); 
    }

    public function canAddTo($to)
    {
        return isset($this->keyFrom[$to]); 
    }       

    public function getAddFromPath($from)
    {
        return $this->keyTo[$from]->path; 
    }

    public function getAddToPath($to)
    {
        return $this->keyFrom[$to]->path; 
    }       
}

RoutePath

The class that holds the 'partial list' of adjacent routes:

class RoutePath {

    private $path = array();

    /**
    * Add the route to the appropriate end of the list
    * 
    * @param stdClass $route
    * 
    * @return void
    */    
    public function add($route)
    {
        $route->path = $this; // ensure it pounts to correct path

        if (empty($this->path)) {

            array_push($this->path, $route);

        } elseif  ($this->canAddFrom($route->from)) {

            array_push($this->path, $route);

        } elseif ($this->canAddTo($route->to)) {

            array_unshift($this->path, $route);

        } else {

            throw new \Exception('Cannot add node: From: '. $route->from . ', To: '. $route->to, 500);

        }
    }

    /**
    * Merge two partial lists together
    * 
    * o Decide which list to append to 
    *
    * o Update all the routes to point to rthe merged path 
    * 
    * @param RoutePath $path
    * 
    * @return void
    */
    public function merge(\RoutePath $path)
    {
        if ($this->canAddFrom($path->getFrom())) {

            $path->updateRoutePath($this);             
            $this->path = array_merge($this->path, $path->getpath());

        } elseif ($this->canAddTo($path->getTo())) {

            $path->merge($this);

        } else {

            throw new \Exception('Cannot merge paths: '  
                                 . ' (this): From: '. $this->getFrom() .', To: '. $this->getTo()
                                 . ' (path): From: '. $path->getFrom() .', To: '. $path->getTo()
                                 , 500);

        }        
    }

    /**
    * Make all the routes point to the correct list
    * 
    * @param RoutePath $path
    * 
    * @return void
    */
    public function updateRoutePath(\RoutePath $path)
    {
        foreach ($this->path as $route) {
            $route->path = $path;
        }    
    }

    // always check the first entry in the list
    public function canAddTo($to)
    {
        return $this->getFrom() === $to; 
    }       

    // alway check last entry in the list
    public function canAddFrom($from)
    {
        return $this->getTo() === $from; 
    }

    public function getFrom()
    {
        reset($this->path);
        return current($this->path)->from;
    }           

    public function getTo()
    {
        return end($this->path)->to;
    }           

    public function getpath()
    {
        return $this->path;
    }

    public function getRoutes()
    {
        return $this->path;
    }
}

Run it and show output:

$path = new BuildPath($passes);
// print output...

echo '<pre>Sorted...', PHP_EOL;
    print_r($path->getSortedRoutes());
echo '</pre>';    

Sample Output:

Sorted...
Array
(
    [0] => Array
        (
            [planner\boarding\BoardingPasses] => stdClass Object
                (
                    [from] => Madrid
                    [to] => Barcelona
                    [passId] => 1
                )
        )
    [1] => Array
        (
            [planner\boarding\BoardingPasses] => stdClass Object
                (
                    [from] => Barcelona
                    [to] => Gerona Airport
                    [passId] => 3
                )
        )
    [2] => Array
        (
            [planner\boarding\BoardingPasses] => stdClass Object
                (
                    [from] => Gerona Airport
                    [to] => Stockholm
                    [passId] => 0
                )
        )
    [3] => Array
        (
            [planner\boarding\BoardingPasses] => stdClass Object
                (
                    [from] => Stockholm
                    [to] => New York JFK
                    [passId] => 2
                )
        )
)

Test Data:

$passes = Array(
  0 =>   array('planner\boarding\BoardingPasses' => 
            (object) array('from' => 'Gerona Airport', 'to' => 'Stockholm')
         ),   

  1 => array('planner\boarding\BoardingPasses' => 
           (object) array('from' => 'Madrid', 'to' => 'Barcelona')
       ),

  2 => array('planner\boarding\BoardingPasses' =>
           (object) array('from' => 'Stockholm', 'to' => 'New York JFK')
       ),    

  3 => array('planner\boarding\BoardingPasses' =>
           (object) array('from' => 'Barcelona', 'to' => 'Gerona Airport')
       ),
 );