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

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.