Home arrow PHP arrow Page 4 - Collections and Sorting Continued

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

Here are some lovely graphs borrowed from http://linux.wku.edu/~lamonml/algor/sort/sort.html. The first graph shows execution time, represented in seconds on the vertical axis and the number of items in a data set on the horizontal axis. The second graph shows execution time in tenths of a second. You can perhaps guess which sort of complexity is represented by each graph!

 

The n log n algorithms absolutely crush the quadratic algorithms in terms of speed.

Conclusion

In this article we have reviewed the primary sorting algorithms and their general properties. We have reviewed how quickly they complete relative to the size of the data set to be sorted. We have also discussed how to choose the appropriate algorithm. The metrics presented in this article were borrowed from http://linux.wku.edu/~lamonml/algor/sort/sort.html, who was kind enough to compile them, knowing that eventually I would need them-–so, thanks to wku.edu.

As I wrote this article, it occurred to me that we could go one step further and throw in an implementation of the Strategy design pattern using the contents of this article. We will create a SortStrategy class and create a method in the base Collection class to select a SortStrategy class based on the data it contains. Since we have reviewed the best and worst of our two classes of algorithms and know how complex (or simple) they are, we will pick the “best” from each class and go from there.



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