The most popular Array Sorting Algorithms In PHP

by Luigi Nori Date: 25-08-2020 php arrays sorting algorythm

There are many ways to sort an array in PHP, the easiest being to use the sort() function built into PHP. This sort function is quick but has it's limitations, especially when sorting things like dates as PHP usually guesses which value is higher than the other and can produce odd results. However, there are plenty of sorting algorithms available than can allow you to sort an array in any way you want.

BubbleSort Algorythm

The simplest of these is called the bubble sort. Here is a function that will sort an array of values using the bubble sort algorithm.

function bubbleSort($array)
{
 if (!$length = count($array)) {
  return $array;
 }
 for ($outer = 0; $outer < $length; $outer++) {
  for ($inner = 0; $inner < $length; $inner++) {
   if ($array[$outer] < $array[$inner]) {
    $tmp = $array[$outer];
    $array[$outer] = $array[$inner];
    $array[$inner] = $tmp;
   }
  }
 }
}

This algorithm works by running through the array and swapping a value for the next value along if that value is less than the current value. After the first run through the highest value in the array will be at the correct end. It therefore must run through the array once for every item in the array, so it has a low efficiency.

Bidirectional BubbleSort Algorythm

An improvement on this is the bidirectional bubble sort, in which the items are run through twice at the same time, one going from top to bottom and one going from bottom to top. The following code is an example of a bidirectional bubble sort with an added level of efficiency. This function assumes that after one iteration through the array the first and last elements are in the correct place. It therefore looks at the array minus these two values.

function bidirectionalBubbleSort($array){
 if(!$length = count($array)){
  return $array;
 }
 $start = -1;
 while($start < $length){
  ++$start;
  --$length;
  for($i= $start; $i < $length; ++$i){
   if($array[$i] > $array[$i + 1]){
    $temp = $array[$i];
    $array[$i] = $array[$i + 1];
    $array[$i + 1] = $temp;
   }
  }
  for($i = $length; --$i >=$start;){
   if($array[$i] > $array[$i + 1]){
    $temp = $array[$i];
    $array[$i] = $array[$i + 1];
    $array[$i + 1] = $temp;
   }
  }
 }
}

ShellSort Algorythm

However, this still isn't that efficient. To get another level of efficiency you would need to use a shell short. This works on a "divide and conquer" technique where groups of the array are looked at and sorted individually. Here is an example function.

function shellSort($array)
{
 if (!$length = count($array)) {
  return $array;
 }
 $k = 0;
 $gap[0] = (int)($length/2);
 while($gap[$k]>1){
  $k++;
  $gap[$k] = (int)($gap[$k-1]/2);
 }
 
 for ($i = 0; $i <=$k; $i++) {
  $step = $gap[$i];
  for ($j = $step; $j<$length; $j++) {
   $temp = $array[$j];
   $p = $j-$step;
   while ($p >=0 &&$temp < $array[$p]) {
    $array[$p+$step] = $array[$p];
    $p = $p-$step;
   }
   $array[$p+$step] = $temp;
  }
 }
 return $array;
}

Although this doesn't look like it is efficient it depends on the data you are sorting. In a best case scenario the data will be randomly placed throughout the array and the algorithm will therefore have a good efficiency. Worst case is when all of the data is sorted in the wrong direction before you try to sort it. However, it is worth using this function unless you know for sure that the worst case will happen all of the time. Tests with random number arrays show that this algorithm is a good choice over the bubble sorts.

QuickSort Algorythm

I should mention another algorithm here called a quick sort. The function works by splitting the array into smaller and smaller pieces eventually merging the array back together again at the end. It does this by first finding a middle point and then spitting the array depending on if the current value is higher or lower than the middle value. It then recursively calls itself in order to do the same to each section of the array. Here is an example of a quick sort:

function quickSort($array)
{
 if (!$length = count($array)) {
  return $array;
 }
 
 $k = $array[0];
 $x = $y = array();
 
 for ($i=1;$i<$length;$i++) {
  if ($array[$i] <=$k) {
   $x[] = $array[$i];
  } else {
   $y[] = $array[$i];
  }
 }
 return array_merge(quickSort($x),array($k),quickSort($y));
}

