quick sort in data structure

Quick Sort In Data Structure

Hello Friends, In this blog, I am going to let you know about a very interesting sorting technique or algorithm which is known as Quick Sort.

When you will read or go through this quick sort then you will find it a bit tricky sorting technique where you need to remember a few rules to complete all the procedures during this quick sort.

This quick sort is based on divide and conquers technique, where we divide a given list into sublists by following a procedure. And by dividing the list into sublist we sort out the whole list and finally, we get a sorted list using quicksort.

When you or especially students will read this quick sort for the very first time then they might get it difficult to understand better as this quick sort has some tricky approach to sort the list.

But here we will explain to you in a very simple way that how to sort a list using Quick sort.

For understanding the quick sort, you just need to follow the below-given procedure step by step.

suppose you have given a list to sort out using quick sort technique:

44 23 76 84 87 72 36

Then the very first thing you need to do is just do the naming for a few specific elements of the list like given below.

quick sort1
quick sort1

Here the first element is marked as low and this is also our pivot element which will be the center of the list partition.

The last element is marked as high and that will also be known as the left element.

Now see a few simple rules to sort out the list below.

if right < low then move the right handle one position forward towards high.
if left > low then you need to move left handle one position forward towards low.

So the basis of the above condition we need to move our right and left handle across the list. Now see below more conditions for swapping the elements of the list.

When there is no movement in right and left handle or both the above-given conditions are false then we need to swap the right and left element. and we also move the right and left handle towards their moving direction.

We repeat this process until the right and left handle crosses each other. And once they cross each other or we also denote this as right > left (here we do not compare the value it is just crossing the left and right handle) then we swap left and low element.

Now we see the position of our pivot element, in this case, we have 44 as our pivot element. and we divide the list into sublist by assuming our pivot as our divide point, as you will always find that left side elements of the pivot will be less than the pivot and right side elements will be greater than a pivot.

So we get two sublists again and with the same procedure, we again start sorting out the list.

See an example given below with the same list elements given above.

quick sort2
quick sort2
quick sort3
quick sort3

swap a[right] and a[left] and move right and left

quick sort4
quick sort4
quick sort5
quick sort5
quick sort6
quick sort6
quick sort7
quick sort7

Since right > left, so swap a[left] and a[low]

36 23 44 84 87 72 76

low
36 23 44 84 87 72 76

At this point 44 is at its proper place, and the list is divided into two parts,
which will also be sorted using the same procedure

quick sort8
quick sort8

Since right = left, so swap a[left] and a[low].

{23 36}

At this point 36 is at proper place and the list contains only a single element,
so further sorting is not required in this part.

quick sort9
quick sort9

swap a[right] and a[left] and move right and left further.

quick sort10
quick sort10
quick sort11
quick sort11

Since right > left, so swap a[left] and a[low]

72 76 84 87

At this point 84 is at its proper place. And the list is divided into two parts {72 76} and {87}.
The second list contains only a single element, its sorting is not required, First part is now to be sorted below using Quick Sort.

quick sort12
quick sort12

Since, right = left, so we need to swap a[low] and a [left], but here 72 is at its proper place, so we will not swap here. And here we get only one list that contains only one single element {76}, so no further sorting required here.

{72 76}

Hence the resulted sorted list is as follows using Quick Sort

23 36 44 72 76 84 87

In the case of any queries, you can write to us at a5theorys@gmail.com we will get back to you ASAP.

Hope! you would have enjoyed this post about Quick Sort.

Please feel free to give your important feedbacks in the comment section below.

Have a great time! Sayonara!