CODEWITHSUNDEEP
python
joe van horn
joe van horn

Reputation: 61

Timing Sort functions

import time

def timeSort(sortfn, L):
   t1 = time.time()
   sortfn(L)
   t2 = time.time()
   return (t2 - t1)

# try, e.g.,
# l = mixup(list(range(4000)))
# timeAllSorts(l)
def timeAllSorts(L):

    Lcopy = L[:]
    sTime = timeSort(selectionSort, Lcopy)
    Lcopy = L[:]
    iTime = timeSort(insertionSort, Lcopy)
    Lcopy = L[:]
    mTime = timeSort(mergeSort, Lcopy)
    Lcopy = L[:]
    biTime = timeSort(builtinSort, Lcopy)
    Lcopy = L[:]
    qTime = timeSort(quicksort, Lcopy)

   print("{}\t sel: {:.2f}\t ins: {:.2f}\t merge: {:.2f}\t builtin: {:.2f}\t quick:{:.2f}".format(len(L), sTime, iTime, mTime, biTime,qTime))

I have multiple sorting functions, I could not fit all them in the code but for example my quicksort():

import random
def quicksort(L):
    if len(L)<2: return L
    pivot_element = random.choice(L)
    small = [i for i in L if i< pivot_element]
    medium = [i for i in L if i==pivot_element]
    large = [i for i in L if i> pivot_element]
    return quicksort(small) + medium + quicksort(large)

When I run the timeAllSorts function it returns a runtime of 0.00 for every function and I am not sure why this happens. Maybe with my print statement?

>>> timeAllSorts([12,5,13,8,9,65])
6    sel: 0.00   ins: 0.00   merge: 0.00     builtin: 0.00   quick:0.00

Upvotes: 0

Views: 178

Answers (2)

MTset
MTset

Reputation: 90

As user2357112 said, you have specified quick:{:.2f}, which is insufficient resolution to show anything but 0. The first significant digit occurs only after four zeros (on my machine). So try something like quick:{:.10f}.

Upvotes: 0

user764357
user764357

Reputation:

Sorting 5 integers will take no time for even the worst sorting algorithm. To properly test you will need several hundred or even thousand items.

For example, testing with 8000 items shows that the sorted inbuilt is still "0 seconds", while quicksort is "0.05" seconds

import time

def timeSort(sortfn, L):
   t1 = time.time()
   sortfn(L)
   t2 = time.time()
   print t2-t1
   return (t2 - t1)

# try, e.g.,
# l = mixup(list(range(4000)))
# timeAllSorts(l)

import random
def quicksort(L):
    if len(L)<2: return L
    pivot_element = random.choice(L)
    small = [i for i in L if i< pivot_element]
    medium = [i for i in L if i==pivot_element]
    large = [i for i in L if i> pivot_element]
    return quicksort(small) + medium + quicksort(large)

def timeAllSorts(L):

    Lcopy = L[:]
    qTime = timeSort(quicksort, Lcopy)
    sTime = timeSort(sorted, Lcopy)

    print("{}\t sel:{:.2f} quick:{:.2f}".format(len(L),sTime, qTime))

l = list(range(8000,1,-1))
timeAllSorts(l)

7999   sel:0.00 quick:0.05

Upvotes: 2

Related Questions