Created
December 24, 2013 21:45
-
-
Save fintara/8118093 to your computer and use it in GitHub Desktop.
QuickSort realized in PHP.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
namespace Sort; | |
class QuickSorter { | |
private $_array; | |
public function __construct(array $array) { | |
$this->_array = $array; | |
} | |
public function sort() { | |
$this->quicksort(0, count($this->_array) - 1); | |
} | |
public function getArray() { | |
return $this->_array; | |
} | |
public function printArray() { | |
foreach($this->_array as $x) { | |
echo "{$x} "; | |
} | |
echo "\n"; | |
} | |
private function swap($index, $with) { | |
$tmp = $this->_array[$index]; | |
$this->_array[$index] = $this->_array[$with]; | |
$this->_array[$with] = $tmp; | |
} | |
private function split($left, $right, $pivotIndex) { | |
$pivotValue = $this->_array[$pivotIndex]; | |
$storeIndex = $left; | |
$this->swap($pivotIndex, $right); | |
for($i = $left; $i < $right; $i++) { | |
if($this->_array[$i] <= $pivotValue) { | |
$this->swap($i, $storeIndex); | |
$storeIndex++; | |
} | |
} | |
$this->swap($storeIndex, $right); | |
return $storeIndex; | |
} | |
private function quicksort($left, $right) { | |
if($left < $right) { | |
$pivotIndex = (int)($left + ($right - $left) / 2); | |
$pivotNewIndex = $this->split($left, $right, $pivotIndex); | |
$this->quicksort($left, $pivotNewIndex - 1); | |
$this->quicksort($pivotNewIndex + 1, $right); | |
} | |
} | |
} | |
$sorter = new QuickSorter([-16, -9, 47, 25, -39, -43, 32, -23, -12, -50, -23, 0, 42, -40, 6, 49, 9, 10, -7, -20]); | |
$sorter->printArray(); | |
$sorter->sort(); | |
$sorter->printArray(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment