Solution: Quick Sort

Grokking the Art of Recursion for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Quick Sort

Table of Contents

Contents are not accessible

Problem Statement

Write Recursive Approach for Quick Sort

Given an array of integers, sort it in ascending order using the Quick Sort algorithm.

Examples

Sr#	Input Array	Output	Description
1	[4, 2, 6, 8, 3]	[2, 3, 4, 6, 8]	The array is sorted in ascending order.
2	[10, 5, 3, 7, 2, 8, 6]	[2, 3, 5, 6, 7, 8, 10]	The array is sorted in ascending order.
3	[1, 2, 3, 4, 5]	[1, 2, 3, 4, 5]	The array is already sorted in ascending order.

Solution

The Quick Sort algorithm follows a divide-and-conquer approach to sort an array. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. The base case of the recursion is an array with zero or one element, which is already considered sorted.

The steps of the Quick Sort algorithm can be summarized as follows:

Select a pivot element from the array.
Partition the array into two sub-arrays: one with elements less than the pivot and one with elements greater than the pivot.
Recursively apply Quick Sort to the sub-arrays.
Combine the sorted sub-arrays and the pivot element to obtain the final sorted array.

Quick Sort

Code

Here is the code for this algorithm:

Python3

. . . .

Time and Space Complexity

The time complexity of the Quick Sort algorithm is $O(n* log n)$ on average and in the best case, where n is the number of elements in the array. This is because the algorithm divides the array into smaller sub-arrays and recursively sorts them. The worst-case time complexity is $O(n^2)$ when the array is already sorted or almost sorted, and the pivot is chosen poorly. However, the probability of encountering the worst case is low.

The space complexity of the algorithm is $O(log N)$ on average and in the best case, corresponding to the recursive call stack. In the worst case, the space complexity can be $O(N)$ due to the partitioning process. However, the overall space usage is efficient as the algorithm performs in-place sorting by swapping elements within the array.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible