Quick Sort

CSE231: Algorithms
Md. Ferdouse Ahmed Foysal
Quick Sort

• QuickSort is a sorting algorithm based on the Divide and Conquer that picks an
element as a pivot and partitions the given array around the picked pivot by placing
the pivot in its correct position in the sorted array.

Quick Sort CSE231: Algorithms 1

How does QuickSort Algorithm work?

1. Choose a pivot
2. Partition the array around pivot. After partition, it is ensured that all elements are
smaller than all right and we get index of the end point of smaller elements. The left
and right may not be sorted individually.
3. Recursively call for the two partitioned left and right subarrays.
4. We stop recursion when there is only one element is left

Quick Sort CSE231: Algorithms 2

Choice of Pivot

• Always pick the first (or last) element as a pivot. The below implementation is picks
the last element as pivot. The problem with this approach is it ends up in the worst
case when array is already sorted.
• Pick a random element as a pivot. This is a preferred approach because it does not
have a pattern for which the worst case happens.
• Pick the median element is pivot. This is an ideal approach in terms of time
complexity as we can find median in linear time and the partition function will
always divide the input array into two halves. But it is low on average as median
finding has high constants.

Quick Sort CSE231: Algorithms 3

Quick Sort Algorithm

1. Make the right-most index value pivot

2. Partition the array using pivot value
3. Quicksort left partition recursively
4. Quicksort right partition recursively

Quick Sort CSE231: Algorithms 4

Quick Sort Pivot Algorithm

1. Choose the highest index value has pivot

2. Take two variables to point left and right of the list
excluding pivot
3. Left points to the low index
4. Right points to the high
5. While value at left is less than pivot move right
6. While value at right is greater than pivot move left
7. If both step 5 and step 6 does not match swap left and right
8. If left ≥ right, the point where they met is new pivot

Quick Sort CSE231: Algorithms 5

Step-1.1 i j P

14 22 1 46 6 10 27 Low=0, high=6
0 1 2 3 4 5 6 i=low-1, P = a[high]
P
i=-1, j=0, P=27
i j
a[j] < P
14 < 27, True, i++, i= 0
Swap (a[i],a[j])
14 22 1 46 6 10 27
0 1 2 3 4 5 6

Quick Sort CSE231: Algorithms 6

Step-1.2 i j P

14 22 1 46 6 10 27
0 1 2 3 4 5 6 i=0, j=1, P=27
i j P a[j] < P
22 < 27, True, i++, i= 1
Swap ( a[i], a[j] )
14 22 1 46 6 10 27
0 1 2 3 4 5 6

Quick Sort CSE231: Algorithms 7

Step-1.3 i j P

14 22 1 46 6 10 27
0 1 2 3 4 5 6 i=1, j=2, P=27
i j P a[j] < P
1 < 27, True, i++, i= 2
Swap ( a[i], a[j] )
14 22 1 46 6 10 27
0 1 2 3 4 5 6

Quick Sort CSE231: Algorithms 8

Step-1.4 i j P

14 22 1 46 6 10 27
0 1 2 3 4 5 6 i=2, j=3, P=27
i j P a[j] < P
46 < 27, False – No change

14 22 1 46 6 10 27
0 1 2 3 4 5 6

Quick Sort CSE231: Algorithms 9

Step-1.5 i j P

14 22 1 46 6 10 27
0 1 2 3 4 5 6 i=2, j=4, P=27
i j P a[j] < P
6 < 27, True, i++, i= 3
Swap ( a[i], a[j] )
14 22 1 46 6 10 27
0 1 2 3 4 5 6
i j P

14 22 1 6 46 10 27
0 1 2 3 4 5 6

Quick Sort CSE231: Algorithms 10

 i j P
Step-1.6

14 22 1 6 46 10 27
0 1 2 3 4 5 6 i=3, j=5, P=27
i j P a[j] < P
10< 27, True, i++, i= 4
Swap ( a[i], a[j] )
14 22 1 6 46 10 27
0 1 2 3 4 5 6
i j P

