Overview

While learning DSA for placement and for the college examination, we all come across to different sorting algorithm for linear data structures. One of the algorithm we learn is the Quick Sort. Now many of you thinking, why just Quick Sort?

In this blog post, We discuss about the Quick Sort Implementation using Recursion and Why we prefer Quick Sort over Merge Sort and other sorting algorithm?

Introduction

Quick Sort is an sorting algorithm uses divide-and-conquer technique to recursively sort the sub-array to get a sorted array.

So, from the above definition nothing much is getting clear. Also it is not clearing out the question which we are struggling to get though.

Before moving to the deep dive into the discussion lets look into the time and space complexity of the Quick Sort with the comparison of other sorting algorithm.

Implementation

public class QuickSort {

    private int partition(int[] arr, int start, int end) {
        int pivot = arr[end]; // mark last element as pivot
        int idx = start - 1; // use for identifying the pivot position

        for(int i = start; i<end; i++) {
        // move all the elements smaller than the pivot to left side of the pivot
            if(arr[i] < pivot) {
                idx++;
                int temp = arr[idx];
                arr[idx] = arr[i];
                arr[i] = temp;
            }
        }
        // move the pivot to the correct position in the array
        idx++;
        int temp = arr[idx];
        arr[idx] = arr[end];
        arr[end] = temp;

        return idx;
    }

    public void quickSort(int[] arr, int start, int end) {
        if(start < end) {
            // getting the correct position of the pivot
            int pos = partition(arr, start, end); 
            // apply recursion to the left sub-array of the pivot
            quickSort(arr, start, pos - 1); 
            // apply recursion to the right sub-array of the pivot
            quickSort(arr, pos + 1, end); 
        }
    }
}

Why Quick sort is prefer over Merge Sort and other Sorting algorithm?

Quick sort is used whenever we have less space to sort the array with O(nlogn) time complexity. Since, both Quick Sort and Merge Sort sorted the array in O(nlogn) but in Merge Sort we require extra space for storing data while partitioning but this is not the case in Quick Sort. And also, in worst case Merge Sort is better than Quick Sort [O(n^2)] but still we prefer the Quick Sort over the merge sort due to its less space.

🗒️For better referencing, Time and Space Complexity chart is attached above. You can refence it from there.

And also according to the Wikipedia,

When implemented well (Quick Sort), it can be somewhat faster than merge sort and about two or three times faster than heapsort.

Conclusion

For most of the case, Quick Sort is good for sorting the array. But every sorting algorithm have its own advantage and disadvantage. So, it depends what are the different conditions you have while sorting the data structure, just going to just one doesn't fits.

Subscribe to the newsletter to read more blogs on data structures and algorithms!