Quick Sort in C

In this article we will discuss about the Quick sort Algorithm. The working procedure of quick sort is simple. This algorithm will helpful for their academic purpose. Quick Sort is faster and highly efficient sorting algorithm.

It follows divide and conquer technique. It is a technique of breaking down the algorithm to subproblem and combining the result back together to solve the original problem. Merge Sort also follows this divide and conquer technique.

Quick Sort picks an element as pivot. A large array is divided into two arrays, one side (left hand part)holds the values which are smaller than pivot and other side (right hand part) of the array holds the element greater than pivot.

Then those two arrays are further partitioned using the same approach. This process continues till single elements remain in the sub array.

Working of Quick Sort Algorithm

Now let' see the working of Quick Sort Algorithm.

To understand the working let us take an unsorted array(unsorted array means the data present in the array is in jumbled order that is neither in ascending order nor descending)and start sorting it using Quick Sort Algorithm.

Lets start by taking the array elements.

How to choose Pivot?

Picking a good pivot is necessary for the fast implementation of quicksort. However, it is typical to determine a good pivot. Some of the ways of choosing a pivot are as follows -

• Pivot can be random, i.e. select the random pivot from the given array.

• Pivot can be the first element of the given array.

• Pivot can be the second element of the given array.

• Pick median as the pivot.

Lets proceed towards sorting the array by Quick Sort

In the given array figure 1 we have to consider the left most index as Start and the right most index as End. We are taking the left most index as our pivot.

So we got

a[start]=35

a[pivot]=35

a[end]=40

Lets represent them into the given array

We have represented, now just to quick memorize that Quick sort divides a large array into two arrays in which one side i.e. left part hold elements lesser than the pivot and the other side i.e. the right hand part hold elements greater than the pivot.

As our pivot is at start so algorithm will start from End and move towards Start .

Now there are some conditions we have to follow when pivot is at left

• When any element is greater than pivot then End will move forward one position towards Start

• When any element is less than pivot a swap will occur both Pivot and End will get swapped.

In fig 2 a[End] > a[Pivot] i.e. element is greater than pivot which is our case (1) so End will move one position towards Start.

In fig 3 a[End] < a[Pivot] i.e. element is less than pivot which is our case (2) so End and pivot will be swapped.

Let swap both of them.

Now in fig 4: Pivot is at End so algorithm will start form Start and move towards from End

Now there are some conditions we have to follow when pivot is at Right

• When any element is less than pivot then Start will move one position towards End.

• When any element is greater than pivot a swap will occur both Pivot and Start will get swapped.

In fig 4 a[start] < a[Pivot], element is less than pivot so Start will move one position towards End

Now in fig 5 again a[start] < a[pivot] i.e. element is less than pivot so Start will move one position towards End

Here in fig 6 a[start] > a[pivot] i.e. element is greater than pivot so swap will occur both Pivot and Start will get swapped.

As our pivot is at start so algorithm will start from End and move towards Start .

Those condtion will be applicable when Pivot is at start

In fig 7 a[End] > a[Pivot] i.e. element is greater than pivot so End will move one position towards Start

Now in fig 8 a[End] < a[pivot] i.e. element is less than pivot so swap will occur both Pivot and End will get swapped.

Now in fig 9: Pivot is at End so algorithm will start form Start and move towards from End

Same conditions will be applied when Pivot is at End

Here in fig 9 a[start] < a[pivot] i.e. element is less than pivot so Start will move one position towards End

Element 35, which is the pivot element is placed at its exact position.

So our array will represented as given below

Elements that are right side of element 35 are greater than it, and the elements that are left side of element 35 are smaller than it.

Now, in a similar manner, quick sort algorithm is separately applied to the left and right sub-arrays.

After sorting gets done, the array will be -

If you want how the Left and Right sub arrays are sorted click here

As we have learned the working of Quick Sort Lets proceed towards the Pseudo Code.

Pseudo Code Of Quick Sort

We are moving towards the Algorithm of Insertion Sort.

Algorithm of Quick Sort

Quick Sort Program in C

Time Complexity

Now let's see the Time complexity of Quick Sort in Best case, worst case, Average case. We will also be learning about space complexity.

Best Case: In Quick Sort best case occur when the array is already sorted.

Worst Case: Worst Case occurs when we have to sort the array elements in ascending order, but its elements are in descending order.

Average Case: Average Case of Quick Sort occurs when the element are in jumbled order i,e. neither in ascending nor in descending order.

Space Complexity

Advantage of Quick Sort

• Quick sort is the most favored users’ choice to perform sorting functions quickly and efficiently. It allows users to achieve the same result much quicker than other sorting algorithms.

• Quick sort algorithm is faster in an environment like virtual memory, as it manifests good cache locality.

• Quick sort has a space complexity of O(logn), making it a suitable algorithm when you have restrictions in space availability.

Disadvantage of Quick Sort

• One of the biggest disadvantages of Quick Sort is that it can consume a lot of memory when sorting large arrays.

• Quick sort is undoubtedly a fast and efficient sorting algorithm, but when it comes to stability, you might want to reconsider your options. This sorting algorithm is regarded unstable as it does not retain the original order of the key-value pair.

• Major disadvantage occurs when the largest or smallest element is the pivot, or when all the elements are the same size. Both of these worst-case scenarios greatly affect the speed of the quick sort.

When to use Quick Sort

• The sorting algorithm is used for information searching and as Quicksort is the fastest algorithm so it is widely used as a better way of searching.

• Quicksort is a cache-friendly algorithm as it has a good locality of reference when used for arrays.

• If data is sorted then the search for information became easy and efficient

Conclusion

So far our Insertion Sort article comes to an end but before ending we just conclude what are the things that we have learned today.

To conclude, it can be said that

• Quick Sort method sorts the elements using the Divide and Conquer approach and has an average O(nLogn) complexity

• In quicksort , we repeatedly divide the array into smaller sub arrays until there is only one element present in they array and sort the array recursively

• Quick sort is the most favored users’ choice to perform sorting functions quickly and efficiently. It allows users to achieve the same result much quicker than other sorting algorithms.