-
Notifications
You must be signed in to change notification settings - Fork 0
/
quick.py
39 lines (31 loc) · 1.37 KB
/
quick.py
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
39
# The following was copied from https://www.geeksforgeeks.org/python-program-for-quicksort/
# Python program for implementation of Quicksort Sort
# This implementation utilizes pivot as the last element in the nums list
# It has a pointer to keep track of the elements smaller than the pivot
# At the very end of partition() function, the pointer is swapped with the pivot
# to come up with a "sorted" nums relative to the pivot
def partition(l, r, nums):
# Last element will be the pivot and the first element the pointer
pivot, ptr = nums[r], l
for i in range(l, r):
if nums[i] <= pivot:
# Swapping values smaller than the pivot to the front
nums[i], nums[ptr] = nums[ptr], nums[i]
ptr += 1
# Finally swapping the last element with the pointer indexed number
nums[ptr], nums[r] = nums[r], nums[ptr]
return ptr
# With quicksort() function, we will be utilizing the above code to obtain the pointer
# at which the left values are all smaller than the number at pointer index and vice versa
# for the right values.
def quicksort(l, r, nums):
if len(nums) == 1: # Terminating Condition for recursion. VERY IMPORTANT!
return nums
if l < r:
pi = partition(l, r, nums)
quicksort(l, pi-1, nums) # Recursively sorting the left values
quicksort(pi+1, r, nums) # Recursively sorting the right values
return nums
def sort(arr):
arr = quicksort(0, len(arr)-1, arr)
return arr