quicksort algorithm | Quicksort algorithm in daa

Quicksort is a type of sorting algorithm, quicksort algorithm is based on divide and conquers approach, In this article, i will explain quicksort algorithm with example.

ALGORITHM:

 Quicksort(a[l..r])

//Sorts a subarray by quicksort

//Input: Subarray  A[0….n-1], defined by its left and right

// indices l and r

//Output: Subarray A[l..r] sorted order

if l < r

S ←Partition(A[l..r]) //s is a split position

Quicksort(A[l..s − 1])

Quicksort(A[s + 1..r])

Solving Quicksort problem There are 4 condition:

1. A [P] > i

2. A [P] < j

3. if (a<j)

                  Swap A[i] and A[j]

Else

4. Swap A[j] and A[p]

Example:

                                                    

                                                     5  2  1  6

 Pivot element is = 5

I is = 5

J is = 6

P is a Pivot element

i position is 0

j position is n-1

First check the first condition  [A [i] > p] i++

Initially I position is zero

For ex  :

[A [5] > 5]   “Condition False” i++

[A [5] > 2]    “Condition False” i++

[A [5] > 1]  “Condition False” i++

[A [5] > 6]   “True” stop incrementing

Second condition  [A [p] <  j]  j—

Initially j position is n-1

[A [6] < 5]   “False” j—

[A [1] < 5] “true” stop decrementing

Check  “if(i<j)”  Swap [A [i] and A [j] ]

(6 < 1) “False”

Else

Swap [A [j] and A[p]]

Now it becomes

                           1  2  5  6

The Same rule applied for all the problem of the quicksort. I hope you should understand correctly if you face any problem the comment in the comment section