As the name suggests it is a fast way of sorting, and it would be if we were not using PHP. Although this function is very much quicker in Java or C, it is a very slow function in PHP. This is because PHP doesn't handle recursion all that well. In fact when trying to test this function it either timed out the script, or simply gave the following memory error.

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 35 bytes) in C:htdocstest.php on line 130

This occurred when testing an array length of just 50 and happens because every time PHP recursively calls a function it adds that information to the call stack. This error happens because that stack is full. So although quick sort is fast in other languages you should probably stick to a shell sort or something similar. At the very least you will need to use a function that doesn't use recursion.

CheckSort Algorythm

If you fancy writing your own sorting functions then you can use the following function to check your work.

function checkSort($array){
 if (!$length = count($array)) {
  return true;
 }
 for ($i = 0; $i < $length; $i++) {
  if (isset($array[$i+1])) {
   if ($array[$i]>$array[$i+1]) {
    return false;
   }
  }
 }
 return true;
}

Other Sort Algorythms

Counting Sort

function countingSort(&$a) {
	$k = max($a);
	$c = array();
	$n = count($a);
	for ($i = 0; $i <= $k; $i++)
		$c[$i] = 0;
	for ($i = 0;$i < $n; $i++) {
		$c[$a[$i]]++;
	}
	$b = 0;
	for ($j = 0;$j <= $k; $j++) {
		for ($i = 0; $i < $c[$j]; $i++) {
			$a[$b] = $j;
			$b++;
		}
	}
}

HeapSort

function heapSort(&$a) {
	$n = count($a);
	heapMake($a);
	while ($n > 0) {
		list($a[0], $a[$n - 1]) = array($a[$n - 1], $a[0]);
		$n--;
		heapify($a, 0, $n);
	}
}

function heapMake(&$a) {
	$n = count($a);
	for ($i = ($n - 1); $i >= 0; $i--) {
		heapify($a, $i, $n);
	}
}

function heapify(&$a, $pos, $n) {
	while (2 * $pos + 1 < $n) {
		$t = 2 * $pos +1;
		if (2 * $pos + 2 < $n && $a[2 * $pos + 2] >= $a[$t]) {
			$t = 2 * $pos + 2;
		}
		if ($a[$pos] < $a[$t]) {
			list($a[$pos], $a[$t]) = array($a[$t], $a[$pos]);
			$pos = $t;
		}
		else break;
	}
}

InsertSort

function insertSort(&$a) {
	$n = count($a);
	for ($i = 0; $i < ($n - 1); $i++) {
		$key = $i + 1;
		$tmp = $a[$key];
		for ($j = ($i + 1); $j > 0; $j--) {
			if ($tmp < $a[$j - 1]) {
				$a[$j] = $a[$j - 1];
				$key = $j - 1;
			}
		}
		$a[$key] = $tmp;
	}
}

SelectionSort


function selectionSort(&$a) {
	$n = count($a);
	for ($i = 0; $i < ($n - 1); $i++) {
		$key = $i;
		for ($j = ($i + 1); $j < $n; $j++) {
			if ($a[$j] < $a[$key]) $key = $j;
		}
		if ($key != $i) {
			list($a[$key], $a[$i]) = array($a[$i], $a[$key]);
		}
	}
}

MergeSort


function mergeSort(&$a, $first = 0, $last = null) {
	if (is_null($last)) $last = count($a) - 1;
	$function = __FUNCTION__;
	if ($first < $last) {
		$function($a, $first, floor(($first + $last) / 2));
		$function($a, floor(($first + $last) / 2) + 1, $last);

		$tmp = array();

		$middle = floor(($first + $last) / 2);
		$start = $first;
		$final = $middle + 1;
		for ($i = $first; $i <= $last; $i++) {
			if (($start <= $middle) && (($final > $last) || ($a[$start] < $a[$final]))) {
				$tmp[$i] = $a[$start];
				$start++;
			} else {
				$tmp[$i] = $a[$final];
				$final++;
			}
		}

		for ($i = $first; $i <= $last; $i++) {
			$a[$i] = $tmp[$i];
		}
	}
}

GnomeSort

