How do Quick Sort works?

Share

In this blog post, you will learn about how the quick sort works and its implementation in the C program.

Quick sort is a sorting algorithm that is based on the divide and conquer approach which means the problem is divided into smaller parts ( sub-problem) and we solve it and finally combine all the solutions.

In quick sort what we do is,

We select a pivot position and divide the array into sub-array in such order, that the elements in its left direction are smaller and in the right direction are greater. The left and right subarrays are also divided using the same approach. This process continues until each subarray contains a single element. At this point, elements are already sorted. Finally, elements are combined to form a sorted array.

Working Mechanism

For example, we have an array a[5] = [7, 9, 6, 10, 3, 2]

  1. Select a pivot position

There are different variations of quicksort where the pivot element is selected from different positions. Here, we will be selecting the leftmost element of the array as the pivot element.

Down: A pointer set in an array that moves toward the right-hand side and stops once it finds an element greater than the pivot element.

Up: A pointer set in an array that moves toward the left-hand side and stops once it finds an element smaller than or equal to the pivot element.

2. Rearranging the array

At the point when the up and down pointer stops moving, we check two conditions:

  • if down index is smaller than up index, we swap a[down] and a[up].
  • if down index is greater, which means the pointers crosses each other or equal to, we swap a[pivot] and a[up]

After the first pass, a[5] = [7,2,6,10,3,2]

2nd pass: a[5] = [7,2,6,3,10,9]

After the first pass, again the pointers start to move. at this point, the down pointer reaches a[3], and the up pointer reaches a[4]. here down < up, so we swap a[down] with a[up].

3rd pass: a[5] = [3,2,6,7,10,9]

Again the process continues to find the right place for the pivot element. now the down pointer reaches a[4] and the up pointer reaches a[3]. here down > up, so we swap a[pivot] and a[up].

Pivot elements are again chosen for the left and the right sub-parts separately. And, step 2 is repeated. The process continues until each sub arrays have a maximum of single elements. at this point, the array is already sorted.

C program for quick sort & online compiler: https://www.onlinegdb.com/hCdYp0Hb7

Note : DSA Quick Sort Notes

Share
Sudeep Mishra

Sudeep Mishra

Healing

Leave a Reply

Your email address will not be published.

%d bloggers like this: