# Hands-on: Implementing Quick-sort

June 29, 2018

Now that we have learnt about quick-sort, it’s time to implement it. You can work any any programming language of your choice - Python, C++, Java, or anything else you want. Let’s get started!

# Implementing Quick-sort

## Python

Below, we provide a short Python code template for you to implement quick-sort.

# quick_sort.py
import random
def quick_sort(array):
# base case
# choose pivot
# split into left and right
# quick-sort each segment
# return
array = [5, 10, 8, 7, 3, 7, 6, 12, 2, 7]
result = quick_sort(array)
assert result == [2, 3, 5, 6, 7, 7, 7, 8, 10, 12], result

## C++, Java, etc

If you’re not using Python, have your implementation accept test cases from standard input, and print results to standard output.

Input description: The first line contains the number of test cases T. This is followed by T lines. Each line starts with a number N, the size of the array. On the same line, the N numbers of the array are listed one after the other.

Sample input:

2
3 227 198 19
10 458 687 945 378 479 421 33 295 922 840

Output description: Output should contain T lines. Each line should just contain the numbers in sorted order, separated by spaces.

Sample output:

19 198 227
33 295 378 421 458 479 687 840 922 945

## Notes

The trickiest part about implementing quick-sort is the partition function. Specifically, be careful about how you handle the case where the pivot appears multiple times in the array.

## Python

# grader.py
from __future__ import print_function
import datetime
import random
from quick_sort import quick_sort
npassed, nfailed = 0, 0
for itest in range(1, 13):
print('Test case:', itest)
nelements = random.randint(int((10**(itest/2.))/2), int(10**(itest/2.)))
print('Array size:', nelements)
array = [random.randint(1, 100*nelements) for _ in range(nelements)]
tic = datetime.datetime.now()
submission = quick_sort(array)
toc = datetime.datetime.now()
if correct:
print('PASSED (Runtime = %.2f seconds)' % (toc-tic).total_seconds())
npassed += 1
else:
print('FAILED')
nfailed += 1
print(array)
print(submission)
print('='*100)
print('TOTAL PASSED: %d. TOTAL FAILED: %d.' % (npassed, nfailed))

Save the file above, and then run the following command:

python grader.py

and you should see the results of running the grader.

## C++, Java, etc

You’ll find all the files required to check your solution here: Algorithms - Sorting. In particular, the folder includes 3 files - input, answer and grader.py.

Do the following to check your solution.

{COMMAND TO RUN C++/JAVA CODE} < input > output
python grader.py output answer

# Bonus: Implement in-place Quick-sort

If you’d like to, you can also implement in-place quick-sort. Review the section on In-place Quick-sort from the tutorial if you get stuck.

Again, be careful about how you handle the case where the pivot appears multiple times in the array.

# Solution

The solution for this assignment can be found here: quick_sort.py. It also contains the solution for the bonus problem. quick_sort() takes about 7 seconds to run for input size 750,000. quick_sort_inplace() takes about 3.5 seconds. Note that if you implemented the solution in C++ / Java, your code should be executing about > 5x faster. Written by CommonLounge Team (@commonlounge)