function gnomeSort(&$a) {
	$n = count($a);
	$i = 1;
	$j = 2;
	while ($i < $n) {
		if ($a[$i - 1] < $a[$i]) {
			$i = $j;
			$j++;
		} else {
			list($a[$i], $a[$i - 1]) = array($a[$i - 1], $a[$i]);
			$i--;
			if ($i == 0) {
				$i = $j;
				$j++;
			}
		}
	}
}

OddEvenSort

function oddEvenSort(&$a) {
	$n = count($a);
	$sorted = false;
	while (!$sorted) {
		$sorted = true;
		for ($i = 1; $i < ($n - 1); $i += 2) {
			if ($a[$i] > $a[$i + 1]) {
				//echo "Swap ";
				list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]);
				//printArray($a, array($i, $i + 1), 'blue');
				if ($sorted) $sorted = false;
			}
		}

		for ($i = 0; $i < ($n - 1); $i += 2) {
			if ($a[$i] > $a[$i + 1]) {
				//echo "Swap ";
				list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]);
				//printArray($a, array($i, $i + 1), 'blue');
				if ($sorted) $sorted = false;
			}
		}
	}
}

CombSort

function combSort(&$a) {
	$gap = $n = count($a);
	$swapped = true;
	while ($gap > 1 || $swapped) {
		if ($gap > 1) $gap = floor($gap / 1.24733);
		$i = 0;
		$swapped = false;
		while ($i + $gap < $n) {
			if ($a[$i] > $a[$i + $gap]) {
				list($a[$i], $a[$i + $gap]) = array($a[$i + $gap], $a[$i]);
				if (!$swapped) $swapped = true;
			}
			$i++;
		}
	}
}

cocktailSort

function cocktailSort(&$a) {
	$n = count($a);
	$left = 0;
	$right = $n - 1;
	do {
		//echo "# Left: ".$left." Right: ".$right.EOL;
		for ($i = $left; $i < $right; $i++) {
			//echo "Comparation: ";
			//printArray($a, array($i, $i + 1));
			if ($a[$i] > $a[$i + 1]) {
				//echo "Swap ";
				list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]);
				//printArray($a, array($i, $i + 1), 'blue');
			}
		}
		$right -= 1;
		for ($i = $right; $i > $left; $i--) {
			//echo "Comparation: ";
			//printArray($a, array($i, $i - 1));
			if ($a[$i] < $a[$i - 1]) {
				//echo "Swap ";
				list($a[$i], $a[$i - 1]) = array($a[$i - 1], $a[$i]);
				//printArray($a, array($i, $i - 1), 'blue');
			}
		}
		$left += 1;
	} while ($left <= $right);
}

BubbleSortWithFlag

function bubbleSortWithFlag(&$a) {
	$n = count($a);
	// bubble sorting
	for ($j = 0; $j < ($n - 1); $j++) {
		//echo "Iteration #".$j.EOL;
		$flag = false;
		for ($i = 0; $i < ($n - $j - 1); $i++) {
			//echo T.'#'.$i.T.'v'.$a[$i].EOL;
			//echo "Comparation: ";
			//printArray($a, array($i, $i + 1));
			if ($a[$i] > $a[$i + 1]) {
				//echo "Swap: ";
				list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]);
				//printArray($a, array($i, $i + 1), 'blue');
				if (!$flag) $flag = true;
			}
		}
		if (!$flag) break;
	}
}

combinedBubbleSort

function combinedBubbleSort(&$a) {
	$n = count($a);
	// bubble sorting
	for ($j = 0; $j < ($n - 1); $j++) {
		//echo "Iteration #".$j.EOL;
		$flag = false;
		$min = $j;
		for ($i = $j; $i < ($n - $j - 1); $i++) {
			//echo T.'#'.$i.T.'v'.$a[$i].EOL;
			//echo "Comparation: ";
			//printArray($a, array($i, $i + 1));
			if ($a[$i] > $a[$i + 1]) {
				//echo "Swap: ";
				list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]);
				//printArray($a, array($i, $i + 1), 'blue');
				if (!$flag) $flag = true;
			}
			if ($a[$i] < $a[$min]) $min = $i;
		}
		if (!$flag) break;
		if ($min != $j) {
			//echo "Swap: ";
			list($a[$min], $a[$j]) = array($a[$j], $a[$min]);
			//printArray($a, array($min, $j), 'yellow');
		}
	}
}

