codedamn

What is Quick Sort?

  • Aman Chopra's profile image
    Aman Chopra
    Author
What is Quick Sort?

In this article, we will learn about Quick Sort Algorithm, its implementation, time complexity, and its pros and cons.

What is Quick Sort?

It is one of the fastest sorting algorithms that follow the Divide and Conquer approach, it is a technique of breaking down the algorithms into subproblems, then solving the subproblems, and combining the results back together to solve the original problem.

Working of Quick Sort

  1. It picks an element as a pivot element.
    • Pivot can be random, i.e. select the random pivot from the given array.
    • A pivot can either be the leftmost element or the rightmost element of the given array.
    • Select median as the pivot element.
  2. It partitions the given array around the pivot into two halves.
  3. It then partitions the leftmost sub-array and rightmost sub-array separately using the same approach and sorts them first.
  4. It then combines both arrays and results in a sorted array.

Algorithm

  1. Select the pivot element.
  2. After the first pass, elements < pivot element will be on LHS
  3. Elements > pivot element will be on RHS
  4. Step 2 and Step 3 will keep continuing for every sub-array until each element of sub-arrays is sorted.
  5. At last, merge the both left and right sorted sub-array.

Quicksort Implementation

Program:- Write a program to implement Quick Sort in Java language.

import java.util.Arrays; public class QuickSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] arr = {5, 4, 3, 2, 1}; sort(arr, 0, arr.length-1); System.out.println(Arrays.toString(arr)); } static void sort(int[] nums, int low, int high) { if (low > high) return; int start = low; int end = high; int mid = start + (end - start) / 2; int piv = nums[mid]; while (start <= end) { while (nums[start] < piv) { start++; } while (nums[end] > piv) { end--; } if (start <= end) { int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start++; end--; } } // now my pivot is at correct index and thus sort other two halves sort(nums, low, end); sort(nums, start, high); } }
Code language: JavaScript (javascript)

Time Complexity

Recurrence Relation

A recurrence is an equation or inequality that reflects the value of a function with smaller inputs. It can be used to represent the running duration of an algorithm that comprises a recursive call to itself.

Recurrence relation of Quick Sort:-

T(N) = T(K) + T(N-K-1) + O(N)

Best Case

When K = N/2

T(N) = T(N/2) + T(N – N/2 – 1) + O(N)

T(N) = T(N/2) +T(N/2) + O(N)

T(N) = 2 T(N/2) + O(N)

T(N) = O(N logN)

Worst Case

When K = 0

T(N) = T(0) + T(N – 0 – 1) + O(N)

T(N) = T(N-1) + O(N)

T(N) = O(N2)

Space Complexity

Quick Sort has a space complexity of O(logN), even in the worst case.

Why Quick Sort is preferred over Merge Sort for Sorting arrays?

Quick sort, in general, doesn’t require space since it is an in-place sorting algorithm whereas Merge sort requires O(N) extra space, (N is the size of an array).

In comparison with merge sort, both have the same average complexity but the constants get differ for arrays and thus this is the reason why we prefer quick sort over merge sort.

What is 3-way Quick Sort?

In a simple quick sort, there is a pivot element, then we do the partition of the arrays around that pivot element and then recur for subarrays on the left and right of the pivot element.

But what if in an array there are multiple redundant elements like arr={1, 4, 3, 5, 4, 1, 4, 5, 5, ,3, 1, 7, 9, 4, 2, 2, 1}. Now if we pick 4 as a pivot element, then it will fix only one 4 and recursively process the remaining occurrences. Then in such cases, we prefer a 3-way quick sort i.e. an array arr[n] => arr{l…r} is divided into 3 parts:-

  1. Elements less than pivot element -> arr[l…i]
  2. Elements equal to pivot element-> arr[i+1…j-1]
  3. Elements greater than pivot element -> arr[j..r]

Advantages

  1. It is an in-place sorting algorithm.
  2. For the best case, it only takes O(n log n) time.
  3. Efficient to deal with a large number of items.
  4. It doesn’t require additional storage.
  5. It has been subjected to a thorough mathematical analysis, and a very precise statement can be made about performance issues.

Disadvantages

  1. It is recursive in nature.
  2. Without recursion, its implementation becomes extremely complicated.
  3. It takes O(N2) time to sort in its worst case.
  4. It is fragile, i.e. a simple mistake in the implementation can go unnoticed and cause it to perform badly.
  5. The split stage is complex in the quick sort algorithm as compared to the merge sort algorithm.

Conclusion

The Quicksort algorithm is one of the fastest sorting algorithms. It uses Divide and Conquer approach.

We generally use the Quicksort algorithm when:-

  • the programming language is good for recursion
  • time complexity matters
  • space complexity matters

Learn programming on codedamn

Codedamn is an interactive coding platform with tons of sweet programming courses that can help you land your first coding job. Here's how:

Programming is one of the most in-demand jobs today. Learning to program can change your future. All the best!