forked from kennyledet/Algorithm-Implementations
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathquick_sort.py
More file actions
40 lines (35 loc) · 973 Bytes
/
Copy pathquick_sort.py
File metadata and controls
40 lines (35 loc) · 973 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from random import randint, shuffle
def quicksort(array):
"""
Quicksort (partition-exchange sort)
----------
Advantages:
- Fast for large data sets
Disadvantages:
- Not stable
Time complexity:
- worst: O(n^2)
- average: O(n*log(n))
- best: O(n*log(n))
Space complexity:
- Ideally O(log n)
- This implementation O(n)
"""
if len(array) <= 1:
return array
pivot_index = randint(0, len(array)-1)
pivot = array.pop(pivot_index)
less, greater = [], []
for element in array:
if element <= pivot:
less.append(element)
else:
greater.append(element)
return quicksort(less) + [pivot] + quicksort(greater)
if __name__ == '__main__':
#test cases
array = list(range(10, 0, -1))
shuffle(array)
print('Unsorted list: ' + str(array));
array = quicksort(array)
print('Sorted list: ' + str(array))