Collections and Sorting Continued - Sort Algorithms of Quadratic Complexity

(Page 2 of 4 )

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.

Next: Sort Algorithms of n log n Complexity >>
 

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!