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 operators
STRCMP this is the strcmp function
INTCMP 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

krak / sorts

Maintainers

Details