Sorting Algorithms and Their Run Times

[wisvuze]

Homework Statement

hi, I was asked to notice a pattern involving the run times of sorting algorithms.. however, the run time timer program I have keeps giving me different values for the same length lists :| will the pattern/formula be an approximation then? also, I read that the run time should follow n^2 or some kind of quadratic relation.. I just can't see it, the runtime values I'm getting are no way quadratic. could anybody help me?

thanks

Homework Equations

The Attempt at a Solution

here is my selection sort code , it is written in python:

def swapper(L, i):
    larger = i
    for e in range(i+1 , len(L)): 
        if L[e] > L[larger]:
            larger = e
            
    return larger    

def non_ascending(L):
    i = 0
    while i != len(L)-1:
        larger = swapper(L,i)
        L[i], L[larger] = L[larger], L[i]
        i += 1

 

[mgb_phys]

It's difficult to test because of things like caches.
You either need to do the run 100s of times an take an average
or you should analyse the algorithm to decide the big-O

 

[wisvuze]

It's difficult to test because of things like caches.
You either need to do the run 100s of times an take an average
or you should analyse the algorithm to decide the big-O

ah, thanks for the speedy reply. I was certain that something was off with my testing method. could you show me how (briefly at least?) I could analyze my algorithm to decide the big-O?

thanks a lot :)

 

[story645]

also, I read that the run time should follow n^2 or some kind of quadratic relation..

That's its bigO run time, which you get by taking the worst case time of your algorithm. The worst case time is when you have N (N>1) values, how long will it take to sort? This is figured out by counting your operations and adding them/multiplying them together.

Example:

while(i<N): #done N times
  k[i] = k[o] #assigned N times

the O(n) = n^2 because n assignemnts in n loops = n(n)=n*2

if your code is

while(i<N): # done N times
  k[i] = k[o] #N times
  l[i] = l[o] # N times

the O(n) = n^2 because n+n assignments in n loops = n(2n)=2n*2, but 2 (as are all constants) is negligible so O(n) = n^2