What is Quick Sort?

[aastha]

What is Quick Sort?

[aastha]

Quick sort is a sorting algorithm used to sort elements of an array. Quick sort make use of a pivot which is selected using randomized selection or constrained selection and sort the array in reference with the pivot element. All the elements which are smaller in value than pivot element is placed at right of the pivot and all elements greater than pivot are placed at right of pivot hence placing pivot at correct position (position at which pivot element would be present if the array was sorted).

Quick sort uses divide and conquer approach.

Selection of pivot: –
• Last element is selected as pivot.
• First element is selected as pivot.
• Pivot is selected at random.
• Pivot is selected as median of the array.

Steps involved: –
Array-A, Size- n, i= iterator to separate element larger and smaller than pivot, j= iterator to travers

1. Set i= A[0], j= A[1], swap pivot element with first element.
2. If (A[1]< pivot)
i++, j++.
else j++
3. while (j! = n-1)
if(A[j]< pivot)
swap(A[i+1], A[j])
i++, j++
else j++
4. swap(A[0], A[i]) //to move pivot to its exact position.
5. Recurs Step 1,2,3,4 on subarrays A1 and A2
Where A1= array of elements on left of pivot.
A2= array of elements on right of pivot.

Time Complexity

1. Best Case
Best case of quick sort occurs when pivot is selected as the middle element of the array. As problem size is decreased by a factor of 2.
Therefore,
T(n)= 2T(n/2) + cn
So complexity of algorithm is of the order O(nlog(n)) (by Master Method ).

2. Worst Case
Worst case of quick sort occurs when pivot is selected as either the smallest or the largest elements in the array. As size of the array will decrease by 1 unit and each recursive call will have n-1 elements to sort.
So, complexity of algorithm is of the order O(n2).

[Author]

Posts