Разминка для мозга: Ручная сортировка массивов Quicksort / Быстрая сортировка на php.

29.05.2017 14:33:43

Набросок простого алгоритма для сортировки элементов массива методом Quicksort / Быстрая сортировка.

test1.php (Download)

 <?

  require_once('class.qsort.php');
  
  
  $aIn = array();
  for($i = 0; $i < 100; $i++)
  {
    $aIn[] = rand(-100, 100);
  }
  
  
  echo '<pre>';
    print_r($aIn);
  echo '</pre><hr/>';
  
  
  $oQsort = new cQsort();  
  $aIn = $oQsort->go($aIn);
  
  echo '<pre>';
    print_r($aIn);
  echo '</pre><hr/>';

class.qsort.php (Download)

 <?

  class cQsort
  {
    protected $_aIn			= array();
    
    function __construct() 
    {
      
    }

    protected function _sort($iLeft, $iRight)
    {
      //Вычисляем 'центр', на который будем опираться. Берем значение центральной ячейки массива.
      $elCenter = $this->_aIn[($iLeft + $iRight) / 2];
      
      $l = $iLeft;
      $r = $iRight;
      
      do
      {

        // Ищем значения меньше 'центра'
        while ($this->_aIn[$l] < $elCenter) {
          $l++;
        }

        // Ищем значения больше 'центра'
        while ($this->_aIn[$r] > $elCenter) {
          $r--;
        }

        // Проверяем, есть ли смысл менять местами
        if ($l <= $r)
        {

          // меняем ячейки друг с другом.
          list($this->_aIn[$r], $this->_aIn[$l]) = array($this->_aIn[$l], $this->_aIn[$r]);

          // И переводим счетчики на следующий элементы
          $l++;
          $r--;
        }

	  }
	  while($l <= $r);

      // Если не достигои правого края
	  if ($l < $iRight)
	  {
        // Передаем текущие начало и конец
	    $this->_sort($l, $iRight);
	  }

      // Если не достигои левого края
	  if ($r > $iLeft)
	  {
        // Передаем начало и текущий конец
	    $this->_sort($iLeft, $r);
	  }


	}

    public function go(&$aIn)
    {
      $this->_aIn = $aIn;
      
      $this->_sort(0, count($this->_aIn) -1);
      
      return $this->_aIn;
	}
  }


Категории: PHP, Алгоритмы
Пометки: Из старых тестов. array sort Quicksort / Быстрая сортировка
Яндекс.Метрика