PHP Sort Algorithms

A play to implement some sorting algorithms PHP.

Not built for speed. Built to understand functionality. You would better off using internal sorting algorithms for speed.

	<?php
	/**
	* BubbleSort in PHP
	*
	* @param array $data
	* @return array
	*/
	function bubblesort ($data) {
	$length = count($data);
	for ($i = 0; $i < $length; $i++) {
	for ($j = 0; $j < ($length - 1); $j++) {
	if ($data[$i] < $data[$j]) {
	$tmp = $data[$i];
	$data[$i] = $data[$j];
	$data[$j] = $tmp;
	}
	}
	}
	return $data;
	}
	$data = [265, 7, 3, 2, 9, 8, 7, 12, 234, 43, 856, 3, 12, 0, 332, 479];
	$sort = bubblesort($data);
	echo "<pre>";
	print_r($sort);
	echo "</pre>";
	exit;

view raw bubblesort.php hosted with by GitHub

	<?php
	/**
	* InsertionSort in PHP
	*
	* @param array $data
	* @return array
	*/
	function insertionsort ($data) {
	$length = count($data);
	for ($i = 1; $i < $length; $i++) {
	for ($j = ($i - 1); $j >= 0; $j--) {
	if ($data[$j] > $data[$j + 1]) {
	$tmp = $data[$j + 1];
	$data[$j+1] = $data[$j];
	$data[$j] = $tmp;
	}
	}
	}
	return $data;
	}
	$data = [265, 7, 3, 2, 9, 8, 7, 12, 234, 43, 856, 3, 12, 0, 332, 479];
	$sort = insertionsort($data);
	echo "<pre>";
	print_r($sort);
	echo "</pre>";
	exit;

view raw insertionsort.php hosted with by GitHub

	<?php
	/**
	* MergeSort in PHP
	*
	* @param array $data
	* @return array
	*/
	function mergesort ($data) {
	$length = count($data);
	if ($length == 1) {
	return $data;
	}
	$mid = $length /2;
	$left = array_slice($data, 0, $mid);
	$right = array_slice($data, $mid, $length);
	/**
	* Natural way of splitting data in half, without using internal
	* functions of php
	* @var array
	*/
	/*$left = [];
	$right = [];
	for ($i = 0; $i < $length; $i++) {
	if ($i < $length/2) {
	$left[] = $data[$i];
	} else {
	$right[] = $data[$i];
	}
	}*/
	$result = [];
	$left = mergesort($left);
	$right = mergesort($right);
	/**
	* MERGE
	*
	* Seen other versions that breaks this functionality into a lone
	* function, but not sure I understand why
	*/
	while (count($left) > 0 && count($right) > 0) {
	if ($left[0] <= $right[0]) {
	$result[] = array_shift($left);
	} else {
	$result[] = array_shift($right);
	}
	}
	while (count($left) > 0) {
	$result[] = array_shift($left);
	}
	while (count($right) > 0) {
	$result[] = array_shift($right);
	}
	return $result;
	}
	$data = [265, 7, 3, 2, 9, 8, 7, 12, 234, 43, 856, 3, 12, 0, 332, 479, 99];
	$sort = mergesort($data);
	echo "<pre>";
	print_r($sort);
	echo "</pre>";
	exit;

view raw mergesort.php hosted with by GitHub

Quick Sort

Quick sort is usually an effective sorting algorithm. This implementation is about 80% slower than the default sort() function within PHP.

Wikipedia also mentions that this is a “naive implementation“. Taking the first element in the array can be a low number (if we’d already sorted some of the array), and therefore bring us close to O(n²)… which is bad.

	<?php
	/**
	* Quick Sort in PHP
	*
	* This sort algorithms is close to 80% slower than sort() when
	* sorting ~10,000 integers. Use internal functions.
	*
	* @param array $data
	* @return array
	*/
	function quicksort ($data) {
	$length = count($data);
	if ($length < 2) {
	return $data;
	}
	// Taking the first element in the array is
	$pivot = $data[0];
	$left = [];
	$right = [];
	for ($i=1; $i < $length; $i++) {
	if ($data[$i] < $pivot) {
	$left[] = $data[$i];
	} else {
	$right[] = $data[$i];
	}
	}
	return array_merge(quicksort($left), [$pivot], quicksort($right));
	}
	$data = [265, 7, 3, 2, 9, 8, 7, 12, 234, 43, 856, 3, 12, 0, 332, 479, 99];
	$sort = quicksort($data);
	echo "<pre>";
	print_r($sort);
	echo "</pre>";
	exit;

view raw quicksort.php hosted with by GitHub

Photo by Aleks Dahlberg on Unsplash