What is Quick Sort | Algorithm | Complexity
What is Quick Sort in DAA
Quick Sort is the technique which comes under the divide and conquer. It is a sorting technique or algorithm that works by partitioning or dividing the array seeing pivot(priority) element.
The pivot element is the chosen randomly or arbitrarily. The algorithm then recursively sorts the smaller and larger sub-array or list on either side of the prior/pivot element.
Steps of Quick Sort:-
Example 1
35 | 55 | 20 | 18 | 28 |
Solution:-
Step 1: Take the first or 0th index element as the pivot/priority element
35 | 55 | 20 | 18 | 28 |
Pivot Element |
Step 2: Take the greater number from left to right which is greater than pivot element which is represented by “p”. And take the smaller number from right to left which is smaller than pivot element which is represented by “q”.
--------------Left To Right (Greater)-------->
35 | 55 | 28 | 18 | 20 |
Pivot Element |
P q
<-------------Right To Left (Smaller)--------
Note:- A) When the ‘p’ and ‘q’ is separat == “Replace the the position of the ‘p’ and ‘q’ ”. B) When the ‘p’ and ‘q’ is cross each other == “Interchange the place of the ‘q’ with pivot element”. C) When the ‘q’ is equal to pivot element == “Check the number it must be in series. If it is not then there is error in series. If the series in series then stay at it is.” |
Step 3: Repeat the step 2 until sort……(Remember the Note)
--------------Left To Right (Greater)-------->
35 | 20 | 28 | 18 | 55 |
Pivot Element |
↓ ↓
q <---> p
<-------------Right To Left (Smaller)--------
--------------Left To Right (Greater)-------->
18 | 20 | 28 | 35 | 55 |
Pivot Element |
↓
p
<-------------Right To Left (Smaller)--------
Step 4: See the Array / List whether it is all series or continue then it is your final Sort …..as shown in this figure….
18 | 20 | 28 | 35 | 55 |
Fig . Quick Sort
Quick Sort Algorithm
------> Partition(A, left index, right index)
{
X = A[left index]
L = left index
For j = left index +1 to right index
{
If A[j] <= X then,
i = i+1
Exchange A[i] <----> A[j]
}
Exchange A[left index] <----> A[i]
return i
}
Quick_Sort(A, left index, right index)
{
If left index < right index
then,
Pivot index = Partition(A,left index,right index)
Quick_Sort(A, left index, pivot index - 1)
Quick_Sort(A, pivot index + 1, right index)
}
Complexity
-----> 0(n log n).
Example 1:
35 | 50 | 15 | 25 | 80 | 20 | 90 | 45 |
Example 2:
45 | 35 | 15 | 55 | 75 | 90 | 40 | 65 | 99 | 25 | 88 |
...............................................For Solution stay tuned (First try it by yourself).........................
Solutions: {Soon...}