CM10135 / Programming II:   Lecture 5

Yet More on Algorithms and Complexity:

The Complexity of Various Sort Algorithms


I. Criteria for Evaluating an Algorithm, Re-revisited 

  1. What do you need to know about algorithms and complexity?
    1. Worst case,
      1. If everything is organized in the worst possible way, how long will it take?
    2. Best case,
      1. If you are really lucky, what's the fastest it could run?
    3. Average or expected case.
      1. What is the most probable situation?
  2. Big O notation should be used to give a boundary for the worst case.
  3. Notes from Dr. Paddon's old lectures say "Average case analysis is mathematically much harder to perform, and for many algorithms is not known."
  4. One practical way to determine average case is with a stopwatch (well, anyway, to run statistics!)
  5. Here's some folks who used a stopwatch on the sorting algorithms.
    1. Notice they get more precise results than we'll get below.
    2. But notice also the difference between O(n2) and O(nlogn) matters a lot more!
  6. Things to remember about big O values:
    1. Since it an upper bound on running time, performance could be much better.
    2. The input that causes worst case performance could be very rare --- and it might be recognizable or avoidable.
    3. You don't know what the constants are ---
      1. May be very large.
      2. Even a constant of 2 matters a lot if your operation is going to take 3 years (e.g. database conversions.)

II. How Bad is Bad?

Another table shamelessly cribbed from Gerald Kruse's page on Algorithm Efficiency.

Table of growth rates

Linear
N

logarithmic
log2N

n*log2N

quadratic
N2

cubic
N3

exponential
2N

exponential
3N

factorial
N!

1

0

0

1

1

2

1

2

1

2

4

8

4

2

4

2

8

16

64

16

81

24

8

3

24

64

512

256

6561

40320

16

4

64

256

4096

65,536 

43,046,721

2.09E+013

32

5

160

1024

322,768

4,294,967,296 

…1.85E+15

2.63E+035

64

6

384

4096

262,144

1.84E+17
(Note 1) 

…3.43E+30

1.27E+089

128

7

896

16,384

2,097,152

3.4E+38
(Note 2) 

…1.18E+61

3.86E+215

256

8

2048 

65,536

1,677,216

1.16E+77 ??? 

…1.39E+122

Find other calculator

Note 1: The value here is approximately the number of machine instructions executed by a 1 gigaflop computer in 5000 years, or 5 years on a current supercomputer (teraflop computer)

