php uasort() with stable stability

[andrewschools]

Hello -

Looking to find a function that works just like the php function uasort() but have it maintain the relative order of items when equal keys are found.

Here's my code now:

$array = array("item1"=>-1,"item2"=>-1,"item3"=>-1,"item4"=>0,"item5"=>2,"item6"=>2,"item7"=>1);

function sortThis($a,$b)
{
  if( $a == -1 || $b == -1 )
  {
    return 0;
  }
  elseif ($a == $b)
  {
    return 0;
  }
  return ($a < $b) ? -1 : 1;
}

uasort($array,"sortThis");

As you can see from the code above, I'm also returning 0 if negative #'s are found since all negative numbers must stay relative to where they are in the list (just like equal #). However, since php removed stable sort and do not keep the original order for elements comparing as equal, the code above returns:

array(7) {
  ["item1"]=>
  int(-1)
  ["item3"]=>
  int(-1)
  ["item4"]=>
  int(0)
  ["item7"]=>
  int(1)
  ["item6"]=>
  int(2)
  ["item5"]=>
  int(2)
  ["item2"]=>
  int(-1)
}

Item2 was moved down the list when it did not need to be moved since it's compared as an equal #. What I need returned is:

array(7) {
  ["item1"]=>
  int(-1)
  ["item2"]=>
  int(-1)
  ["item3"]=>
  int(-1)
  ["item4"]=>
  int(0)
  ["item7"]=>
  int(1)
  ["item6"]=>
  int(2)
  ["item5"]=>
  int(2)
}

Any help appreciated!

Thanks,
Andrew Schools

[NettSite]

The best I could come up with is the following, but it doesn't move item5 down the list, and that is what you say you want. I think moving item5 down, with value equal to item6, and not moving item2, may be a challenge.

$array = array("item1"=>-1,"item2"=>-1,"item3"=>-1,"item4"=>0,"item5"=>2,"item6"=>2,"item7"=>1);
foreach ($array as $key=>$value) {
  $keys[] = $key;
  $data[] = $value;
}
array_multisort($data,SORT_ASC,$keys,SORT_ASC,$array);
echo nl2br(var_export($array,true));

[andrewschools]

Thank you, however, this would not work because it isn't stable sort. Items must stay in their position if they are found to be equal.

[NettSite]

I am not sure I understand what you mean. The output of my script is as follows:

array (
'item1' => -1,
'item2' => -1,
'item3' => -1,
'item4' => 0,
'item7' => 1,
'item5' => 2,
'item6' => 2,
)

Items 1,2,3 and 4 have remaimed in their original positions, and 7 has moved into it's correct position according to value, and 5 and 6 have remained in the same position relative to each other.

[andrewschools]

Your example is not stable sort. Just move item2 to the end of the array and use your sort method. It will not keep item2 at the end of the array. You cannot use any php sort methods as a solution because none of them support stable sort after php 4.1.0

[andrewschools]

The array I gave was a bad example. Here's a better example:

$array = array("item1"=>-1,"item3"=>-1,"item4"=>0,"item5"=>2,"item6"=>2,"item7"=>1,"item2"=>-1);

[mschroeder]

@andrewschools
I don't believe you are using the correct definition of stable sort.
By definition a stable sort, the sort is performed by key/index. Where when duplicate keys exist the relative order of their values is maintained. In PHP you can not have two array items with the same key.

e.g. If you have a data set like (letters denote that we have multiple instances of the same key for reference):

(1b, 1) (1a, 1) (1c, 1) (0a, 1) (0c, 1) (0b, 1)

it would sort to:

(0a, 1) (0c, 1) (0b, 1) (1b, 1) (1a, 1) (1c, 1)

In the data set your provided:

$array = array("item1"=>-1,"item3"=>-1,"item4"=>0,"item5"=>2,"item6"=>2,"item7"=>1,"item2"=>-1);

would stable sort to:

(item1, -1)(item2, -1)(item3, -1)(item4, 0)(item5, 2)(item6, 2)(item7, 1)

since you do not have any duplicate keys it would be sorted by key only.

What it appears you're asking for, is a sort by value while maintaining relative position of the keys so your result set would be:

(item1, -1)(item3, -1)(item2, -1)(item4, 0)(item7, 1)(item5, 2)(item6, 2)

Problem being something like asort() is resulting in:

array
  'item2' => int -1
  'item3' => int -1
  'item1' => int -1
  'item4' => int 0
  'item7' => int 1
  'item5' => int 2
  'item6' => int 2

Where it is sorting by value, but not maintaining the correct order of the keys.

Am I correct in understanding the problem at this point? Essentially a stable sort using the value as the key and the key as the value.

[andrewschools]

Hello -

Thank you for your reply. I do understand what you are saying, however, it looks that PHP usort used to keep the original order for elements comparing as equal prior to 4.1.0. That's why in my code above I'm returning 0 when both a+b are equal or if a is equal to -1. Since PHP 4.1.0, according to their website, "a new sort algorithm was introduced. The cmp_function doesn't keep the original order for elements comparing as equal." What I'm looking for is a way this can be accomplished. Maybe it's not really stable sort I'm looking for. I'm assuming there must be a sorting algorithm out there that essential skips items comparing as equal.

Thank You
Andrew Schools

[andrewschools]

Am I correct in understanding the problem at this point? Essentially a stable sort using the value as the key and the key as the value.

Maybe? As long as the key indexes are maintained and there can be duplicate keys which can be compared numerically.

[NettSite]

The array I gave was a bad example. Here's a better example:

$array = array("item1"=>-1,"item3"=>-1,"item4"=>0,"item5"=>2,"item6"=>2,"item7"=>1,"item2"=>-1);

What would your desired result be?

[andrewschools]

Array:

$array = array("item1"=>-1,"item3"=>-1,"item4"=>0,"item5"=>2,"item6"=>2,"item7"=>1,"item2"=>-1);

Would be sorted to:

"item1"=>-1,
"item3"=>-1,
"item4"=>0,
"item7"=>1,
"item5"=>2,
"item6"=>2,
"item2"=>-1

I need to maintain the relative order of records with equal keys (i.e., values)

[NettSite]

Good luck! Beats me. I would have thought that -1 is less than 1, so should be moved before 1, at the very least - that's if you consider all minus values to be equal to 0. -1 is certainly not equal to 2.

What is the bigger picture? What are you trying to do? Maybe there is a different approach altogether.

[andrewschools]

I would have thought that -1 is less than 1, so should be moved before 1, at the very least - that's if you consider all minus values to be equal to 0. -1 is certainly not equal to 2.

Here's another example without any negative numbers. However, the relative order of records with equal keys will not be maintained. I was only using negative numbers to show what items I was referring too. Here's another example :

$array = array("item1"=>0,"item2"=>0,"item3"=>0,"item4"=>1,"item6"=>3,"item7"=>3,"item5"=>2);
asort( $array,SORT_NUMERIC );
var_dump( $array );

In the example above, item5 should fall into place so the results should be:

array(7) {
  ["item1"]=>
  int(0)
  ["item2"]=>
  int(0)
  ["item3"]=>
  int(0)
  ["item4"]=>
  int(1)
  ["item5"]=>
  int(2)
  ["item6"]=>
  int(3)
  ["item7"]=>
  int(3)
}

But if you sort this array, this will not be the result.

What is the bigger picture? What are you trying to do? Maybe there is a different approach altogether.

There isn't any bigger picture other than I want stable sort for php. There has been several instances lately where I needed to maintain the relative order of records with equal keys (stable sort) in arrays I've being working with.

[NettSite]

I have just tried my code with your latest example, and it ouputs the result you want:

$array = array("item1"=>0,"item2"=>0,"item3"=>0,"item4"=>1,"item6"=>3,"item7"=>3,"item5"=>2);
foreach ($array as $key=>$value) {
  $keys[] = $key;
  $data[] = $value;
}
array_multisort($data,SORT_ASC,$keys,SORT_ASC,$array);
echo nl2br(var_export($array,true));

[andrewschools]

Hello -

Actually, your right. This is another bad example I did not test first before submitting my results. But moving an item equal to 0 to the end of this list will not work because all you are doing is sorting an array numerically which I already know how to do :-) I appreciate all your help in this matter but I know any of your attempts to use PHP sort functions will not provide me with a solution because PHP sort functions do not provide stable sort capability. See here: http://bugs.php.net/bug.php?id=53341&edit=2

I will just need to convert a C/C++ stable sort algorithm to PHP which I was hoping already existed: http://www.cplusplus.com/reference/algorithm/stable_sort/

Thank You
Andrew Schools

[redfox23]

http://notmysock.org/blog/php/schwartzian-transform.html

This neat solution works just fine.
Hope it helps.