14 22 1 6 10 46 27
0 1 2 3 4 5 6

Quick Sort CSE231: Algorithms 11

 i j P
Step-1.7

14 22 1 6 10 46 27
0 1 2 3 4 5 6 i=4, high = 6
i j P
Swap( a[i+1] , a[high] )
Swap (a[5], a[6])
14 22 1 6 10 27 46
0 1 2 3 4 5 6

14 22 1 6 10 27 46
0 1 2 3 4 5 6

Quick Sort CSE231: Algorithms 12

Step-2.1 i j P

14 22 1 6 10 27 46 Low=0, high=4
0 1 2 3 4 5 6 i=low-1, P = a[high]
i j P
i=-1, j=0, P=10
a[j] < P
14 < 10, False – No Change
14 22 1 6 10 27 46
0 1 2 3 4 5 6

Quick Sort CSE231: Algorithms 13

Step-2.2 i j P

14 22 1 6 10 27 46
0 1 2 3 4 5 6
i=-1, j=1, P=10
i j P a[j] < P
22 < 10, False – No Change

14 22 1 6 10 27 46
0 1 2 3 4 5 6

Quick Sort CSE231: Algorithms 14

Step-2.3 i j P

14 22 1 6 10 27 46
0 1 2 3 4 5 6
i=-1, j=2, P=10
i j P a[j] < P
1 < 10, True, i++, i= 0
Swap ( a[i], a[j] )
14 22 1 6 10 27 46
0 1 2 3 4 5 6
i j P

1 22 14 6 10 27 46
0 1 2 3 4 5 6
Quick Sort CSE231: Algorithms 15
Step-2.4 i j P

1 22 14 6 10 27 46
0 1 2 3 4 5 6
i=0, j=3, P=10
i j P a[j] < P
6 < 10, True, i++, i= 1
Swap ( a[i], a[j] )
1 22 14 6 10 27 46
0 1 2 3 4 5 6
i j P

1 6 14 22 10 27 46
0 1 2 3 4 5 6
Quick Sort CSE231: Algorithms 16
Step-2.5 i j P

1 6 14 22 10 27 46
0 1 2 3 4 5 6 i=1, high = 4
i j P
Swap( a[i+1] , a[high] )
Swap (a[2], a[4])
1 6 10 22 14 27 46
0 1 2 3 4 5 6

1 6 10 22 14 27 46
0 1 2 3 4 5 6
Quick Sort CSE231: Algorithms 17
 i j P
Step-3.1

1 6 10 22 14 27 46
0 1 2 3 4 5 6
Low=0, high=1
i=low-1, P = a[high]
i j P
i=-1, j=0, P=6
a[j] < P
1 < 6, , True, i++, i= 0
1 6 10 22 14 27 46 Swap ( a[i], a[j] )
0 1 2 3 4 5 6

Quick Sort CSE231: Algorithms 18

Step-3.2 j i P

1 6 10 22 14 27 46
0 1 2 3 4 5 6 i=0, high = 1
i j P
Swap( a[i+1] , a[high] )
Swap (a[1], a[1])
1 6 10 22 14 27 46
0 1 2 3 4 5 6

1 6 10 22 14 27 46
0 1 2 3 4 5 6
Quick Sort CSE231: Algorithms 19
Step-4.1 i j P

1 6 10 22 14 27 46
0 1 2 3 4 5 6
Low=0, high=0
i=low-1, P = a[high]
i jP
i=-1, j=0, P=1
a[j] < P
1 < 1, False – No change
1 6 10 22 14 27 46
0 1 2 3 4 5 6 i=-1, high = 0

Swap( a[i+1] , a[high] )

Swap (a[0], a[0])
1 6 10 22 14 27 46
0 1 2 3 4 5 6
Quick Sort CSE231: Algorithms 20
Step-5.1 i j P