Note 2: The value here is about 500 billion times the age of the universe in nanoseconds, assuming a universe age of 20 billion years.
  1. Some people think that it doesn't really matter how complex an algorithm is because computers are getting so much faster.
  2. They are wrong.  It matters.
  3. See the table above --- not going to get much done in less than a nanosecond!
  4. Let's say that for each type of problem space, there's a largest size N for how long we can wait around for our program to finish.
    1. The time we are waiting is always the same, but the size is different because the complexity is different.
    2. N1-N5 
  5. This table (from Dr. Paddon's notes last year) tells us how much faster computers will help us.


    log2n
    n
    nlog2n
    n2
    2n
    Current Computers
    N1
    N2
    N3
    N4
    N5
    Ten times faster
    N1 x 30
    N2 x 10
    N3 x 3
    N4 x 3
    N5 + 3
    Thousand times faster
    N1 x 9,000
    N2 x 1,000
    N3 x 111
    N4 x 31
    N5 + 10
    Million times faster
    N1 x 19E+6
    N2 x 1E+6
    N3 x 5,360
    N4 x 1,000
    N5 + 20

  6. You can see that there are no big wins once you have an exponential algorithm!

III. The Complexity of Our Sort Algorithms

Fore the algorithms you've already seen, I've linked to the pseudo code from Lecture 2.  You may want to open the links in another browser window (use the right mouse button) so you can look at the analysis & the algorithm at the same time.

i) `Real' Selection Sort

  1. Most expensive / basic operation is the comparison, if (sorta[searchIx] < min).
  2. How often do we do it?
    1. Amounts to: 
      for n do
          for 1, 2, 3, 4...n-1 do  (average value (n-1)/2)
    2. This is equiv to the arithematic series (1+2+3+4+...n-1) == n*(n+1)/2 
    3. n*(n+1)/2 = 1/2*n2 + 1/2*n  which means its O(n2)  -- n2 dominates
  3. Caveat: the equation of that arithmatic series might be wrong --- I'm no mathematician, and the notes & web pages I've found don't agree with each other!  But it's something quite like that...  Anyway, that's what O notation is for, so we know what's really important!

ii) Easy Selection Sort

  1. Remember the one I did with two arrays?
  2. How often do we do if (messy[searchIx] < min)?
    1. Amounts to: 
      for n do
          for n do
    2. n2 which means its O(n2)
  3. So no difference at least in O notation!  (though see the charts on this page I mentioned earlier --- these things do matter a little.)

iii) Insertion Sort

  1. How often do we do the comparison? (sorta[searchingIx] < currentItem)
  2. In the worst case, started in reverse order, have to move every item past all the sorted items.
    1. for n do
          for 1, 2, 3, 4...n-1 do...
    2. Look familiar?  Also O(n2)
  3. So again, no difference at least in O notation!  
  4. Insertion & Selection sort are said to be algorithms in the same class, because effectively they take the same time.
  5. Here is my favorite sort algorithm in O(n2) (yes, I have a favorite sort algorithm. Yes, I'm a nerd! Nerd Pride)

iv) Bubble Sort

  1. What you've hopefully noticed is that all of these sorts have an outer for loop as long as the array, and an inner loop that's almost as long as the array, so I'll just call the indecies "out" and "in".
  2. In this one, you just swap / "bubble" any large numbers up out of the way!
    array int sorta;  // this comes from somewhere in a messy state
    int temp; // for the swap
    int outIx, inIx; // these are indecies

    // outer loop over the sorted array -- when everything's sorted we're done
    for (outIx gets the values sorta.length down to 1) {
    // from the beginning of the list to the end of the unsorted bit
    for(inIx = 1; inIx < outIx-1; inIx++) {
    // If adjacent items are out of order, swap them!
    if (sorta[inIx-1]>sorta[inIx]) {
    temp = sorta[inIx-1];
    sorta[inIx-1] = sorta[inIx];
    sorta[inIx] = temp;
    }
    }
  3. How simple is that?  But we may as well do it this way since they're all O(n2) anyway.
  4. Here's a drawing of what happens (I did one in class on the board too.)  Basically on each pass, the largest number will get carried up to the top of the unsorted area.
  5. Don't forget (this page is linked from the class page) that John Morris has sorting movies.

v) Quick Sort

  1. Quick sort is different (hence its name.)
  2. Actually, it's worst case (array is already sorted backwards) is the same as the others.
  3. But, in the best case (random distribution), the pivot point will be at the middle, so the array keeps getting sliced in half.
    1. If this is true, you will have log2n times that you slice the array up,
    2. For each time you do the slicing, you do n comparisons in total.
    3. So best case is exactly O(n log n).
    4. Apparently, the average case is 38% worse than this.
  4. My favorite O(n log n) sort is called Merge Sort.  (Yes, I have a favorite O(n log n) sort...)

vi) Merge Sort

  1. Split the array in halves recursively until each half has only one element.
  2. You can now assume the sub lists are sorted (1 number can't be unsorted.)
  3. Merge the two halves together by interleaving them:
    1. Run two indecies, one from the beginning of each array.
    2. Which ever index points at the smallest number, take that number as the next in your merged array.
  4. This is guaranteed to be O(n log n), since you are certain to split things correctly.
  5. But empirically it's usually slower than quick sort --- probably because it uses twice as much memory.

IV. What have we learned? 

  1. Complexity matters (again.)
  2. The sorts you learned come in two different classes, O(n2) and O(n log n).
  3. A couple of easy sorts in each of these classes.
  4. Hopefully getting an intuition about how to recognize a log n algorithm (or algorithm component.)
  5. This strategy of chopping problems in half recursively to get a log n algorithm is often called divide and conquer.
  6. It's a good strategy!

page author: Joanna Bryson
22 Feb 2005