Blog_Banner_Asset
    Homebreadcumb forward arrow iconBlogbreadcumb forward arrow iconArtificial Intelligencebreadcumb forward arrow iconQuicksort Algorithm Explained [With Example]

Quicksort Algorithm Explained [With Example]

Last updated:
15th Dec, 2020
Views
Read Time
5 Mins
share image icon
In this article
Chevron in toc
View All
Quicksort Algorithm Explained [With Example]

Quick Sort is based on the concept of Divide and Conquer algorithm, which is also the concept used in Merge Sort. The difference is, that in quick sort the most important or significant work is done while partitioning (or dividing) the array into subarrays, while in case of merge sort, all the major work happens during merging the subarrays. For quick sort, the combining step is insignificant.

Top Machine Learning and AI Courses Online

Quick Sort is also called partition-exchange sort. This algorithm divides the given array of numbers into three main parts:

  1. Elements less than the pivot element
  2. Pivot element
  3. Elements greater than the pivot element

Pivot element can be chosen from the given numbers in many different ways:

Ads of upGrad blog
  1. Choosing the first element
  2. Choosing the last element (example shown)
  3. Choosing any random element
  4. Choosing the median

For example: In the array {51, 36, 62, 13, 16, 7, 5, 24}, we take 24 as pivot (last element). So after the first pass, the list will be changed like this.

{5 7 16 13 24 62 36 51}

Trending Machine Learning Skills

Enrol for the Machine Learning Course from the World’s top Universities. Earn Masters, Executive PGP, or Advanced Certificate Programs to fast-track your career.

Hence after the first pass, the array is sorted such that all elements less than the chosen pivot are on its left side and all greater elements on its right side. The pivot is finally at the position it is supposed to be in the sorted version of the array. Now the subarrays {5 7 16 13} and {62 36 51} are considered as two separate arrays, and same recursive logic will be applied on them, and we will keep doing this until the complete array is sorted.

Also Read: Heap Sort in Data Structure

How does it work?

These are the steps followed in the quick sort algorithm:

  1. We choose our pivot as the last element, and we start to partition (or divide) the array for the first time.
  2. In this partitioning algorithm, the array is broken into 2 subarrays such that all the elements smaller than the pivot will be on the left side of the pivot and all the elements greater than the pivot will be on the right side of it.
  3. And the pivot element will be at its final sorted position.
  4. The elements in the left and right subarrays do not have to be sorted.
  5. Then we recursively pick the left and right subarrays, and we perform partitioning on each of them by choosing a pivot in the subarrays and the steps are repeated for the same.

Shown below is how the algorithm works in C++ code, using an example array.

void QuickSort(int a[], int low, int high)

{

if(high<low)

return;

int p= partition(a,low,high);

QuickSort(a,low,p-1);

QuickSort(a,p+1,high);

}

 

int partition(int a[], int low, int high)

{

int pivot=a[high];

int i=low;

for(int j=low; j<high; j++)

{

if(a[j]<=pivot)

{

swap(&a[j],&a[i]);

i++;

}

}

swap(&a[i],&a[high]);

return i;

}

int main()

{

int arr[]={6,1,5,2,4,3};

QuickSort(arr,0,5);

cout<<”The sorted array is: “;

for(int i=0; i<6; i++)

cout<<arr[i]<<” “;

return 0;

}

Below is a pictorial representation of how quick sort will sort the given array.

Suppose the initial input array is:

So after our first partition, the pivot element is at its correct place in the sorted array, with all its smaller elements to the left and greater to the right.

Now QuickSort() will be called recursively for the subarrays {1,2} and {6,4,5} and continue till the array is sorted.

Must Read: Types of AI Algorithms You Should Know

Complexity Analysis

Best Case Time Complexity: Ω(n*log n)

Average Time Complexity: Θ(n*log n)

Worst Case Time Complexity: O(n2)

If partitioning leads to nearly equal subarrays, then the running time is the best, with time complexity as O(n*log n).

Worst case happens for arrays with cases where the elements are already sorted, and pivot is chosen as the last element. Here the partitioning gives unbalanced subarrays, where all elements are already smaller than the pivot and hence on its left side, and no elements on the right side.

Space Complexity (considering recursion stack): O(n*log n) 

Popular AI and ML Blogs & Free Courses

Conclusion

Ads of upGrad blog

Quicksort is a comparison-based algorithm and it is not stable. A small optimization that can be done, is to call the recursive QuickSort() function for the smaller subarray first and then the larger subarray.

