Permalink
Find file
Fetching contributors…
Cannot retrieve contributors at this time
76 lines (71 sloc) 3.46 KB

qsort ala python

original source modified from this [stackoverflow question](http://stackoverflow.com/questions/4322823/how-to-make-this-naive-python-implement-of-quicksort-more-pythonic) thanks Frankie, I'm learning from your learning

in case your curious here's it's execution time of a million sorts with 0.7.1

Mark-Essels-iMac:py-util messel$ python qsort.py
[0, 2, 4, 4.2999999999999998, 5.5, 8, 9, 11.6, 77.400000000000006, 112] 0.028202
[0, 2, 4, 4.2999999999999998, 5.5, 8, 9, 11.6, 77.400000000000006, 112] 2.341727
[0, 2, 4, 4.2999999999999998, 5.5, 8, 9, 11.6, 77.400000000000006, 112] 4.670012
[0, 2, 4, 4.2999999999999998, 5.5, 8, 9, 11.6, 77.400000000000006, 112] 7.012248
[0, 2, 4, 4.2999999999999998, 5.5, 8, 9, 11.6, 77.400000000000006, 112] 9.346553
[0, 2, 4, 4.2999999999999998, 5.5, 8, 9, 11.6, 77.400000000000006, 112] 11.666572
[0, 2, 4, 4.2999999999999998, 5.5, 8, 9, 11.6, 77.400000000000006, 112] 13.997745
[0, 2, 4, 4.2999999999999998, 5.5, 8, 9, 11.6, 77.400000000000006, 112] 16.314619
[0, 2, 4, 4.2999999999999998, 5.5, 8, 9, 11.6, 77.400000000000006, 112] 18.643811
[0, 2, 4, 4.2999999999999998, 5.5, 8, 9, 11.6, 77.400000000000006, 112] 20.968307

with pypy 1.5 alpha

Mark-Essels-iMac:py-qsort messel$ pypy qsort.py
[0, 2, 4, 4.3, 5.5, 8, 9, 11.6, 77.4, 112] 0.000207
[0, 2, 4, 4.3, 5.5, 8, 9, 11.6, 77.4, 112] 0.436853
[0, 2, 4, 4.3, 5.5, 8, 9, 11.6, 77.4, 112] 0.775002
[0, 2, 4, 4.3, 5.5, 8, 9, 11.6, 77.4, 112] 1.108878
[0, 2, 4, 4.3, 5.5, 8, 9, 11.6, 77.4, 112] 1.449188
[0, 2, 4, 4.3, 5.5, 8, 9, 11.6, 77.4, 112] 1.783163
[0, 2, 4, 4.3, 5.5, 8, 9, 11.6, 77.4, 112] 2.12146
[0, 2, 4, 4.3, 5.5, 8, 9, 11.6, 77.4, 112] 2.453842
[0, 2, 4, 4.3, 5.5, 8, 9, 11.6, 77.4, 112] 2.786009
[0, 2, 4, 4.3, 5.5, 8, 9, 11.6, 77.4, 112] 3.117207

pypy 1.5a with mergesort, Fail I didn't see the error in the outputs. thanks for the catch

Mark-Essels-iMac:py-util messel$ pypy sort.py 
[0, 11.6, 2, 4.3, 5.5, 9, 112, 8, 77.4, 4] 0.000294
[0, 11.6, 2, 4.3, 5.5, 9, 112, 8, 77.4, 4] 0.365598
[0, 11.6, 2, 4.3, 5.5, 9, 112, 8, 77.4, 4] 0.641387
[0, 11.6, 2, 4.3, 5.5, 9, 112, 8, 77.4, 4] 0.915025
[0, 11.6, 2, 4.3, 5.5, 9, 112, 8, 77.4, 4] 1.20461
[0, 11.6, 2, 4.3, 5.5, 9, 112, 8, 77.4, 4] 1.481948
[0, 11.6, 2, 4.3, 5.5, 9, 112, 8, 77.4, 4] 1.756874
[0, 11.6, 2, 4.3, 5.5, 9, 112, 8, 77.4, 4] 2.029232
[0, 11.6, 2, 4.3, 5.5, 9, 112, 8, 77.4, 4] 2.300741
[0, 11.6, 2, 4.3, 5.5, 9, 112, 8, 77.4, 4] 2.574396

whoa. that pypy version is not too shabby compared to my home brewed c++ qsort

in place sorting 1000000 arrays 
sorted 0    2   4   4.3 5.5 8   9   11.6    77.4    112
in place method: 0.000
sorted 0    2   4   4.3 5.5 8   9   11.6    77.4    112
in place method: 0.097
sorted 0    2   4   4.3 5.5 8   9   11.6    77.4    112
in place method: 0.194
sorted 0    2   4   4.3 5.5 8   9   11.6    77.4    112
in place method: 0.292
sorted 0    2   4   4.3 5.5 8   9   11.6    77.4    112
in place method: 0.388
sorted 0    2   4   4.3 5.5 8   9   11.6    77.4    112
in place method: 0.485
sorted 0    2   4   4.3 5.5 8   9   11.6    77.4    112
in place method: 0.583
sorted 0    2   4   4.3 5.5 8   9   11.6    77.4    112
in place method: 0.680
sorted 0    2   4   4.3 5.5 8   9   11.6    77.4    112
in place method: 0.777
sorted 0    2   4   4.3 5.5 8   9   11.6    77.4    112
in place method: 0.874