Archive
Merge sort algorithm – PHP implementation
Heapsort is a divide and conquer algorithm that was invented by John von Neumann in 1945.
Algorithm:
- Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
- Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.
Performance:
- Worst case: O(n logn)
- Average case: O(n logn)
- Best case: O(n logn)
PHP implementation (a special class for merge sorting):
class mergeSort {
/**
* splitting the array recursively until has max two elements
* merging and sorting recursively until sorted array is built
*
* @param type $array
* @return array Sorted input array
*/
public function sort($array) {
//if array has 1 element return that element
$count=count($array);
if ($count<=1)
return $array;
//split array and build left and right arrays
$mid=(int)$count/2;
$left=array();
$right=array();
for ($i=0;$i<$mid;$i++) {
$left[]=$array[$i];
}
for ($i=$mid;$imerge($this->sort($left),$this->sort($right));
}
/**
* merge left and right arrays sorting elements
*
* @param array $left
* @param array $right
* @return array
*/
private function merge($left,$right) {
$sorted=array();
//compare first element from left with first element from right
//add the lowest to $sorted and erase it from parent array
while (count($left)>0 && count($right)>0)
if ($left[0]<$right[0]) {
$sorted[]=$left[0];
array_shift($left);
} else {
$sorted[]=$right[0];
array_shift($right);
}
//after one of right and left arrays is empty is added elements from
//remaining to $sorted
for ($i=0;$i<count($left);$i++)
$sorted[]=$left[$i];
for ($i=0;$i<count($right);$i++)
$sorted[]=$right[$i];
return $sorted;
}
}
Bibliography:
- Introduction to Algorithms – Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- Algorithms – Robert Sedgewick
- http://en.wikipedia.org/wiki/Merge_sort
Heapsort algorithm – PHP implementation
Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family.
Algorithm:
- Build a heap (heap is a tree structure with rule that parent value are bigger or equal with childrens values) out of the data.
- Removing the largest element from the heap and insert in sorted array starting with first position (0).
- Reconstruct the heap with remaining elements and add largest value in sorted array.
Heap sort can be performed in place by spliting the array in two parts, the heap and the sorted array.
Performance:
- Worst case: O(n logn)
- Average case: O(n logn)
- Best case: O(n logn)
PHP implementation (a special class for heap sorting):
class heapSort {
/**Change first value to the end of array recursively
*
* @param array $array
* @return array
*/
public function heap(&$array) {
$length=count($array);
$this->heapify($array,$length);
$end=$length-1;
while ($end>0) {
$tmp=$array[0];
$array[0]=$array[$end];
$array[$end]=$tmp;
$end=$end-1;
$this->siftDown($array,0,$end);
}
return $array;
}
/**Build binary tree
*
* @param array $array
* @param integer $count
*/
private function heapify(&$array,$count) {
$start=floor(($count-2)/2);
while ($start>=0) {
$this->siftDown($array,$start,$count-1);
$start=$start-1;
}
}
/**Arrange tree branch: parent node bigger than his children
*
* @param array $array
* @param integer $start
* @param integer $end
* @return when tree is sorted
*/
private function siftDown(&$array,$start,$end) {
$root=$start;
while ($root*2+1<=$end) {
$left=$root*2+1;
$swap=$root;
//check who is the bigger between root,left child and right child
if ($array[$swap]<$array[$left]){
$swap=$left;
}
if ($left+1<=$end && $array[$swap]<$array[$left+1]){
$swap=$left+1;
}
//swap root with bigger children (if exist)
if ($swap!=$root) {
$tmp=$array[$root];
$array[$root]=$array[$swap];
$array[$swap]=$tmp;
$root=$swap;
} else return;
}
}
}
Bibliography:
- Introduction to Algorithms – Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- Algorithms – Robert Sedgewick
- http://en.wikipedia.org/wiki/Heapsort
Improvement of Quicksort algorithm – PHP implementation
Because quicksort has bad performance on little arrays (or list) I used Insertion sort for arrays with fewer than 30 elements (I ran some tests and found that 30 is better than 20 or 40).
This improvement is faster with around 30-40%.
PHP implementation (function from a larger sort Class that use Insertion method discussed earlier):
/**Function for sorting an array with optimized quick sort algorithm.
*
* @param array $array
* @return array
*/
public static function optQuickSort(array $array) {
if (count($array)<30)
return self::insertionSort($array);
$low=array();
$high=array();
$length=count($array);
$pivot=$array[0];
for ($i=1;$i<$length;$i++) {
if ($array[$i]<$pivot) {
$low[]=$array[$i];
} else {
$high[]=$array[$i];
}
}
return array_merge(self::optQuickSort($low),array($pivot),
self::optQuickSort($high));
}
}
Bibliography:
- Introduction to Algorithms – Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- Algorithms – Robert Sedgewick
- http://en.wikipedia.org/wiki/Quick_sort
Quick Sort algorithm – PHP implementation
Quicksort is a divide and conquer algorithm: recursively split a large array in two sub-arrays, one with low elements and second with high elements.
Algorithm:
- Pick an element, called pivot, from the list.
- Reorder hte list so the element with value less than pivot came before pivot, and elements higher came after the pivot.
- Recursively sort the sub-list of lower and higher elements.
This algorithm is used as built-in in PHP and in MySQL and is most widely used.
Performance:
- Worst case: O(n2)
- Average case: O(n logn)
- Best case: O(n logn)
PHP implementation (function from a larger sort Class):
/**Function for sorting an array with quick sort algorithm.
*
* @param array $array
* @return array
*/
public static function quickSort(array $array) {
if (count($array)<2)
return $array;
$low=array();
$high=array();
$length=count($array);
$pivot=$array[0];
for ($i=1;$i<$length;$i++) {
if ($array[$i]<$pivot) {
$low[]=$array[$i];
} else {
$high[]=$array[$i];
}
}
return array_merge(self::quickSort($low),array($pivot),
self::quickSort($high));
}
Bibliography:
- Introduction to Algorithms – Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- Algorithms – Robert Sedgewick
- http://en.wikipedia.org/wiki/Quick_sort
Gnome Sort algorithm – PHP implementation
Algorithm:
- Finds the first place where two adiacent elements are in wrong order and swap them.
- Check to the left if there are wrong order of two adiacent elements and swap if found.
- If not found other elements on left continue with step 1.
Gnome sort is a sorting algorithm which is similar to insertion sort, except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort.
Performance:
- Worst case: O(n2)
- Average case: O(n2)
- Best case: O(n)
PHP implementation (function from a larger sort Class):
/**Function for sorting an array with gnome sort algorithm.
*
* @param array $array
* @return array
*/
public static function gnomeSort(array $array) {
$i=1;
while($i<count($array)) {
if ($array[$i]>=$array[$i-1]){
$i++;
} else {
//swap the elements
$tmp=$array[$i];
$array[$i]=$array[$i-1];
$array[$i-1]=$tmp;
if ($i>1) {
$i--;
}
}
}
return $array;
}
Bibliography:
Comb Sort algorithm – PHP implementation
Algorithm:
- Compare each pair of elements found on positions n and n+gap and, if they are in reversed order, swap them.
- Change the step by division with 1.3
- If step is 1 do bubble sort
In bubble sort, when any two elements are compared, they always have a gap (distance from each other) of 1. The basic idea of comb sort is that the gap can be much more than 1 (Shell sort is also based on this idea, but it is a modification of insertion sort rather than bubble sort).
Performance:
- Worst case: O(n2)
- Average case: O(n logn)
- Best case: O(n)
PHP implementation:
/**Function for sorting an array with comb sort algorithm.
*
* @param array $array
* @return array
*/
public static function combSort(array $array) {
$swapped=false;
$j=0;
$length=count($array);
$gap=$length;
while($gap>1 || $swapped) {
if ($gap>1) {
$gap=floor($gap/1.2473);
}
$swapped=false;
$j++;
for ($i=0;$i+$gap<$length;$i++) {
if ($array[$i]>$array[$i+$gap]) {
$tmp=$array[$i];
$array[$i]=$array[$i+$gap];
$array[$i+$gap]=$tmp;
$swapped=true;
}
}
}
return $array;
}
Bibliography:
Shell Sort algorithm – PHP implementation
Algorithm:
- Remove the element from the input array at position h+n.
- Compare the element form position h+n with element from position n and switch if is smaller
- Continue with until finish the array and change to next gap
Shell sort is based on bubble sort and insertion sort but change to step for compare two elements of array. Practically is a multi-pass algorithm (because there are more steps): each pass is an insertion sort of the sequences consisting of every h-th element for a fixed gap h (also known as the increment).
Performance is depending of gap sequence used for sorting. I used next sequence: 701,301,132,57,23,10,4,1. Like an observation all gap must finish in 1.
Performance:
- Worst case: depend on gap, no more than O(n2)
- Average case: depend on gap, no more than O(n2)
- Best case: depend on gap
PHP implementation (function from a larger sort Class):
/**Function for sorting an array with shell sort algorithm.
*
* @param array $array
* @return array
*/
public static function shellSort(array $array) {
$gaps=array(701,301,132,57,23,10,4,1);
$length=count($array);
$lgap=count($gaps);
for ($z=0;$z<$lgap;$z++) {
$gap=$gaps[$z];
for ($i=$gap;$i<$length;$i++) {
$element=$array[$i];
$j=$i;
while($j>=$gap && $array[$j-$gap]>$element) {
//move value to right and key to previous smaller index
$array[$j]=$array[$j-$gap];
$j=$j-$gap;
}
//put the element at index $j
$array[$j]=$element;
}
}
return $array;
}
Bibliography:
- Introduction to Algorithms – Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- Algorithms – Robert Sedgewick
- http://en.wikipedia.org/wiki/Shell_sort
Insertion Sort algorithm – PHP implementation
Algorithm:
- Remove the element from the input array.
- Check to the left where is correct position for this element and move all elements to right with one step if those are bigger than element
- Insert the element in correct position
Insertion sort is very similar to selection sort. As in selection sort, after k passes through the array, the first k elements are in sorted order. For selection sort these are the k smallest elements, while in insertion sort they are whatever the first k elements were in the unsorted array. Insertion sort’s advantage is that it only scans as many elements as needed to determine the correct location of the (k+1)st element, while selection sort must scan all remaining elements to find the absolute smallest element.
However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort; indeed, good quicksort implementations use insertion sort for arrays smaller than a certain threshold, also when arising as subproblems.
Performance:
- Worst case: O(n2)
- Average case: O(n2)
- Best case: O(n)
PHP implementation (function from a larger sort Class):
/**Function for sorting an array with insertion sort algorithm.
*
* @param array $array
* @return array
*/
public static function insertionSort(array $array) {
$length=count($array);
for ($i=1;$i<$length;$i++) {
$element=$array[$i];
$j=$i;
while($j>0 && $array[$j-1]>$element) {
//move value to right and key to previous smaller index
$array[$j]=$array[$j-1];
$j=$j-1;
}
//put the element at index $j
$array[$j]=$element;
}
return $array;
}
Bibliography:
- Introduction to Algorithms – Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- Algorithms – Robert Sedgewick
- http://en.wikipedia.org/wiki/Insertion_sort
Selection Sort algorithm – PHP implementation
Algorithm:
- Find the smallest element in array and swap it with element from first position.
- Repeat first step with second smallest element and swap with element from second position.
- Continue until array is sorted.
This is among the simplest of sorting method, and it will work very well for small files. Its running time is proportional with n2 (n is array length): the number of comparisons between array elements is about n2/2, since the outer loop (on i) is executed n times and the inner loop (on j) is executed about n/2 times on average.
Performance:
- Worst case: O(n2)
- Average case: O(n2)
- Best case: O(n2)
PHP implementation (function from a larger sort Class):
/**Function for sorting an array with selection sort algorithm.
*
* @param array $array
* @return array
*/
public static function selectionSort(array $array) {
for ($i=0;$i<count($array);$i++) {
$min=$i;
$length=count($array);
for ($j=$i+1;$j<$length;$j++) {
if ($array[$j]<$array[$min]) {
$min=$j;
}
}
$tmp=$array[$min];
$array[$min]=$array[$i];
$array[$i]=$tmp;
}
return $array;
}
Bibliography:
- Introduction to Algorithms – Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- Algorithms – Robert Sedgewick
- http://en.wikipedia.org/wiki/Selection_sort
Bubble Sort algorithm – PHP implementation
Algorithm:
- Compare each pair of adiacent elements from the beginning of an array and, if they are in reversed order, swap them.
- If at least one swap has be done repeat step 1.
Is one of the most inefficient algorithm.
Performance:
- Worst case: O(n2)
- Average case: O(n2)
- Best case: O(n)
PHP implementation:
/**Function for sorting an array with bubble sort algorithm.
*
* @param array $array
* @return array
*/
public static function bubbleSort(array $array) {
$swapped=true;
$j=0;
$length=count($array);
while($swapped) {
$swapped=false;
$j++;
$comp=$length-$j;
for ($i=0;$i<$comp;$i++) {
if ($array[$i]>$array[$i+1]) {
$tmp=$array[$i];
$array[$i]=$array[$i+1];
$array[$i+1]=$tmp;
$swapped=true;
}
}
}
return $array;
}
Bibliography:
- Introduction to Algorithms – Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- Algorithms – Robert Sedgewick
- http://en.wikipedia.org/wiki/Bubble_sort
Algorithms in PHP 