What is Quick Sort?

Introduction

In the era of sorting algorithms which is a very essential component of computer science, they help us sort data in a logical and simple way. To make it easier and more understandable for us to work on Data/Large Data. Today, we are learning about Quick Sort. Quick sort is the most commonly and most efficiently used algorithm.

Quick sort is nothing but a sorting technique that uses a divide-and-conquer strategy to sort data. To use the divide and conquer strategy in quick sort uses the pivot element.

The basic idea behind using quick sort is to select any element from the array as a pivot element. Then divide an array into two sublists. One will consist of all the smaller elements than the pivot element on the left-hand side and on the right-hand side all the larger elements will be there. then divide those sub-arrays using the same method. And at last, combine those elements to create a fully sorted list.

How Quick Sort Works?

To learn the process of quick sorting, we are taking a given example: A[] = {7 , 10 , 2 , 70 , 1 , 3 , 9 , 7}.

Step 1:

First of all, Select a Pivot element(FYI: It could be any element) from an array. Then mark the 0th element as Start and the last element as End. To understand more clearly please look into Fig 1.

Step 2:

Now, here are two conditions that come into the picture.
1. First condition is to Increment the position of Start until you find a bigger element than the Pivot element.
2. Second condition is to decrement the position of the End until you find a lesser or equal to the pivot element.

Here, we started from the 0th value and incremented till the 1st value, because the 1st index value is greater than the pivot element which is 10.

Also similarly last value of End is 7. Which is equal to the pivot element hence we stopped at the last value itself.

Step 3:

Now swap the value of the start position with the value of the end position. To get more understanding please see Fig. 1.

Step 4:

Follow steps 2 and 3 until the start and end cross each other.

Step 5:

You can see all the smaller elements are on LHS and all the larger ones are on RHS. Now the array is divided into parts. Now one array is {1 , 7 , 2 , 3 } and the second array is { 70 , 9 , 10}. 7 is at its fixed position i.e. 4.

Now perform steps 1,2, 3, and 4 for left array and right array too.

Implementation of Quick Sort:

Implementing quick sort requires knowledge of basic programming concepts such as recursion and arrays.

Here’s the algorithm in pseudocode:

Quicksort(array, low, high)
    if low < high
        pivotIndex = Partition(array, low, high)
        Quicksort(array, low, pivotIndex - 1)
        Quicksort(array, pivotIndex + 1, high)
    end if
end function

Partition(array, low, high)
    pivot = array[high]
    i = low - 1
    for j = low to high - 1
        if array[j] <= pivot
            i = i + 1
            Swap(array[i], array[j])
        end if
    end for
    Swap(array[i + 1], array[high])
    return i + 1
end function

Swap(a, b)
    temp = a
    a = b
    b = temp
end function

Advantages of Quick Sort

It has several advantages, making it a popular sorting algorithm in computer science. These include:

Efficiency:
Quick sort has an average time complexity of O(n log n), making it one of the fastest sorting algorithms, especially for large datasets.
Simplicity:
It is relatively easy to understand and implement, even for novice programmers.
In-place sorting:
It sorts the elements in place, meaning that it does not require additional memory space to store the sorted list, unlike other sorting algorithms like merge sort.
Good performance in most cases:
Quick sort performs well in most cases, making it a reliable choice for sorting data.

Disadvantages of Quick Sort

Despite its numerous advantages, also has several disadvantages, which include:

Worst-case scenario:
As mentioned earlier, it can have a worst-case time complexity of O(n^2), which is not efficient, especially for large datasets.
Unstable sorting:
Quick sorting is an unstable sorting algorithm, meaning that it may not preserve the relative order of equal elements in the list.
The choice of pivot element:
The efficiency of Quick Sort depends on the choice of pivot element, and selecting a poorly chosen pivot can result in poor performance.

Conclusion

Quick sort is a highly efficient and popular sorting algorithm that uses a divide-and-conquer strategy to sort a list or an array of elements. It has an average time complexity of O(n log n), making it one of the fastest sorting algorithms, especially for large datasets.

Read More
What is Merge Sort?

Follow Us on
https://www.linkedin.com/company/scribblers-den/
https://www.facebook.com/scribblersden.blogs

Thank You

Introduction