Home arrow PHP arrow Page 2 - Collections and Sorting Continued

Sort Algorithms of Quadratic Complexity - PHP

In the first part of this series we implemented a basic sortable collection class. We used a Bubble Sort algorithm to order the elements in the collection, which came with a disclaimer regarding what a slow sort it is. This article will examine the primary sorting algorithms with code examples, and some empirical data regarding how they perform in relation to one another, as well as the size of the data set in question.

TABLE OF CONTENTS:
  1. Collections and Sorting Continued
  2. Sort Algorithms of Quadratic Complexity
  3. Sort Algorithms of n log n Complexity
  4. Metrics
By: David Fells
Rating: starstarstarstarstar / 7
April 04, 2006

print this article
SEARCH DEV SHED

TOOLS YOU CAN USE

advertisement

Bubble sort, insertion sort, selection sort and shell sort are algorithms of quadratic complexity. In the first part of this article, we implemented the bubble sort with the following code in the Sort() method from our People Collection class:

        public function Sort()
  {
        for ($i = $this->data->count() - 1; $i >= 0; $i--)
        {
              $flipped = false;
              for ($j = 0; $j < $i; $j++)
              {
                    if (strcmp($this->data[$j]->GetSortKey(), 
                          $this->data[$j + 1]->GetSortKey()) > 0)
                    { 
                          $tmp = $this->data[$j];
                          $this->data->offsetSet($j, $this->data
[$j + 1]);
                          $this->data->offsetSet($j + 1, $tmp);
                          $flipped = true;
                    }
              }
              if (!$flipped)
                    return;
        }
  }

Very simple and straightforward. I will not explain the code in the algorithms in this article, I leave it to you the reader as an exercise. You will benefit from learning how these algorithms work if you do not know already! Letís have a look at the code for an insertion sort:

        public function InsertionSort()
  {
       for ($i = 1; $i < $this->data->count(); $i++)
        {
              $j = $i;
              $tmp = $this->data[$i];
              while (($j > 0) && (
                    strcmp($this->data[$j - 1]->GetSortKey(), 
                          $tmp->GetSortKey()) > 0)
                    )
              {
                    $this->data->offsetSet($j, $this->data[$j -
1]);
                    $j--;
              }
              $this->data->offsetSet($j, $tmp);
        }
  }

Now a selection sort:

        public function SelectionSort()
  {
        for ($i = 0; $i < $this->data->count(); $i++)
        {
              $min = $i;
              $j = 0;
               
              for ($j = $i + 1; $j < $this->data->count(); $j++)
              {
                    if (strcmp($this->data[$j]->GetSortKey(), 
                          $this->data[$min]->GetSortKey()) < 0)
                    {
                          $min = $j;
                    }
              }                 

              $tmp = $this->data[$min];
              $this->data->offsetSet($min, $this->data[$i]);
              $this->data->offsetSet($i, $tmp);
        }
  }

And for the last quadratic complexity sort, the shell sort:

        public function ShellSort()
  {
        $increment = 3;                 

        while ($increment > 0)
        {
              for ($i = 0; $i < $this->data->count(); $i++)
              {
                    $tmp = $this->data[$i];
                    $j = $i;                       

                    while ($j >= $increment)
                    {
                          if ($this->data[$j - $increment])
                          {
                                if (strcmp($this->data[$j -
$increment]->GetSortKey(), 
                                      $tmp->GetSortKey()) > 0)
                                {
                                      $this->data->offsetSet($j, 
                                            $this->data[$j -
$increment]);
                                      $j -= $increment;
                                }
                          }
                    }
                    $this->data->offsetSet($j, $tmp);
              }
               
              if ($increment % 2 != 0)
                    $increment = ($increment - 1) / 2;
              elseif ($increment == 1)
                    $increment = 0;
              else 
                    $increment = 1;
        }
 }

All of these sorts are slow. The shell sort is dramatically faster than the rest, but still slow relative to the algorithms. Before we delve into performance, though, I want to show the code for the n log n complexity algorithms.



 
 
>>> More PHP Articles          >>> More By David Fells
 

blog comments powered by Disqus
escort Bursa Bursa escort Antalya eskort
   

PHP ARTICLES

- Hackers Compromise PHP Sites to Launch Attac...
- Red Hat, Zend Form OpenShift PaaS Alliance
- PHP IDE News
- BCD, Zend Extend PHP Partnership
- PHP FAQ Highlight
- PHP Creator Didn't Set Out to Create a Langu...
- PHP Trends Revealed in Zend Study
- PHP: Best Methods for Running Scheduled Jobs
- PHP Array Functions: array_change_key_case
- PHP array_combine Function
- PHP array_chunk Function
- PHP Closures as View Helpers: Lazy-Loading F...
- Using PHP Closures as View Helpers
- PHP File and Operating System Program Execut...
- PHP: Effects of Wrapping Code in Class Const...

Developer Shed Affiliates

 


Dev Shed Tutorial Topics: