the-jj/spl-collections-sort

Helper library for sorting Spl data structures

1.0.3 2017-10-16 10:45 UTC

Requires

• php: >=5.6

Requires (Dev)

• phpunit/phpunit: ^5.7

MIT

• Juraj Juričić

README

Several methods for sorting SPL datastructures. Currently only SplFixedArray objects are supported. Should be fast with big arrays as well.

Basic usage

All sorting algorithms accept SplFixedArray object as first argument and optional comparison callback function as second argument. Sorting is done in place.

• Insertion sort
• Quicksort
• Mergesort
• Fallback to standard PHP array sort()

Insertion sort

$splFixedArray = SplFixedArray::fromArray([5, 3, 8, 6, 0, 4]);

SplFixedArraySort::insertionSort($splFixedArray);

var_dump($splFixedArray->toArray()); // [0, 3, 4, 5, 6, 8]

Custom comparison function

$splFixedArray = SplFixedArray::fromArray([5, 3, 8, 6, 0, 4]);

SplFixedArraySort::insertionSort($splFixedArray, function($a, $b) {
    if ($a < $b) return 1;
    if ($a > $b) return -1;
    return 0;
});

var_dump($splFixedArray->toArray()); // [8, 6, 5, 4, 3, 0]

Boundaries

Additionally, insertion sort accepts two more arguments - boundaries $low and $high:

$splFixedArray = SplFixedArray::fromArray([5, 3, 8, 6, 0, 4]);

SplFixedArraySort::insertionSort($splFixedArray, null, 2, 4);

var_dump($splFixedArray->toArray()); // [5, 3, 0, 6, 8, 4]

Quicksort

Non-recursive implementation is used, which makes it viable for sorting big arrays. Upon reaching subsets of 5 elements or less, falls back to insertion sort.

$splFixedArray = SplFixedArray::fromArray([5, 3, 8, 6, 0, 4]);

SplFixedArraySort::quickSort($splFixedArray);

var_dump($splFixedArray->toArray()); // [0, 3, 4, 5, 6, 8]

Custom comparison function

$splFixedArray = SplFixedArray::fromArray([5, 3, 8, 6, 0, 4]);

SplFixedArraySort::quickSort($splFixedArray, function($a, $b) {
    if ($a < $b) return 1;
    if ($a > $b) return -1;
    return 0;
});

var_dump($splFixedArray->toArray()); // [8, 6, 5, 4, 3, 0]

Mergesort

A bottom-up (non-recursive) implementation is used.

Usage? You guessed it:

$splFixedArray = SplFixedArray::fromArray([5, 3, 8, 6, 0, 4]);

SplFixedArraySort::mergeSort($splFixedArray);

var_dump($splFixedArray->toArray()); // [0, 3, 4, 5, 6, 8]

Custom comparison function

$splFixedArray = SplFixedArray::fromArray([5, 3, 8, 6, 0, 4]);

SplFixedArraySort::mergeSort($splFixedArray, function($a, $b) {
    if ($a < $b) return 1;
    if ($a > $b) return -1;
    return 0;
});

var_dump($splFixedArray->toArray()); // [8, 6, 5, 4, 3, 0]

Array sort

There is one more sorting method - array sort that uses PHP's sort() (or usort()) method. Usage is same as with the above algorithms:

$splFixedArray = SplFixedArray::fromArray([5, 3, 8, 6, 0, 4]);

SplFixedArraySort::arraySort($splFixedArray);

var_dump($splFixedArray->toArray()); // [0, 3, 4, 5, 6, 8]

Custom comparison function

$splFixedArray = SplFixedArray::fromArray([5, 3, 8, 6, 0, 4]);

SplFixedArraySort::arraySort($splFixedArray, function($a, $b) {
    if ($a < $b) return 1;
    if ($a > $b) return -1;
    return 0;
});

var_dump($splFixedArray->toArray()); // [8, 6, 5, 4, 3, 0]

Why?

When using a regular PHP array, we are offered a vast array (no pun intended) of sorting functions. However, no such thing is offered for SplFixedArray objects in vanilla PHP.

This library is to change that. Currently it offers several methods for sorting SplFixedArray objects. In the future, I might add support for other structures (that make sense to be sorted, like doubly-linked list?).

Installation

composer require the-jj/spl-collections-sort