Index Sorting in PHP

Index Sort is not a general sorting algorithm because it has a limitation that is the ranges of the element have to be determined beforehand. The idea is simple. The index sorting will check each element one by one and use the element value as its index (plus one for identical elements). The last step would be looping either from low to high or vice versa and output the current value if any. This sorting algorithm is not stable meaning that it does not preserve the orders between idential elements.

However, at some points, this index sorting algorithm is efficient depending on how it will be used. The general space complexity is because it requires an additional array that holds the counter of appearance for each element. The algorithm complexity is that it counts the number of times for each element. The following PHP code illustrates this sorting algorithm and compares the efficiency with the PHP inbuilt asort function. The asort sorts the array by values and preserve the key association. It must’ve been optimised.

The random integers are generated and the timings are recorded. However, this cannot be used as a fair comparison because some PHP may be replaced with a much-optimised ones. Also, the index sorting’s performance largely depends on the ranges of the input elements (i.e. smaller ranges better performance and vice versa). The following limits the input element range from 1 to 100 and the index sorting outperforms the asort.

However, if the element range is the same as the number of elements to sort, e.g. 99999 in this case, there is no much difference between these two sorting functions. Beaware that the index sorting algorithm in theory, has a lower computation complexity which is . But in practice, the last step of this index sorting is time-consuming which re-arrange the elements and put them in the array. If this part is not counted in the sorting procedure of index sorting, then the index sorting is faster.

Despite of this, the index sorting may be recommended if the given element ranges are small. It all depends on how you gonna use this idea. LOL, the following PHP code illustrates the comparisons.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

  // number of elements in the unsorted array
  define("MAXN", 99999);
  define("RANG", 100);
  $arr1 = array();
  $arr2 = array();
  $arr3 = array();
  for ($i = 1; $i <= MAXN; $i ++)
  {
    // generate random numbers between [1, maxn], inclusive
    $arr1[$i] = rand(1, RANG);
    $arr2[$i] = $arr1[$i];
  }
  echo "Before: ".implode(',', $arr1)."
";
  $st = microtime();
  // build-in PHP sorting by values, keep index association.
  asort($arr1);
  $time1 = microtime() - $st;
  echo "After: ".implode(',', $arr1)."
";
  // index sorting
  $st = microtime();
  $cnt = array_fill(1, RANG, 0);
  foreach ($arr2 as $v)
  {
    $cnt[$v] ++;
  }  
  $time3 = round(microtime() - $st, 9);
  for ($i = 1; $i <= RANG; $i ++)
  {
    for ($j = 0; $j < $cnt[$i]; $j ++)
    {
      array_push($arr3, $i);
    }
  }  
  $time2 = microtime() - $st;
  echo "After: ".implode(',', $arr3)."
";
  $time1 = round($time1, 9);
  $time2 = round($time2, 9);
  echo "
Time1: $time1
";
  echo "Time2: $time2 ($time3)
";

  // number of elements in the unsorted array
  define("MAXN", 99999);
  define("RANG", 100);
  $arr1 = array();
  $arr2 = array();
  $arr3 = array();
  for ($i = 1; $i <= MAXN; $i ++)
  {
    // generate random numbers between [1, maxn], inclusive
    $arr1[$i] = rand(1, RANG);
    $arr2[$i] = $arr1[$i];
  }
  echo "Before: ".implode(',', $arr1)."
";
  $st = microtime();
  // build-in PHP sorting by values, keep index association.
  asort($arr1);
  $time1 = microtime() - $st;
  echo "After: ".implode(',', $arr1)."
";
  // index sorting
  $st = microtime();
  $cnt = array_fill(1, RANG, 0);
  foreach ($arr2 as $v)
  {
    $cnt[$v] ++;
  }  
  $time3 = round(microtime() - $st, 9);
  for ($i = 1; $i <= RANG; $i ++)
  {
    for ($j = 0; $j < $cnt[$i]; $j ++)
    {
      array_push($arr3, $i);
    }
  }  
  $time2 = microtime() - $st;
  echo "After: ".implode(',', $arr3)."
";
  $time1 = round($time1, 9);
  $time2 = round($time2, 9);
  echo "
Time1: $time1
";
  echo "Time2: $time2 ($time3)
";

--EOF (The Ultimate Computing & Technology Blog) --