1 6 10 22 14 27 46
0 1 2 3 4 5 6
Low=3, high=4
i=low-1, P = a[high]
i j P
i=2, j=3, P=14
a[j] < P
22 < 14, False – No change
1 6 10 22 14 27 46
0 1 2 3 4 5 6

Quick Sort CSE231: Algorithms 21

Step-5.2 i j P

1 6 10 22 14 27 46
0 1 2 3 4 5 6
i j P i=2, high = 4

Swap( a[i+1] , a[high] )

1 6 10 14 22 27 46 Swap (a[3], a[4])

0 1 2 3 4 5 6

1 6 10 14 22 27 46
0 1 2 3 4 5 6
Quick Sort CSE231: Algorithms 22
Step-6.1 i jP

1 6 10 14 22 27 46
0 1 2 3 4 5 6
Low=4, high=4
i=low-1, P = a[high]
i j P
i=3, j=4, P=22
a[j] < P
22 < 22, False – No change
1 6 10 14 22 27 46
0 1 2 3 4 5 6 i=3, high = 4

Swap( a[i+1] , a[high] )

Swap (a[4], a[4])
1 6 10 14 22 27 46
0 1 2 3 4 5 6
Quick Sort CSE231: Algorithms 23
Step-7.1 i j P

1 6 10 14 22 27 46
0 1 2 3 4 5 6
Low=6, high=6
i=low-1, P = a[high]
i j P
i=5, j=6, P=46
a[j] < P
46 < 46, False – No change
1 6 10 14 22 27 46
0 1 2 3 4 5 6 i=5, high = 6

Swap( a[i+1] , a[high] )

Swap (a[6], a[6])
1 6 10 14 22 27 46
0 1 2 3 4 5 6
Quick Sort CSE231: Algorithms 24
Quick Sort Pseudocode
procedure quickSort(left, right)
if right-left <= 0
return
else
pivot = A[right]
partition = partitionFunc(left, right, pivot)
quickSort(left,partition-1)
quickSort(partition+1,right)
end if
end procedure

Quick Sort CSE231: Algorithms 25

Quick Sort Pivot Pseudocode
function partitionFunc(left, right, pivot)
leftPointer = left
rightPointer = right - 1

while True do
while A[++leftPointer] < pivot do
//do-nothing
end while

while rightPointer > 0 && A[--rightPointer] > pivot do

//do-nothing
end while

if leftPointer >= rightPointer

break
else
swap leftPointer,rightPointer
end if
end while

swap leftPointer,right
return leftPointer
end function

Quick Sort CSE231: Algorithms 26

Code #include <bits/stdc++.h>
using namespace std;
// The QuickSort function implementation
void quickSort(vector<int>& arr, int low, int high) { int partition(vector<int>& arr, int low, int high) {

if (low < high) { // Choose the pivot

int pivot = arr[high];
// pi is the partition return index of pivot
int pi = partition(arr, low, high); // Index of smaller element and indicates
// the right position of pivot found so far
// Recursion calls for smaller elements int i = low - 1;
// and greater or equals elements
quickSort(arr, low, pi - 1); // Traverse arr[;ow..high] and move all smaller
quickSort(arr, pi + 1, high); // elements on left side. Elements from low to
} // i are smaller after every iteration
} for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
int main() { i++;
vector<int> arr = {10, 7, 8, 9, 1, 5}; swap(arr[i], arr[j]);
int n = [Link](); }
quickSort(arr, 0, n - 1); }
cout << "Sorted Array\n";
for (int i = 0; i < n; i++) { // Move pivot after smaller elements and
cout << arr[i] << " "; // return its position
} swap(arr[i + 1], arr[high]);
return 0; return i + 1;
} }

Quick Sort CSE231: Algorithms 27

Complexity

• Time Complexity: O(n^2)

Quick Sort CSE231: Algorithms 28

Reference

• [Link]
• [Link]

Quick Sort CSE231: Algorithms 29

Thank You