4

In a PHP project I have some data I want to sort using a linear time, simple counting sort:

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);
$count = array();
foreach ($ar as $v)
    $count[$v]++;
$sorted = array();    
foreach ($count as $v => $c)
    for ($i = 0; $i < $c; $i++)
        $sorted[] = $v;

The problem is that the above obviously doesn't work. The php array works more like a hashmap than an array. The code can be made to work by inserting ksort($count) before the final loop, but ksort runs in O(nlogn) which destroys the entire point.

Is there any way to do a linear time sort in php? Perhaps using some paramter to array(), or some entirely different structure?

Improve this question
5
  • 2
    Are you trying to sort the array based on how many times an item occurs in that array? So in your above example "7" would be first because it occurs more (3) times than any other number? Commented Dec 30, 2011 at 16:21
  • 1
    The above is supposed to leave $sorted as a sorted version of $ar. That is array(0,0,2,3,6,7,7,7,8,12). Currently it gives array(7,7,7,2,0,0,3,8,12,6). Commented Dec 30, 2011 at 16:29
  • 1
    So speed is not an issue, but it needs to run linear? Commented Dec 30, 2011 at 17:41
  • Despite the little fixes needed in your algorithm, you were right. The accepted answer is O(nlogn) too! May be, as you suggested, is related with the inner use of hybrid hash tables instead of classical arrays. Commented Sep 24, 2020 at 23:29
  • I just tried using SplFixedArray, and it grows like O(nlogn) too, and is slower. Commented Sep 25, 2020 at 0:01

6 Answers 6

Reset to default
3

You didn't follow the algorithm correctly. This is O(n).

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);
$count = array();
foreach ($ar as $v) {
    $count[$v] = isset($count[$v]) ? $count[$v] + 1 : 1;
}
$sorted = array();
$min = min($ar);
$max = max($ar);
for ($i=$min; $i<=$max; $i++) {
    if (isset($count[$i])) {
        for ($j=0; $j<$count[$i]; $j++) {
            $sorted[] = $i;
        }
    }
}

also, see array_count_values(), or alternatively compute the min and max inside the counting loop.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

What about the second one, can you make an array default to 0?
you can use array_fill(), but that creates real entries in the array. array_fill and array_merge could replace the inner most for loop though, I just didn't want to get fancy.
@ThomasAhle: Drop that function, even if it's O(n), it's much more slower than PHP's interal sort(). You're comparing complexity at the wrong place.
Nice answer, but there is a little bug in your for - test. In your sorted array "sorted" you have missed the element with the value "12". This can be fixed by using "$i<=$max" instead of "$i<$max" in the for - test!
I did some benchmarking. Using array_count_values() made the algorithm a 20% faster, while computing min and max inside the counting loop made it 20% slower. By the way, is not O(n) in PHP. Is O(nlogn) instead. May be is related with the inner use of hybrid hash tables instead of classical arrays.
1

Approved answer is wrong. Correct:

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);
$count = array();
foreach ($ar as $v) {
    $count[$v] = isset($count[$v]) ? $count[$v] + 1 : 1;
}
$sorted = array();
$min = min($ar);
$max = max($ar);
for ($i=$min; $i  <=   $max; $i++) {
    if (isset($count[$i])) {
        for ($j=0; $j<$count[$i]; $j++) {
            $sorted[] = $i;
        }
    }
}
Improve this answer

3 Comments

Yes, from a quick comparison, I can see no difference.
Is it wrong because of style or wrong as in just wrong... why would it get approved if it were wrong?
He is right! The for - test was not correct ... In the answer above the element "12" is missing. The right for - test is "$i<=$max" instead of "$i<$max"!
0

If i understand your question AND comment correctly, just using sort($count) would work no?

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);
$sorted = $ar;
sort($sorted);
var_dump($ar);
var_dump($sorted);

Result:

array(7,2,0,3,8,0,12,7,6,7);
array(0,0,2,3,6,7,7,7,8,12);

But i'm wondering what the foreach($ar as $v)$count[$v]++; does... doesn't really make sense...

Improve this answer

3 Comments

The question is called "Counting sort" because I'm looking to implement a counting sort. Counting sort has the advantage of running in O(n+k) where k is the size of the largest element. sort() runs in O(nlogn).
Still, the result is the same no? Quicksort is slow if you have thousands of elements, but PHP is usually not meant to process that kind of information. You use MySQL do to so. So what is the means of the question in the end if i might ask?
Teaching the quirks of php I guess :) And in the case where you have data well suited for counting sort anyway.
0

Adding some comments to the code to show you why this doesn't do what you think it should do.

$ar = array(7, 2, 0, 3, 8, 0, 12, 7, 6, 7);

$count = array();
foreach ($ar as $v) {
    // add each number in $ar to $count.
    // the first number in $ar is 7, so 7 will be the first number in $count.
    // because 7 is in $ar 3 times, $count[7] == 3.
    $count[$v]++;
}

// the output of print_r will be very revealing:
print_r($count);
/*Array
(
    [7] => 3
    [2] => 1
    [0] => 2
    [3] => 1
    [8] => 1
    [12] => 1
    [6] => 1
)*/

$sorted = array();    
foreach ($count as $v => $c) {
    // the first entry: $count[7] == 3
    // so add 7 to $sorted 3 times.
    // the second entry: $count[2] == 1
    // so add 2 to $sorted 1 time.
    // etc.
    for ($i = 0; $i < $c; $i++) {
        $sorted[] = $v;
    }
}

This simply groups numbers together based on their location in the first array.

Improve this answer

1 Comment

Thank you, but as I wrote in the question, the code "obviously doesn't work". I just wanted to show you the algorithm you would use in C or Java. I hoped somebody could tell me a way to make it work in php (in the proposed complexity).
0

To get the sorted $ar in a variable of it's own ($sorted), it's pretty trivial:

$sorted = $ar;
sort($sorted);

Which makes me think that your question and comment is not giving the whole picture.

Edit: Now after you have clarified that you wanted to implement a specific algorithm (and you actually got an answer already that shows some points that were wrong implementing it first), I think it's worth to focus on another aspect of your question:

You're comparing the complexity of two (theoretical) algorithms, but you're leaving aside how the algorithms are implemented.

PHP's sort() - even based on "bad" quicksort, will outrun your own PHP usercode implementation of some other algorithm by numbers.

You just have compared the wrong parameters here. The complexity of a function does not says much when you compare a build-in PHP function with some function in your user-code.

Improve this answer

7 Comments

Yeah had the same bogus running... Question is either not clear or problem is overly simple...
The PHP sort is a quicksort, see: php.net/manual/en/function.sort.php That means in runs worst case O(n^2) and O(nlogn) in average.
There are other sort algorithms, which one would you prefer if you think quicksort is too slow?
@hakre: Counting sort obviously ;)
@ThomasAhle: Edited the answer, the complexity you talk about are two pair of shoes. You can't compare those two functions which each other unless you metric in your specific case.
|
0 
$A = [1, 2, 2, 2, 1, 3, 3, 1, 2, 4, 5, 0, 0]; // example array
$m = max($A);
$count = array_fill(0, $m + 1, '0');
foreach ($A as $value) $count[$value] += 1;
       // next step is print the numbers 
$a = [];
foreach ($count as $key => $value) {
    for ($i = 0; $i < $value;) {
        array_push($a, $key);;
        $i++;
    }
}

var_dump($count); // print the sorted array
var_dump($a); // print the numbers (low to high)
Improve this answer

1 Comment

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.