StupidSort

function stupidSort(&$a) {
	$n = count($a);
	for ($i = 1; $i < $n; $i ++) {
	//echo "Iteration #".$i.EOL;
		if ($a[$i] < $a[$i - 1]) {
			//echo "Swap :";
			list($a[$i], $a[$i - 1]) = array($a[$i - 1], $a[$i]);
			//printArray($a, array($i, $i - 1));
			$i = 0;
			continue;
		}
	}
}

Benchmarking

You can test how long your algorithm takes to run by using the following PHP benchmarking function. This will convert the result of the php function microtime() into a float value.

function getmicrotime($t){
  list($usec, $sec) = explode(" ",$t);
  return ((float)$usec + (float)$sec); 
}

Use this function to see how long something runs for. At the start of the code call the microtime() function and store the result at the start. At the end store the result of the microtime() function as the end and then use the two values to figure out how long the code took to run.

$start = microtime();
$a = array();
for($i=0;$i<10000;$i++) {
  $a[] = $i;
}
$end = microtime();
$time = (getmicrotime($end) - getmicrotime($start));

The bottom line when benchmarking is to run the same bit of code lots of times. If you run the code once or twice you will find a different result every time. The best thing to do is run the code more than 100 times and take an average.

 
by Luigi Nori Date: 25-08-2020 php arrays sorting algorythm hits : 18099  
 
Luigi Nori

Luigi Nori

He has been working on the Internet since 1994 (practically a mummy), specializing in Web technologies makes his customers happy by juggling large scale and high availability applications, php and js frameworks, web design, data exchange, security, e-commerce, database and server administration, ethical hacking. He happily lives with @salvietta150x40, in his (little) free time he tries to tame a little wild dwarf with a passion for stars.

 
 
 

Related Posts

Examine the 10 key PHP functions I use frequently

PHP never ceases to surprise me with its built-in capabilities. These are a few of the functions I find most fascinating.   1. Levenshtein This function uses the Levenshtein algorithm to calculate the…

How to Track Flight Status in real-time using the Flight Tracker API

The Flight Tracker API provides developers with the ability to access real-time flight status, which is extremely useful for integrating historical tracking or live queries of air traffic into your…

What is a JWT token and how does it work?

JWT tokens are a standard used to create application access tokens, enabling user authentication in web applications. Specifically, it follows the RFC 7519 standard. What is a JWT token A JWT token…

PHP - The Singleton Pattern

The Singleton Pattern is one of the GoF (Gang of Four) Patterns. This particular pattern provides a method for limiting the number of instances of an object to just one.…

How to Send Email from an HTML Contact Form

In today’s article we will write about how to make a working form that upon hitting that submit button will be functional and send the email (to you as a…

The State of PHP 8: new features and changes

PHP 8.0 has been released last November 26: let's discover together the main innovations that the new version introduces in this language. PHP is one of the most popular programming languages…

HTTP Cookies: how they work and how to use them

Today we are going to write about the way to store data in a browser, why websites use cookies and how they work in detail. Continue reading to find out how…

MySQL 8.0 is now fully supported in PHP 7.4

MySQL and PHP is a love story that started long time ago. However the love story with MySQL 8.0 was a bit slower to start… but don’t worry it rules…

Java Sorting Algorithm: Selection Sort

Today we are going to analyze a sorting algorithm that is not very efficient but often used in various fields. We are talking abou the Selection Sort. Let's have a look. Intuition The…

Java Sorting Algorithm: Bubble Sort

Programming, the need to order the collections of data or objects that must then be manipulated often arises. Ordering a list can be useful in cases where you have to do…

Java Sorting Algorithms: Merge Sort

Today we are going to analyze one of the most used sorting algorithms: the Merge Sort. It is part of the Divide and Conquer family, just like the  Quick Sort. Merge Sort offers a better performance…

Java Sorting Algorithms: Quick Sort

Welcome back to this overview about the Java world! Today, we are going to talk about a renowned sorting algorithm: the Quick Sort. The Quick Sort is not very suitable for educational purposes because…