1/2/25, 12:17 PM Quick Sort
AfterAcademy
Admin AfterAcademy
10 Aug 2020
Quick Sort
Difficulty: Hard
Asked in: Microsoft, Google, Goldman Sachs
Sorting is a process of arranging items systematically. There are several
ways to sort a list of items, you may read about some of the basic
algorithms we have discussed here .
https://afteracademy.com/blog/quick-sort/ 1/10
1/2/25, 12:17 PM Quick Sort
Understanding The Problem
Problem Description
Given an array of integers arr[] , write a program to sort the array in
ascending order using Quick Sort.
Example 1
Input: arr[] = [5,2,3,1]
Output: [1,2,3,5]
Explanation: Return the sorted array
Example 2
Input: arr[] = [9,-3,5,2,6,8,-6,1,3]
Output: [-6,-3,1,2,3,5,6,8,9]
Solution
As you might know for sorting or comparison-based sorting algorithm the
best time complexity that is possible is NlogN. Some of the algorithms that
provide this time complexity are merge sort and quicksort. You could read
about the merge sort algorithm and understand how the sorting takes place
and you will also get to know that the merge sort uses an auxiliary space
complexity of O(N).
We will discuss quick sort which guarantees with a very high probability of
time complexity of NlogN in average case but has N² in its worst case. Even
though the time complexity is N² in the worst case, It is mostly used by
various applications because its space complexity is O(1). This algorithm is
so much efficient in practical use cases that the sort function of most of the
languages uses quicksort.
Let us see how the quicksort algorithm works in practice for this array.
https://afteracademy.com/blog/quick-sort/ 2/10
1/2/25, 12:17 PM Quick Sort
[35, 33, 42, 10, 14, 19, 27, 44, 26, 31]
At each iteration of quicksort, we choose the pivot element and try to bring
it at its correct position. Let us see that in our implementation of quicksort,
we always choose the end element of the array as a pivot and try to bring it
at its correct position. What this means that we will try to bring all the
elements that are smaller than the pivot element to the left side of it and all
the elements greater than the pivot element to the right side of it.
The pivot element is the element that will try to be at the current position
is known as the pivot element.
In the above case, in the first iteration, we choose 31 as the pivot, now
10, 14, 19, 27, 26 will go to the left of 31 and 35, 33, 42, 44
will go to the right of 31 . Now you have two smaller unsorted arrays [10,
14, 19, 27, 26] 31 [35, 33, 42, 44] , so we can repeat the
process as the pivot element 31 is at its correct position.
Now if we go on, there will be the case when the size of the subarray
becomes 1, which will be considered as the base case.
If we follow the same procedure for example 2. Then each step will work like
this:
https://afteracademy.com/blog/quick-sort/ 3/10
1/2/25, 12:17 PM Quick Sort
Solution Steps
1. Find a pivot item in the array. This item is the basis for comparison
for a single round.
2. Start a pointer (the left pointer ) at the first item in the array.
3. Start a pointer (the right pointer ) at the last item in the array.
4. While arr[left pointer] < pivot value , move the left pointer
to the right. Continue until the arr[left pointer] >= pivot value.
5. While arr[right pointer] > pivot value , move the right
pointer to the left. Continue until the arr[right pointer] <= pivot value.
6. If arr[left pointer] <= arr[right pointer] , then swap the
values.
7. Move the left pointer to the right by one and the right pointer
to the left by one.
8. If the left pointer and right pointer doesn’t meet, go to step
1.
https://afteracademy.com/blog/quick-sort/ 4/10
1/2/25, 12:17 PM Quick Sort
Pseudo Code
void quicksort(int a[], int start, int end)
{
if(start < end)
{
int pi
pi= partition(a, start, end)
quicksort(a, start, pi-1)
quicksort(a, pi+1, end)
}
}
// partition function
int partition (int arr[], int start, int end)
{
int pivot = arr[end] // selecting last element as pivot
int i = (start - 1) // index of smaller element
for (int j = start to j <= end- 1)
{
// If the current element is smaller than or equal to pivot
if (arr[j] <= pivot)
{
i = i + 1 // increment index of smaller element
swap(arr[i], arr[j])
}
}
swap(arr[i + 1], arr[high])
return (i + 1)
}
Complexity Analyisis
Worst-case time complexity: O( n² )
Best-case time complexity: O( n log n ) (simple partition)or O( n )
(three-way partition and equal keys)
Average-case time complexity: O( n log n )
Worst-case space complexity: O( n ) auxiliary (naive)
Critical Ideas To Think
https://afteracademy.com/blog/quick-sort/ 5/10
1/2/25, 12:17 PM Quick Sort
What if start > end ? that means the array[start::end] is an
invalid array.
start > end . Is this case possible? If yes, then think of such a case!
Can we choose a random pivot instead of arr[end] ? If yes, then will
it affect the complexity?
Can you write the recurrence relation for the quicksort algorithm?
Even though, quick sort worst-case complexity is O(n²), though it
preferred more than merge-sort! Why?
Is quick sort is a stable sorting algorithm? If not, how ?
For a better gist of comparison of sorting algorithms, read here.
Suggested Problems to Solve
Find kth largest in an unsorted array.
Quicksort in a singly linked list.
Top K frequent elements.
K closest points to origin.
The painter’s partition problem
Maximum average sum partition of an array
Please comment down below if you have a better insight in the above approach.
Happy Coding, Enjoy Algorithms!
https://afteracademy.com/blog/quick-sort/ 6/10
1/2/25, 12:17 PM Quick Sort
Recommended for You
Recursive Insertion Sort Sort List - Merge Sort
Write a program for the recursive Sort a linked list using Merge Sort. This is a
implementation of Insertion Sort. Insertion very famous interview problem that
Sort is used to sort a given array. This demonstrates the concept of recursion. This
problem will sharpen your recursion skills. problem is quite similar to Merge Sort in
Arrays.
Admin AfterAcademy Admin AfterAcademy
23 Sep 2020 12 Sep 2020
https://afteracademy.com/blog/quick-sort/ 7/10
1/2/25, 12:17 PM Quick Sort
Wave Array Merge Two Sorted Arrays
You are given an unsorted array of You are given two sorted arrays arr1[ ] and
integers(arr) of length n, write a program to arr2[ ] of sizes m and n respectively. Write a
sort it in wave form. The array elements in program to merge them in such a way that
the resultant array must be such that arr[0] the resultant array is sorted too.
>= arr[1] <= arr[2] >= arr[3] <= arr[4] ... and so
on. If there are multiple sorted orders in
wave-form, return the one which is
lexicographically smallest.
Admin AfterAcademy Admin AfterAcademy
20 Aug 2020 17 Aug 2020
https://afteracademy.com/blog/quick-sort/ 8/10
1/2/25, 12:17 PM Quick Sort
Combinations Search in a 2-D Matrix
Given two integers n and k, Write a program You are given a matrix arr of m x n size.
to return all possible combinations of k Write a program to searches for a value k in
numbers out of 1 2 3 ... n. Elements in a arr. This arr has the following properties: -
combination must be in a non-descending Integers in each row are sorted from left to
order. The combinations themselves must right. - The first value of each row is greater
be sorted in ascending order, i.e., the than the last value of previous row. This is a
combination with the smallest first element basic optimization problem that will clear
should be printed first. the concept of searching.
Admin AfterAcademy Admin AfterAcademy
8 Aug 2020 18 Jul 2020
Connect With Your Mentors
Janishar Ali Amit Shekhar
Founder | IIT-BHU | 10 Yrs Exp. Founder | IIT-BHU | 10 Yrs Exp.
https://afteracademy.com/blog/quick-sort/ 9/10
1/2/25, 12:17 PM Quick Sort
Copyright 2022, MindOrks Nextgen Private Limited
https://afteracademy.com/blog/quick-sort/ 10/10
