DATA STRUCTURE
QUICK SORT
Hina Nawaz
QUICK SORT
Quick Sort follows the divide and conquer
approach.
Divide and conquer is a technique of breaking
down the algorithms into sub problems, then
solving the sub problems, and combining the
results back together to solve the original
problem
QUICK SORT
1) An array is divided into subarrays by selecting
a pivot element (element selected from the
array).
While dividing the array, the pivot element
should be positioned in such a way that
elements less than pivot are kept on the left
side and elements greater than pivot are on the
right side of the pivot.
QUICK SORT
2) The left and right subarrays are also divided
using the same approach. This process
continues until each subarray contains a single
element.
3) At this point, elements are already sorted.
Finally, elements are combined to form a sorted
array.
QUICK SORT
5 3 7 6 1 2 4
QUICK SORT
5 3 7 6 1 2 4
left right
Pointing to 1st element Pointing to last element
QUICK SORT
pivot
5 3 7 6 1 2 4
left right
All element to the RIGHT of pivot be GREATER than pivot.
All element to the LEFT of pivot be SMALLER than pivot.
QUICK SORT
pivot
5 3 7 6 1 2 4
left right
As the pivot is pointing at right. So we will start from left
QUICK SORT i = left - 1
i= -1
j pivot
5 3 7 6 1 2 4
left right
J < Pivot
5<4 F
QUICK SORT i = left - 1
i= -1
j pivot
5 3 7 6 1 2 4
left right
J < Pivot
3<4 T
QUICK SORT i = left - 1
i= -1
j pivot
5 3 7 6 1 2 4
left right
Condition is true
Increment I
Swap value of i with j
QUICK SORT i = -1 + 1
i= 0
i j pivot
5 3 7 6 1 2 4
left right
Condition is true
Increment I
Swap value of i with j
QUICK SORT i = -1 + 1
i= 0
i j pivot
3 5 7 6 1 2 4
left right
QUICK SORT i = -1 + 1
i= 0
i j pivot
3 5 7 6 1 2 4
left right
J < Pivot
7<4 F
QUICK SORT i = -1 + 1
i= 0
i j pivot
3 5 7 6 1 2 4
left right
J < Pivot
6<4 F
QUICK SORT i = -1 + 1
i= 0
i j pivot
3 5 7 6 1 2 4
left right
J < Pivot
1<4 T
QUICK SORT i = -1 + 1
i= 0
i j pivot
3 5 7 6 1 2 4
left right
Condition is true
Increment I
Swap value of i with j
QUICK SORT i=0+1
i= 1
i j pivot
3 5 7 6 1 2 4
left right
Condition is true
Increment I
Swap value of i with j
QUICK SORT i= 1
i j pivot
3 1 7 6 5 2 4
left right
QUICK SORT i=1
i j pivot
3 1 7 6 5 2 4
left right
J < Pivot
2<4 T
QUICK SORT i=1
i j pivot
3 1 7 6 5 2 4
left right
Condition is true
Increment I
Swap value of i with j
QUICK SORT i=1+1
i=2
i j pivot
3 1 7 6 5 2 4
left right
Condition is true
Increment I
Swap value of i with j
QUICK SORT i=1+1
i=2
i j pivot
3 1 2 6 5 7 4
left right
QUICK SORT i=1+1
i=2
i j pivot
3 1 2 6 5 7 4
left right
End for
swap arr[i + 1] with arr[right]
QUICK SORT i=2
i i+1 j pivot
3 1 2 6 5 7 4
left right
End for
swap arr[i + 1] with arr[right]
QUICK SORT i=2
i i+1 j pivot
3 1 2 4 5 7 6
left right
End for
swap arr[i + 1] with arr[right]
QUICK SORT
3 1 2 4 5 7 6
0 1 2 3 4 5 6
QUICK SORT
3 1 2 4 5 7 6
QUICK SORT
pIndex = 3
4
Quick Sort Quick Sort
3 1 2 5 7 6
0 1 2 4 5 6
ALGORITHM
Quicksort(array, left, right)
if (left < right)
pIndex = Partition(A, left, right)
Quicksort(A,start,pIndex-1)
Quicksort(A,pIndex+1, right)
ALGORITHM
partition (array, left, right)
{
pivot = arr[right]; // Setting rightmost Index as pivot
i = (left - 1) // Index of smaller element and indicates the
// right position of pivot found so far
for j = left to j <= right- 1
{
if (arr[j] < pivot) // If current element is smaller than the pivot
{
i++; // increment index of smaller element
swap arr[i] with arr[j]
}
}
swap arr[i + 1] with arr[right])
return i + 1
}
TIME COMPLEXITY
pivot
O(n)
n1 n2
n1 n2
T(n) = T(n1) + T(n2) + cn
TIME COMPLEXITY
Best Case
The best-case occurs when the pivot element is
the middle element or near to the middle
element.
TIME COMPLEXITY
Best Case
n/2 n/2
n/4 n/4 n/4 n/4
TIME COMPLEXITY
Best Case
T(n) = T(n/2) + T(n/2) + n
= 2T(n/2)+n
= n log n
TIME COMPLEXITY
Average Case
It occurs when the array elements are in jumbled order
that is not properly ascending and not properly
descending.
TIME COMPLEXITY
Worst Case
In quick sort, worst case occurs when the pivot
element is either greatest or smallest element.
1 2 3 4 5 6
TIME COMPLEXITY
Worst Case
pivot
1 2 3 4 5 6
pivot
1 2 3 4 5 6
TIME COMPLEXITY
Worst Case
0 n-1
0 n-2
.
.
1
TIME COMPLEXITY
Worst Case
T(n) = T(n1) + T(n2) + cn
= 0 + T(n-1)+n
O(n2)
TIME COMPLEXITY
Best Case:
O(n*log n)
Worst Case:
O(n2)
Average Case:
O(n*log n)
