quicksort algorithm | Quicksort algorithm in daa - InTerestinG321

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



No comments:

Post a Comment