python - Quicksort sorts larger numbers faster? -

i messing around python trying practice sorting algorithms , found out interesting.

i have 3 different pieces of data:

• x = number of numbers sort
• y = range numbers in (all random generated ints)
• z = total time taken sort

when:
x = 100000 and
y = (0,100000) then
z = 0.94182094911 sec

when:
x = 100000 and
y = (0,100) then
z = 12.4218382537 sec

when:
x = 100000 and
y = (0,10) then
z = 110.267447809 sec

any ideas?

code:

import time import random import sys  #-----function definitions  def quicksort(array): #random pivot location quicksort. uses memory.     smaller = []     greater = []     if len(array) <= 1:         return array     pivotval = array[random.randint(0, len(array)-1)]     array.remove(pivotval)     items in array:         if items <= pivotval:             smaller.append(items)         else:             greater.append(items)     return concat(quicksort(smaller), pivotval, quicksort(greater))  def concat(before, pivot, after):     new = []     items in before:         new.append(items)     new.append(pivot)     things in after:         new.append(things)     return new  #-----variable definitions list = [] iter = 0 sys.setrecursionlimit(20000) start = time.clock() #start clock  #-----generate list of numbers sort while(iter < 100000):     list.append(random.randint(0,10))  #modify change sorting speed     iter = iter + 1 timetogenerate = time.clock() - start #current timer - last timer snapshot  #-----sort list of numbers list = quicksort(list) timetosort = time.clock() - timetogenerate #current timer - last timer snapshot  #-----write list of numbers file = open("c:\output.txt", 'w') items in list:     file.write(str(items))     file.write("\n") file.close() timetowrite = time.clock() - timetosort #current timer - last timer snapshot  #-----print info print "time start: " + str(start) print "time generate: " + str(timetogenerate) print "time sort: " + str(timetosort) print "time write: " + str(timetowrite) totaltime = timetogenerate + timetosort + start print "total time: " + str(totaltime) 

-------------------revised new code----------------------------

def quicksort(array): #random pivot location quicksort. uses memory.     smaller = []     greater = []     equal = []     if len(array) <= 1:         return array     pivotval = array[random.randint(0, len(array)-1)]     array.remove(pivotval)     equal.append(pivotval)     items in array:         if items < pivotval:             smaller.append(items)         elif items > pivotval:             greater.append(items)         else:             equal.append(items)     return concat(quicksort(smaller), equal, quicksort(greater))  def concat(before, equal, after):     new = []     items in before:         new.append(items)     items in equal:         new.append(items)     items in after:         new.append(items)     return new 

i think has choice of pivot. depending on how partition step works, if have lot of duplicate values, algorithm can degenerate quadratic behavior when confronted many duplicates. example, suppose you're trying quicksort stream:

 [0 0 0 0 0 0 0 0 0 0 0 0 0] 

if aren't careful how partitioning step, can degenerate quickly. example, suppose pick pivot first 0, leaving array

 [0 0 0 0 0 0 0 0 0 0 0 0] 

to partition. algorithm might smaller values array

 [0 0 0 0 0 0 0 0 0 0 0 0] 

and larger values array

 [] 

this case causes quicksort degenerate o(n²), since each recursive call shrinking size of input 1 (namely, pulling off pivot element).

i noticed in code, partitioning step indeed this:

for items in array:     if items <= pivotval:         smaller.append(items)     else:         greater.append(items) 

given stream that's whole bunch of copies of same element, put of them 1 array recursively sort.

of course, seems ridiculous case - how @ connected reducing number of values in array? - come when you're sorting lots of elements aren't distinct. in particular, after few passes of partitioning, you're group equal elements, bring case.

for discussion of how prevent happening, there's great talk by bob sedgewick , jon bentley how modify partition step work when in presence of duplicate elements. it's connected dijkstra's dutch national flag problem, , solutions clever.

one option works partition input 3 groups - less, equal, , greater. once you've broken input way, need sort less , greater groups; equal groups sorted. above link talk shows how more or less in-place, since you're using out-of-place quicksort fix should easy. here's attempt @ it:

for items in array:     if items < pivotval:         smaller.append(items)     elif items == pivotval:         equal.append(items)     else:         greater.append(items) 

i've never written line of python in life, btw, may totally illegal syntax. hope idea clear! :-)