Skip to content

Instantly share code, notes, and snippets.

@Snugug
Forked from ircmaxell/in_place_quicksort.php
Created January 15, 2013 16:09
Show Gist options
  • Save Snugug/4539735 to your computer and use it in GitHub Desktop.
Save Snugug/4539735 to your computer and use it in GitHub Desktop.
<?php
function swap(array &$array, $k1, $k2) {
$temp = $array[$k1];
$array[$k1] = $array[$k2];
$array[$k2] = $temp;
}
function partition(array &$array, $left, $right, $pivot) {
$pValue = $array[$pivot];
swap($array, $right, $pivot);
$storeIdx = $left;
for ($i = $left; $i < $right; $i++) {
if ($array[$i] < $pValue) {
swap($array, $i, $storeIdx);
$storeIdx++;
}
}
swap($array, $storeIdx, $right);
return $storeIdx;
}
function quicksort2(array &$array, $left = null, $right = null) {
if (is_null($left) || is_null($right)) {
$left = 0;
$right = count($array) - 1;
}
if ($left < $right) {
$pivot = $left + floor(($right - $left) / 2);
$pivot = partition($array, $left, $right, $pivot);
quicksort2($array, $left, $pivot - 1);
quicksort2($array, $pivot + 1, $right);
}
}
<?php
function quicksort(array $array) {
$count = count($array);
if ($count <= 1) {
return $array;
}
$left = array();
$right = array();
$key = floor($count / 2);
$value = $array[$key];
for ($i = 0; $i < $count; $i++) {
if ($key != $i) {
if ($array[$i] < $value) {
$left[] = $array[$i];
} else {
$right[] = $array[$i];
}
}
}
return array_merge(quicksort($left), array($value), quicksort($right));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment