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.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
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:
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.
Sample output:
19 198 22733 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.