Sorting An Array Without Using Any In-Built PHP Functions

TL;DR

The article discusses the challenge of sorting an array in PHP without using any in-built or PHP core functions, such as sort() and rsort(). The article presents a two for loop method as a solution but then explores more efficient methods, such as the Quicksort algorithm, which is used by PHP for sorting indexed arrays. The article measures the execution time of each method and finds that the two for loop method is inefficient compared to the Quicksort algorithm used by PHP.

I tried to tackle this problem on my own and using for loops I came close. Then I decided to research on Google to see if I was on the right track and what other options are there? I stumbled upon a question/link on Stackoverflow, on the link below: https://stackoverflow.com/questions/12409040/sorting-array-value-without-using-built-in-php-like-sort-etc/. The accepted answer with the most rating was as follows:

$array = array('2','4','8','5','1','7','6','9','10','3');

echo "Unsorted array is: ";

echo "<pre>";
print_r($array);

for($j = 0; $j < count($array); $j ++) {
for($i = 0; $i < count($array)-1; $i ++){
if($array[$i] > $array[$i+1]) {
$temp = $array[$i+1];
$array[$i+1]=$array[$i];
$array[$i]=$temp;
}
}
}

echo "Sorted Array is: ";
print_r($array);
?>

This was similar to what I was thinking of. But it seemed too obvious and didn’t feel right. This feeling sent me on a quest for sorting algorithms and I found this site:

https://www.geeksforgeeks.org/quick-sort/

I explained my quest and research on the StackOverflow question well I believe. So, I’m just going to copy-paste my answer here:

First, let’s check how efficient is this (two for loops) method?

I created an array of 10,000 “count” or values and wrote it in a file to be included later on, for consistency, using the following for code:

$str = "<?php"."\n";
$str .= "$tmp_array = array();"."\n";
$str .= "for($x = 0; $x < 10000; $x++){"."\n";
$str .= "$tmp_array[$x] = mt_rand(0,10000)"."\n";
$str .= "}"."\n";
$str .= "?>"."\n";

$file = fopen('req_arr.php', 'w+');
echo fwrite($file,$str);
fclose($file);

include_once('req_arr.php');

$arr = $tmp_array;

Then I used the two for loops method as given by most of the guys here, and also measured the time taken:

$start = microtime(1);
$cnt = count($arr);
for($i = 0; $i < $cnt; $i++ ){
for($j = 0; $j < $cnt-1; $j++ ){
$temp = '';
if($arra[$j] > $arra[$j+1]){
$temp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $temp;
}
}
}
$stop = microtime(1);
echo $stop - $start;
echo '<pre>';
print_r($arr);

And this gave the execution time (in seconds) to be 7.5408220291138.

Note: This code was tested in XAMPP on Windows10, 64 bit, i7 gen 4, 8 GB RAM, and in Chrome. This is way too much. I’m sure PHP can’t be this sloppy. So next I tested the in-built PHP rsort() function, using the following code:

$start = microtime(1);

rsort($arr, SORT_NUMERIC);

$stop = microtime(1);

echo $stop - $start;

echo '<pre>';

print_r($arr);

This time, the execution time was just 0.0033688545227051 seconds. JUST 0.003 SECONDS for sorting a 10,000 values array. Clearly, the two For loop method is inefficient compared to whatever PHP is using at its core.

Quick research on Google/PHP.net gave me the answer that PHP uses the Quicksort algorithm to sort the indexed array, and that it doesn’t use two for loops but recursive function. I dug deeper and found a few examples of Quicksearch for C++, Java, etc. So, I replicated them in PHP, as follows:

/*
The main function that implements QuickSort
arr --> Array to be sorted,
low --> Starting index,
high --> Ending index
*/
function quickSort(&$arr, $low, $high)
{
if ($low < $high)
{
/* pi is partitioning index, arr[p] is now
at right place */
$pi = partition($arr, $low, $high);

// Separately sort elements before
// partition and after partition
quickSort($arr, $low, $pi - 1);
quickSort($arr, $pi + 1, $high);
}

return $arr;
}

function partition (&$arr, $low = 0, $high)
{
$pivot = $arr[$high]; // pivot
$i = ($low - 1); // Index of smaller element

for ($j = $low; $j <= $high-1; $j++)
{
// If current element is smaller than or
// equal to pivot
if ($arr[$j] <= $pivot)
{
$i++; // increment index of smaller element
swap($arr[$i], $arr[$j]);
}
}

swap($arr[$i + 1], $arr[$high]);
return ($i + 1);
}

function swap(&$a, &$b){
$t = $a;
$a = $b;
$b = $t;
}

Obviously, this could be further optimized but I just wanted to get something running and see the results, and this was sufficient. So, now let’s see the results:

$start = microtime(1);
$sarr = quickSort($array, 0, $cnt-1);
$stop = microtime(1);
echo $stop - $start;
echo '<pre>';
print_r($sarr);
die();

The time taken by this algorithm came out to be: 0.022707939147949 Sec  Still, not as fast as rsort() but satisfactory. I tried the same with a million values array too but the two for loops array just exhausted the memory and I decided even a 10,000 value array proves the theory well.

So, now you know, and I’m sure understanding this would help you in some way and would also make you appreciate the PHP core functions which help us immensely.

Check out our web development services and pricing page and contact us today for more information.

Happy Coding… 🙂