Compare sorting algorithms' performance: Difference between revisions
Content added Content deleted
m (Quick sort -> Quicksort) |
(couple examples of sorting routine) |
||
Line 10: | Line 10: | ||
Consider at least two different sorting function (different algorithms or/and different implementation of the same algorithm). |
Consider at least two different sorting function (different algorithms or/and different implementation of the same algorithm). |
||
For example, consider [[Bubble Sort]], [[Insertion sort]], [[Quicksort]] or/and implementations of [[ |
For example, consider [[Bubble Sort]], [[Insertion sort]], [[Quicksort]] or/and implementations of [[Quicksort]] with different pivot selection mechanisms. |
||
Where possible, use existing implementations. |
Where possible, use existing implementations. |
||
Line 28: | Line 28: | ||
'''Interpreter:''' [[Python]] 2.5 |
'''Interpreter:''' [[Python]] 2.5 |
||
[[Category:Python]] |
[[Category:Python]] |
||
===A couple examples of sorting routines=== |
|||
def builtinsort(x): |
|||
x.sort() |
|||
def partition(seq, pivot): |
|||
low, middle, up = [], [], [] |
|||
for x in seq: |
|||
if x < pivot: |
|||
low.append(x) |
|||
elif x == pivot: |
|||
middle.append(x) |
|||
else: |
|||
up.append(x) |
|||
return low, middle, up |
|||
# |
|||
def qsortranpart(seq): |
|||
size = len(seq) |
|||
if size < 2: return seq |
|||
low, middle, up = partition(seq, seq[random.randrange(size)]) |
|||
return qsortranpart(low) + middle + qsortranpart(up) |
|||
===Sequence generators=== |
===Sequence generators=== |
||
Line 53: | Line 73: | ||
Ns, Ts) |
Ns, Ts) |
||
</code> |
</code> |
||
Where ''writedat()'' is defined in the [[Write float arrays to a text file]] |
Where ''writedat()'' is defined in the [[Write float arrays to a text file]], ''usec()'' - [[Query Performance]], ''insertion_sort()'' - [[Insertion sort]], ''qsort'' - [[Quicksort]] subtasks correspondingly. |
||
===Plot timings=== |
===Plot timings=== |
||
{{library|matplotlib}} |
{{library|matplotlib}} |