Preserve Key Order (Stable Sort) When Sorting With PHP'S Uasort

Preserve key order (stable sort) when sorting with PHP's uasort

Since PHP does not support stable sort after PHP 4.1.0, you need to write your own function.

This seems to do what you're asking: http://www.php.net/manual/en/function.usort.php#38827

As the manual says, "If two members compare as equal, their order in the sorted array is undefined." This means that the sort used is not "stable" and may change the order of elements that compare equal.

Sometimes you really do need a stable sort. For example, if you sort a list by one field, then sort it again by another field, but don't want to lose the ordering from the previous field. In that case it is better to use usort with a comparison function that takes both fields into account, but if you can't do that then use the function below. It is a merge sort, which is guaranteed O(n*log(n)) complexity, which means it stays reasonably fast even when you use larger lists (unlike bubblesort and insertion sort, which are O(n^2)).

<?php
function mergesort(&$array, $cmp_function = 'strcmp') {
    // Arrays of size < 2 require no action.
    if (count($array) < 2) return;
    // Split the array in half
    $halfway = count($array) / 2;
    $array1 = array_slice($array, 0, $halfway);
    $array2 = array_slice($array, $halfway);
    // Recurse to sort the two halves
    mergesort($array1, $cmp_function);
    mergesort($array2, $cmp_function);
    // If all of $array1 is <= all of $array2, just append them.
    if (call_user_func($cmp_function, end($array1), $array2[0]) < 1) {
        $array = array_merge($array1, $array2);
        return;
    }
    // Merge the two sorted arrays into a single sorted array
    $array = array();
    $ptr1 = $ptr2 = 0;
    while ($ptr1 < count($array1) && $ptr2 < count($array2)) {
        if (call_user_func($cmp_function, $array1[$ptr1], $array2[$ptr2]) < 1) {
            $array[] = $array1[$ptr1++];
        }
        else {
            $array[] = $array2[$ptr2++];
        }
    }
    // Merge the remainder
    while ($ptr1 < count($array1)) $array[] = $array1[$ptr1++];
    while ($ptr2 < count($array2)) $array[] = $array2[$ptr2++];
    return;
}
?>

---

Also, you may find this forum thread interesting.

PHP usort reorders array the sort value is the same for all

Aha, a case for the Schwartzian Transform.

It basically consists of three steps:

1. decorate; you turn every value into an array with the value as the first element and the key/index as the second
2. sort (as per normal)
3. undecorate; you reverse step 1

Here it is (I've tweaked it to your particular use case):

function decorate(&$v, $k)
{
    $v['authn_weight'] = array($v['authn_weight'], $k);
}

function undecorate(&$v, $k)
{
    $v['authn_weight'] = $v['authn_weight'][0];
}

array_walk($a, 'decorate');
usort($a, 'weightSortImplementation');
array_walk($a, 'undecorate');

The trick is in the following assertion:

array($x, 0) < array($x, 1)

This is what keeps the correct order of your array. And, no recursion required :)

arsort() not stable

You don't need to sort the array if you're only looking for the preferred language:

<?php

function findPrefferedLanguage($languages) {
  foreach ($languages as $lang => $weight) {
    if (empty($key) || ($weight > $languages[$key])) {
      $key = $lang;
    }
  }

  return $key;
}

$foo = array('es' => .6, 'en' => 1, 'fr' => 1, 'de' => .5);    

var_dump(findPrefferedLanguage($foo)); // en

Hastily tested... there's probably some edge-cases that will generate errors/warnings.

How to have a stable sort in PHP with arsort()?

Construct a new array whose elements are the original array's keys, values, and also position:

$temp = array();
$i = 0;
foreach ($array as $key => $value) {
  $temp[] = array($i, $key, $value);
  $i++;
}

Then sort using a user-defined order that takes the original position into account:

uasort($temp, function($a, $b) {
 return $a[2] == $b[2] ? ($a[0] - $b[0]) : ($a[2] < $b[2] ? 1 : -1);
});

Finally, convert it back to the original associative array:

$array = array();
foreach ($temp as $val) {
  $array[$val[1]] = $val[2];
}

Why usort reverts an array when values are equals on PHP prior to 7.0

If you want to have the same results in both versions, you will need to ensure that you specify how equal items will deal with other fields.

So you could solve this with...

usort($arr1, function ($a, $b) {
    if($a['points'] == $b['points']){
      return $a['date'] - $b['date'];
    }
    return ($a['points'] < $b['points']) ? 1 : -1;
});

So if the points value is the same, then use date as the differentiator (assuming a numeric comparison would work.)

Sorting array keeping even values on top PHP

usort is not stable. The documentation states:

If two members compare as equal, their relative order in the sorted array is undefined.

So, what you can do is:

usort($array, function($a, $b) {
                if ($a % 2 == $b % 2) {
                    return intval($a - $b);
                }
                elseif ($a % 2 == 0 )
                { 
                    return -1 ;
                }
                else 
                { 
                    return 1;
                }
        }
    );

This compares the actual values if both are even or both are odd.

---

Related Topics