Collections and Sorting - Concrete Classes (
Page 4 of 4 )
Now it is time to create an actual concrete implementation of the abstract Collection class and the ISortable interface. We will use a class called People for our collection. It will contain objects of the type Person. Really, it can contain any object implementing ISortable, but in our example we will only use the class Person. For now, the Person class is going to be just a glorified container for a single string, $name.
class Person implements ISortable
{
private $name;
public function GetName() { return $name; }
public function SetName($name) { $this->name = $name; }
public function GetSortKey()
{
return $this->name;
}
public function __construct($name)
{
$this->name = $name;
}
}
Next we need to implement the People collection and its Sort() method. As I mentioned earlier in the article, there are quite a lot of ways to sort. For this example I will use the "fundamental" sort algorithm - the Bubble Sort. I should also point out that it is the slowest sort and should never be used on large data sets or where performance is a critical concern.
class People extends Collection
{
public function Sort()
{
for ($i = $this->data->count() - 1; $i >= 0; $i--)
{
$flipped = false;
for ($j = 0; $j < $i; $j++)
{
if (strcmp($this->data[$j]->GetSortKey(),
$this->data[$j + 1]->GetSortKey()) > 0)
{
$tmp = $this->data[$j];
$this->data->offsetSet($j,
$this->data[$j + 1]);
$this->data->offsetSet($j + 1, $tmp);
$flipped = true;
}
}
if (!$flipped)
return;
}
}
}
The Bubble Sort is by far the most obvious and intuitive sort algorithm, performing in-place swaps in a linear fashion. Notice that it will return early if any pass does not cause a swap - which means in an example like this one, it's just fine. Even if it did not return early, we will be working with so few elements that it simply does not matter. Consider the following example:
$people = new People();
$people->Append(new Person('Jamie'));
$people->Append(new Person('David'));
$people->Append(new Person('Natalie'));
$people->Append(new Person('Johnny'));
print '<pre>';
print_r($people);
$people->Sort();
print_r($people);
print '</pre>';
You should see this in your browser after running the script:
People Object
(
[data:protected] => ArrayObject Object
(
[0] => Person Object
(
[name:private] => Jamie
)
[1] => Person Object
(
[name:private] => David
)
[2] => Person Object
(
[name:private] => Natalie
)
[3] => Person Object
(
[name:private] => Johnny
)
)
)
People Object
(
[data:protected] => ArrayObject Object
(
[0] => Person Object
(
[name:private] => David
)
[1] => Person Object
(
[name:private] => Jamie
)
[2] => Person Object
(
[name:private] => Johnny
)
[3] => Person Object
(
[name:private] => Natalie
)
)
)
Conclusion
There it is, a minimal implementation of collections with sorting. We have defined two interfaces and an abstract collection class and created a uniform way to sort within our collection. By sacrificing the ability to use an indexer on our collection, we were able to encapsulate the sort functionality within the collection class itself, sparing ourselves the trouble of creating even more classes.
Having now implemented the worst possible sort algorithm and left an obvious re-factoring or two, the stage is set for the next installment of this article. In the next part we are going to actually implement a number of sort algorithms and benchmark them with a much larger data set. If you need to learn the fundamental sort algorithms (and all programmers do), be sure you check it out!
