Sorting algorithms

Sample implementations of quicksort and mergesort with PHP. It does not make any sense to use them, but they are probably usefull for understanding how these algorithms work. Download: sort.php (2.15 kB)

<?php // Test sorting algorithms $array = array( 4, 2, 54, 23, 43 , 7, 12, 2348, 23, 343, 43 ); var_dump( merge_sort( $array ) ); var_dump( quick_sort( $array ) ); /** * Quick sort * * Sorts an array using the quick sort algorithm. * * http://en.wikipedia.org/wiki/Quicksort * * @param array $array * @return array */ function quick_sort( array $array ) { // Nothing to sort, when only one element left if ( count( $array ) <= 1 ) { return $array; } // Selecting pivotelement - first element for example $pivot = reset($array); // Split array into three parts // - Same // - Larger // - Smaller $same = array(); $larger = array(); $smaller = array(); foreach ( $array as $value ) { if ( $value < $pivot ) { $smaller[] = $value; } elseif ( $value == $pivot ) { $same[] = $value; } else { $larger[] = $value; } } // Merge recursive calls of splitted arrays return array_merge( quick_sort( $smaller ), $same, quick_sort( $larger ) ); } /** * Merge to arrays respecting the order of the elements. * * @param array $array1 * @param array $array2 * @return array */ function merge( array $array1, array $array2 ) { // Return one array, if the other one is empty if ( count( $array1 ) == 0 ) return $array2; if ( count( $array2 ) == 0 ) return $array1; // Initialize counters with 0 $i = 0; $j = 0; $array = array(); // Fill up array with elements from both subarrays while ( ( $i < count( $array1 ) ) && ( $j < count( $array2 ) ) ) { if ( $array1[$i] < $array2[$j] ) { $array[] = $array1[$i++]; } else { $array[] = $array2[$j++]; } } // Fillup with elements which lefted in one of the arrays return array_merge( $array, array_slice( $array1, $i ), array_slice( $array2, $j ) ); } /** * Merge sort * * Sort an array using the merge sort algorithm. * * http://en.wikipedia.org/wiki/Merge_sort * * @param array $array * @return array */ function merge_sort( array $array ) { // Nothing to sort, when only one element left if ( count( $array ) <= 1 ) { return $array; } // Split up in the middle of the array $middle = floor( count( $array ) / 2 ); $array_left = array_slice( $array, 0, $middle ); $array_right = array_slice( $array, $middle ); // Split arays until only arrays with only one element left, merge then return merge( merge_sort( $array_left ), merge_sort( $array_right ) ); }