Overall, Quick Sort is a highly efficient sorting technique that can give better performance than Merge Sort in the case of smaller arrays. 

If you are keen on learning more, check out upGrad & IIIT-B’s PG Diploma in Machine Learning and AI Program.

Profile

Pavan Vadapalli

Blog Author
Director of Engineering @ upGrad. Motivated to leverage technology to solve problems. Seasoned leader for startups and fast moving orgs. Working on solving problems of scale and long term technology strategy.
Get Free Consultation

Select Coursecaret down icon
Selectcaret down icon
By clicking 'Submit' you Agree to  
UpGrad's Terms & Conditions

Our Popular Machine Learning Course

Frequently Asked Questions (FAQs)

1What are the disadvantages of using the quicksort algorithm?

In general, the quick sort algorithm is the most efficient and extensively used technique for sorting a list of any size, although it does have some disadvantages. It's a fragile method, which implies that if a minor flaw in the implementation goes unchecked, the results will suffer. The implementation is difficult, especially if recursion is not available. One little limitation of the quick sort algorithm is that its worst-case performance is comparable to the bubble, insertion, or select sorts' typical performances.

2What is the bucket sort algorithm used for?

The bucket sort algorithm is a sorting method that is used to put different elements into different groups. It is so named because the various subgroups are referred to as buckets. Due to the sheer uniform distribution of elements, it is asymptotically fast. However, if we have a huge array, it is ineffective since it raises the cost of the total process, making it less affordable.

3Which one is better to use—the quicksort or the mergesort algorithm?

For tiny data sets, Quicksort is quicker than other sorting algorithms like Selection Sort, but Mergesort has consistent performance regardless of data size. Quicksort, on the other hand, is less efficient than mergesort when dealing with bigger arrays. Mergesort takes up more space, but quicksort takes up very little. Quicksort, in particular, has strong cache locality, making it quicker than merge sort in many situations, such as in a virtual memory environment. As a result, quicksort outperforms the mergesort algorithm.

Explore Free Courses

Suggested Blogs

Artificial Intelligence course fees
5216
Artificial intelligence (AI) was one of the most used words in 2023, which emphasizes how important and widespread this technology has become. If you
Read More

by venkatesh Rajanala

29 Feb 2024

Artificial Intelligence in Banking 2024: Examples &#038; Challenges
5720
Introduction Millennials and their changing preferences have led to a wide-scale disruption of daily processes in many industries and a simultaneous g
Read More

by Pavan Vadapalli

27 Feb 2024

Top 9 Python Libraries for Machine Learning in 2024
75264
Machine learning is the most algorithm-intense field in computer science. Gone are those days when people had to code all algorithms for machine learn
Read More

by upGrad

19 Feb 2024

Top 15 IoT Interview Questions &#038; Answers 2024 – For Beginners &#038; Experienced
64237
These days, the minute you indulge in any technology-oriented discussion, interview questions on cloud computing come up in some form or the other. Th
Read More

by Kechit Goyal

19 Feb 2024

Data Preprocessing in Machine Learning: 7 Easy Steps To Follow
151423
Summary: In this article, you will learn about data preprocessing in Machine Learning: 7 easy steps to follow. Acquire the dataset Import all the cr
Read More

by Kechit Goyal

18 Feb 2024

Artificial Intelligence Salary in India [For Beginners &#038; Experienced] in 2024
908011
Artificial Intelligence (AI) has been one of the hottest buzzwords in the tech sphere for quite some time now. As Data Science is advancing, both AI a
Read More

by upGrad

18 Feb 2024

24 Exciting IoT Project Ideas &#038; Topics For Beginners 2024 [Latest]
755265
Summary: In this article, you will learn the 24 Exciting IoT Project Ideas & Topics. Take a glimpse at the project ideas listed below. Smart Agr
Read More

by Kechit Goyal

18 Feb 2024

Natural Language Processing (NLP) Projects &amp; Topics For Beginners [2023]
106864
What are Natural Language Processing Projects? NLP project ideas advanced encompass various applications and research areas that leverage computation
Read More

by Pavan Vadapalli

17 Feb 2024

45+ Interesting Machine Learning Project Ideas For Beginners [2024]
326849
Summary: In this Article, you will learn Stock Prices Predictor Sports Predictor Develop A Sentiment Analyzer Enhance Healthcare Prepare ML Algorith
Read More

by Jaideep Khare

16 Feb 2024

Schedule 1:1 free counsellingTalk to Career Expert
icon
footer sticky close icon