No Stack to Fullstack Blogs

QUICK SORT

Introduction

Quick Sort divides the array(or given data structure) into two partition recursively and does in place sorting while forming partition. It doesn't require any extra storage as it does in place sorting.

For every partition, a pivot is selected such that this pivot in bought to a point(somewhere in the middle) such that the elements on the left side of this pivot are lesser than it and the elements on the right side of the pivot are greater than it.

This algorithm falls under Divide & Conquer Technique which is divides the problem, finds the solution to smaller problem and then merges these to get the solution to the original problem. Let's look at the working of this algorithm.

Working Procedure

Do refer the code available the end of this section to understand the following theory.

Consider an array,arr of n elements. Let start be the starting index and end be the ending index.
Quick Sort:
1. Recursion calls will be made if there exist more than one element in the array.
2. Find the partition p, using partition function.
3. Make the first recursive call from start to p-1.
4. Make the second recursive call from p+1 to end.
Partition Function:
1. Let the last element be the pivot, pivot=arr[end](You can select any element as your pivot) and pIndex=start(you will understand the need of this variable at the last step).
2. Loop from start to end-1.
3. If arr[i] < pivot then swap arr[pIndex] & arr[i] and increment pIndex. This step essentially makes all the elements on left side of pIndex to be lesser than pivot and right side of pIndex to be greater than the pivot.
4. After the loop, swap arr[pIndex] and arr[end]. This brings our pivot(which was selected as the last element at the point where the partition is to be made).
5. Return pIndex(this will be the index where the partition has to be made for further recursive calls).

Time Complexity

PS: We give random inputs because the no. of input will generally be 100 or 1000 to find the time complexity and manually giving so many inputs is cumbersome work.

There exists two recursive calls in which the elements gets partitioned in each call. The basic operation in this algorithm is the comparison between at step 3.3 in the above working procedure. So increment the count variable above this if condition to get the count of no. of times the basic operation has been performed.

Time Complexity: θ(nlog(n))

Code file

Please open this in your pc or with a compatible app in your mobile.

C++ Implementation for QUICK SORT

That's it from this blog post. If you liked it then do share this blog with your friends or people who wanna get into programming world. Thank You!