krak / sorts
A collection of sorting algorithms implemented in php
Requires
- php: >=5.3.0
Requires (Dev)
- phpunit/phpunit: ~4.0
This package is not auto-updated.
Last update: 2024-11-13 07:22:31 UTC
README
A library for sort algorithms in php. Typically, you'd want to use php's c sorting functions, however, php lacks a stable sorting algorithms which can be useful in certain situations. In addition, this provides the opportunity for the community to implement many other custom sorts that could be useful in specific scenarios.
Installation
Installation via composer:
{
"repositories": [
{
"type": "vcs",
"url": "https://gitlab.bighead.net/bighead/krak-sorts.git"
}
],
"require": {
"krak/sorts": "~0.1"
}
}
Sorting Algorithms
Identity Sort
The identity sort does absolutely nothing. It just leaves the array untouched. This is useful for testing.
Insertion Sort
This implements the insertion sort algorithm. This is a stable sort. It's memory efficient and performs well on mostly sorted arrays and/or small datasets
Merge Sort
This implements the merge sort algorithm. Our implementation is a little more space efficient than most. However, it's space efficient relative to php's standards not C's.
Mock Sort
<?php
$sort = new Sorts\MockSort($data);
$sort->sort($other_data, Sorts\PHPCMP);
$other_data === $data; // true
This just assigns the data to be sorted to the data passed in. Useful for testing.
StableSort
$sort = new Sorts\StableSort(new Sorts\InsertionSort(), new Sorts\MergeSort(), 20);
This sort will take in two stable sorts (like insertion and merge) and will apply one or the other based off of the cutoff value. If the size of the array to sort is less than the cutoff, it will use the first sort, else it will use the latter sort. This works well when you use it on insertion and merge because insertion will typically outperform merge sort when under 20 or so elements.
Usage
There are two different API's for the sorting library.
Object Oriented Interface
Every sort is defined as class that implements the following interface:
<?php
namespace Krak\Sorts;
interface Sort
{
/**
* @param &$vals an array like object
* @param string|\Closure $cmp a comparison function
*/
public function sort(&$vals, $cmp);
}
You can create an instane of any of these to perform a sort.
new IdentitySort()
new InsertionSort()
new MergeSort()
new MockSort(mixed $data_to_assign)
new StableSort(Sort $few_sort, Sort $many_sort, int $cutoff_value)
Functional Interface
Or you can use the functional interface which is much cleaner to work with.
void sorts\stable(mixed &$data, $cmp = sorts\PHPCMP)
void sorts\insertion(mixed &$data, $cmp = sorts\PHPCMP)
void sorts\merge(mixed &$data, $cmp = sorts\PHPCMP)
There are three constants defined for sorting:
PHPCMP
this uses the<
and>
to get apply a comparison on arbitrary objects that support those operatorsSTRCMP
this is thestrcmp
functionINTCMP
this is just the difference between$a
and$b
You can view the source code for references on these comparison functions.
Comparison Functions
A valid comparison is any variable that can be invoked with these ()
. So if $cmp($a, $b)
doesn't throw an error, then it's a valid comparison. These comparisons are exactly compatible (the same as) the php comparison definitions