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!
Below, we provide a short Python code template for you to implement quick-sort.
# quick_sort.pyimport randomdef quick_sort(array):# base case# choose pivot# split into left and right# quick-sort each segment# returnarray = [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
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.
23 227 198 1910 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.
19 198 22733 295 378 421 458 479 687 840 922 945
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.