# 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.

# Grading your solution

## Python

You can use the following file to grade your solution.

```
# 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()
answer = sorted(array)
correct = len(submission) == len(answer) and (submission == answer)
if correct:
print('PASSED (Runtime = %.2f seconds)' % (toc-tic).total_seconds())
npassed += 1
else:
print('FAILED')
nfailed += 1
print(array)
print(submission)
print(answer)
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.