## Quick Sort-

• Quick Sort is a famous sorting algorithm that sorts the given data items in ascending order.
• This sorting algorithm uses the idea of divide and conquer approach.

## How Quick Sort works?

• Quick Sort follows a recursive algorithm.
• It divides the given array into two sections using a partitioning element called as pivot in such a way that all the elements to the left side of pivot are smaller than pivot and all the elements to the right side of pivot are greater than pivot.
• After dividing the array into two sections, the pivot is set at its correct position.
• Then, sub arrays are sorted separately by applying quick sort algorithm recursively.

## Quick Sort Algorithm-

Partition_Array (a , beg , end , loc)

where-

a = Linear Array in memory

beg = Lower bound of the sub array in question

end = Upper bound of the sub array in question

Begin

Set left = beg , right = end , loc = beg

Set done = false

While (not done) do

While ( (a[loc] <= a[right] ) and (loc ≠ right) ) do

Set right = right – 1

end while

if (loc = right) then

Set done = true

else if (a[loc] > a[right]) then

Interchange a[loc] and a[right]

Set loc = right

end if

if (not done) then

While ( (a[loc] >= a[left] ) and (loc ≠ left) ) do

Set left = left + 1

end while

if (loc = left) then

Set done = true

else if (a[loc] < a[left]) then

Interchange a[loc] and a[left]

Set loc = left

end if

end if

end while

End

## Example of Quick Sort-

Let us sort the following array in ascending order using quick sort- ### Step-01:

Initially-

• Left and Pivot points to the first element of the array
• Right points to the last element of the array

So, to begin with, we set loc = 0, left = 0 and right = 5 as- ### Step-02:

As pivot is pointing at left, so we will start from right and move towards left.

Since, a[loc] < a[right], so we will move right one position towards left as- ### Step-03:

As pivot is pointing at left, so we will start from right and move towards left.

Since, a[loc] > a[right], so we will swap pivot and right as- ### Step-04:

As pivot is pointing at right, so we will start from left and move towards right.

Since, a[loc] > a[left], so we will move left one position towards right as- ### Step-05:

As pivot is pointing at right, so we will start from left and move towards right.

Since, a[loc] > a[left], so we will move left one position towards right as- ### Step-06:

As pivot is pointing at right, so we will start from left and move towards right.

Since, a[loc] < a[left], so we will swap pivot and left as- ### Step-07:

As pivot is pointing at left, so we will start from right and move towards left.

Since, a[loc] < a[right], so we will move right one position towards left as- ### Step-08:

As pivot is pointing at left, so we will start from right and move towards left.

Since, a[loc] > a[right], so we will swap pivot and right as- ### Step-09:

As pivot is pointing at right, so we will start from left and move towards right.

Since, a[loc] > a[left], so we will move left one position towards right as- Since, left becomes equal to loc, it indicates the termination of procedure.

The pivot element 25 is placed in its final position as all elements to the right side of pivot are greater than pivot and all elements to the left side of pivot are smaller than pivot. Pivot divides the array into two sub arrays. Now, we apply Quick Sort on the left and right sub arrays separately in the similar manner.

## Analysis of Quick Sort-

• To find the location of an element that splits the array into two parts, we need O(n) operations since every element in the array is compared to the partitioning element.
• After the division, each section is examined separately. If the array is split approximately in half (which is not usually), then there will be log2n splits.
• Therefore, total comparisons required are f(n) = n x log2n = O(nlog2n)

 Order of Quick Sort = O(nlog2n)

## Worst Case-

• Quick Sort is sensitive to the order of the input data and it gives the worst performance when elements are already in the ascending order.
• It then divides the array into sections of 1 and (n-1) elements in each call.
• Then, there will be (n-1) divisions in all.
• Therefore, here total comparisons required are f(n) = n x (n-1) = O(n2)

 Order of Quick Sort in worst case = O(n2)

## Advantages of Quick Sort-

• Quick Sort is an in-place sort that needs no temporary memory.
• Quick Sort is typically faster than other algorithms because its inner loop can be efficiently implemented on most architectures.
• Quick Sort tends to make excellent usage of the memory hierarchy like virtual memory or caches.
• Quick Sort can be easily parallelized due to its divide and conquer nature.

## Disadvantages of Quick Sort-

• The worst case complexity of quick sort is O(n2) which is worse than the O(nlogn) worst case complexity of algorithms like merge sort, heap sort etc.
• It is not a stable sort i.e. the order of equal elements may not be preserved.

Get more notes and other study material of Design and Analysis of Algorithms (DAA).

Watch video lectures by visiting our YouTube channel LearnVidFun.