Home arrow PHP arrow Collections and Sorting Continued

Collections and Sorting Continued

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

We are going to implement the following sort algorithms for our tests:

  1. Bubble Sort (Implemented in part one)
  2. Heap Sort
  3. Insertion Sort
  4. Merge Sort
  5. Quick Sort
  6. Selection Sort
  7. Shell Sort

We will also create a function to fill up our collection with random data in order to test the sort algorithms with a sufficiently large data set. The sort algorithms listed above are the ones that every computer science student learns in college and are the primary sort algorithms found in real-world applications. Before we actually write code to implement them, let’s discuss a few basic facts.

These algorithms can be grouped into two categories based on their algorithmic complexity:

  1. Algorithms with O(n2) complexity, also called quadratic complexity – bubble, insertion, selection and shell sorts. Algorithms of quadratic complexity are agonizingly slow with large data sets. A data set with 10,000 elements takes 10,000 times longer to process than a data set with 1,000 elements, and a set with 1,000 elements takes 1,000 times longer than a set with 100 elements, and so on.
  2. Algorithms with O(n log n) complexity, also called n log n complexity – heap, merge and quick sorts. n log n complexity is as much better than linear complexity as quadratic is worse. An algorithm completing in constant time would be preferable, but in the case of sorting this is accepted as an impossibility. An example of n log n complexity is the number of bits required to store an integer.

As you may have guessed, n log n complexity implies an inherently faster algorithm than one of quadratic complexity; the tradeoff is in the code itself. Faster algorithms in the case of sorting involve recursion, multiple arrays, and complicated data structures, but they run circles around their slower cousins. Choosing the proper sort algorithm is a subject unto itself, but in this article we will cover the general factors to be considered when choosing a sort algorithm.

First though, we need to whip up a touch of code to create a big data set. In the example below, set $numItems to however many data values you want in the collection.

function makeWord()
{
      $letters = array('a', 'b', 'c', 'd', 'e', 
            'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 
            'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 
            'v', 'w', 'x', 'y', 'z');           

      $return = '';
      for ($i = 0; $i < 20; $i++)
      {
            $return .= $letters[rand(0, count($letters) - 1)];
      }     

      return $return;
}
$people = new People();
$numItems = 10000;
for ($i = 0; $i < $numItems; $i++)
      $people->Append(new Person(makeWord()));



 
 
>>> 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: