Compare sorting algorithms' performance: Difference between revisions

Content added Content deleted
(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 [[Quick sort]] with different pivot selection mechanisms.
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]] subtask, ''usec()'' is defined in the [[Query Performance]] subtask.
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}}