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 : 446  
 
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