License New BSD license
Lines 42
Keywords
algorithm (8) python (33) quicksort (5)
Implements this Algorithm
Permissions
Owner: Theodore Test
Viewable by Everyone
Editable by All Siafoo Users
Hide
Easily highlight source code for your blog with our Syntax Highlighter. Join Siafoo Now or Learn More

Python Quick Sort Atom Feed 0

In Brief A simple implementation of Quicksort in Python. I'll add a more intelligent pivot-picker soon.
# 's
 1def quick_sort(iterable, pivot_picking_function):
2 '''Arguably the most awesome sorting algorithm out there.'''
3
4 if iterable == None or len(iterable) <= 1:
5 return iterable
6
7 pivot = pivot_picking_function(iterable)
8 iterable.remove(pivot)
9
10 first_half = []
11 second_half = []
12
13
14 for x in iterable:
15 if x <= pivot:
16 first_half.append(x)
17 else:
18 second_half.append(x)
19
20 return quick_sort(first_half,pivot_picking_function) + [pivot] + quick_sort(second_half, pivot_picking_function)
21
22
23def dumb_pivot_picker(iterable):
24 '''A dumb way of picking a pivot.'''
25 from random import randint
26
27 if iterable == None:
28 return None
29
30 array_length = len(iterable)
31
32 if array_length < 1:
33 return None
34 elif array_length > 2:
35 return iterable[randint(1,array_length - 2)]
36 elif array_length == 2:
37 return iterable[randint(0,1)]
38 else:
39 return iterable[0]
40
41if __name__ == "__main__":
42 test_array = [3,90,20,1,20,4]
43 out_array = quick_sort(test_array, dumb_pivot_picker)
44 print out_array

A simple implementation of Quicksort in Python. I'll add a more intelligent pivot-picker soon.