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.