Sort Algorithms of Quadratic Complexity - PHP

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.