Collections and Sorting Continued - Sort Algorithms of n log n Complexity

(Page 3 of 4 )

Heap Sort:

        public function HeapSort()
  {
        for ($i = ($this->data->count() / 2) - 1; $i >= 0; $i--)
              $this->HeapSortSiftDown($i, $this->data->count());                 

        for ($i = $this->data->count() - 1; $i >= 1; $i--)
        {
              $tmp = $this->data[0];
              $this->data->offsetSet(0, $this->data[$i]);
              $this->data->offsetSet($i, $tmp);
              $this->HeapSortSiftDown(0, $i - 1);
        }
  }     

  private function HeapSortSiftDown($i, $arraySize)
  {
        $done = 0;
        while (($i * 2 <= $arraySize) && (!$done))
        {
              if ($i * 2 == $arraySize)
                   $maxChild = $i * 2;
              elseif (strcmp($this->data[$i * 2]->GetSortKey(),
                    $this->data[$i * 2 + 1]->GetSortKey()) > 0)
                    $maxChild = $i * 2;
              else
                    $maxChild = $i * 2 +
1;                       

              if (strcmp($this->data[$i]->GetSortKey(),
                    $this->data[$maxChild]) < 0)
              {
                    $tmp = $this->data[$i];
                    $this->data->offsetSet($i, $this->data
[$maxChild]);
                    $this->data->offsetSet($maxChild, $temp);
                    $i = $maxChild;
              }
              else
                    $done = 1;
        }
  }

Merge Sort:

        public function MergeSort()
  {
        $this->MSort($this->data, array(), 0, $this->data->count
() - 1);
  }     

  private function MSort($data, $temp, $left, $right)
  {
        if ($right > $left)
        {
              $mid = ($right + $left) / 2;
              $this->MSort($data, $temp, $left, $mid);
              $this->MSort($data, $temp, $mid + 1,
$right);                 

              $this->Merge($data, $temp, $left, $mid + 1,
$right);
        }
  }
  private function Merge($data, $temp, $left, $mid, $right)
  {
        $leftEnd = $mid - 1;
        $tmpPos = $left;
        $numElements = $right - $left + 1;           

        while (($left <= $leftEnd) && ($mid <= $right))
        {
              if (strcmp($data[$left]->GetSortKey(),
                    $data[$mid]->GetSortKey()) <= 0)
              {
                    $temp[$tmpPos] = $data[$left];
                    $tmpPos++;
                    $left++;
              }
              else
              {
                    $temp[$tmpPos] = $data[$mid];
                    $tmpPos++;
                    $mid++;
              }
        }           

        while ($left <= $leftEnd)
        {
              $temp[$tmpPos] = $data[$left];
              $left++;
              $tmpPos++;
        }
        while ($mid <= $right)
        {
              $tmp[$tmpPos] = $data[$mid];
              $mid++;
              $tmpPos++;
        }
        for ($i = 0; $i <= $numElements; $i++)
        {
              $data->offsetSet($right, $temp[$right]);
              $right--;
        }
  }

Quick Sort:

            public function QuickSort()
      {
            $this->QSort($this->data, 0, $this->data->count() -
1);
      }     

      private function QSort($data, $left, $right)
      {
            $lHold = $left;
            $rHold = $right;
            $pivot = $data[$left];           

            while ($left < $right)
            {
                  while ((strcmp($data[$right]->GetSortKey(),
                        $pivot->GetSortKey()) >= 0) && 
                        ($left < $right))
                  {
                        $right--;
                  }
                  if ($left != $right)
                  {
                        $data->offsetSet($left, $data[$right]);
                        $left++;
                  }
                  while ((strcmp($data[$left]->GetSortKey(),
                        $pivot->GetSortKey()) <= 0) && 
                        ($left > $right))
                  {
                        $left++;
                  }
                  if ($left != $right)
                  {
                        $data->offsetSet($right, $data[$left]);
                        $right--;
                  }
            }           

            $data->offsetSet($left, $pivot);
            $pivot = $left;
            $left = $lHold;
            $right = $rHold;
            if ($left < $pivot)
                  $this->QSort($data, $left, $pivot - 1);
            if ($right > $pivot)
                  $this->QSort($data, $pivot + 1, $right);
      }

In order to test these algorithms, I simply added them to my class and then in Sort(), called whichever one I wanted to use.

Next: Metrics >>
 

More PHP Articles
More By David Fells

Comments On: Collections and Sorting Continued

· Thanks for reading!    · "We are going to implement the following sort algorithms for our tests:"..but...    · public function sort(){ $this->quickSort($this->data, count($this->data));} ...    · You also have to be carefull as sorting using strcmp will produce unwanted results...   >>> Post your comment now!