# Quicksort Algorithm

Copied!
Happy Pythoning!

hauntarl

Here’s an in-place version for the quicksort algorithm.

``````from random import randint
from timer import timed

def sort(items, low, high):
'''
Three-way Partition
. quick sort can be inplace as well, in order to reduce space complexity
using inplace sorting and have support for duplicate elements you need to
perform a three-way partition as follows
'''
if low >= high:
return items

pivot = items[randint(low, high)]  # selecting a pivot
# initialize variables for partition
left = low    # [low, left) - less than elements
right = low   # [left, right) - equal to pivot
upper = high  # [right, upper] - unexamined, (upper, high] - greater than
while right <= upper:
if items[right] < pivot:
items[left], items[right] = items[right], items[left]
left += 1
right += 1
elif items[right] > pivot:
items[right], items[upper] = items[upper], items[right]
upper -= 1
else:
right += 1

sort(items, low, left-1)
sort(items, right, high)
return items

@timed
def to_sort(items): sort(items, 0, len(items) - 1)

# Testing
items = [randint(1, 10) for _ in range(10)]
print(items)
print(sort(items, 0, len(items) - 1))

# Benchmarking: to test how scalable the algorithm is
to_sort([randint(1, 1000) for _ in range(1000)])
to_sort([randint(1, 1000) for _ in range(10000)])
'''
OUTPUT:
[4, 10, 5, 6, 2, 1, 7, 10, 1, 7]
[1, 1, 2, 4, 5, 6, 7, 7, 10, 10]
Finished 'to_sort' in 0.0039396000 secs
Finished 'to_sort' in 0.0343496000 secs
'''
``````

PS: It might not be perfect or even well-optimized, open to suggestions and further improvements.

to join the conversation.