Scribd
Upload
3 views57 pages

Quicksort Algorithm Explained

The document outlines the Quicksort algorithm, which sorts an array by selecting a pivot and partitioning the array into sub-arrays based on the pivot value. It describes the process of picking a pivot, partitioning the array, and recursively sorting the sub-arrays. The document includes examples and detailed steps for implementing the algorithm.

Uploaded by

shivendra
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
3 views57 pages

Quicksort Algorithm Explained

The document outlines the Quicksort algorithm, which sorts an array by selecting a pivot and partitioning the array into sub-arrays based on the pivot value. It describes the process of picking a pivot, partitioning the array, and recursively sorting the sub-arrays. The document includes examples and detailed steps for implementing the algorithm.

Uploaded by

shivendra
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Quicksort Algorithm

Given an array of n elements (e.g.,


integers):
If array only contains one element, return
else
pick one element to use as pivot.
Partition elements into two sub-arrays:
 Elements less than or equal to pivot
 Elements greater than pivot

Quicksort two sub-arrays


Return results
06/04/25 Lijo V.P 13600 SCSE VIT
Example
We are given array of n integers to sort:

40 20 10 80 60 50 7 30 100

06/04/25 Lijo V.P 13600 SCSE VIT


Pick Pivot Element
There are a number of ways to pick the pivot
element. In this example, we will use the first
element in the array:
40 20 10 80 60 50 7 30 100

06/04/25 Lijo V.P 13600 SCSE VIT


Partitioning Array
Given a pivot, partition the elements of the
array such that the resulting array
consists of:
1. One sub-array that contains elements >=
pivot
2. Another sub-array that contains elements <
pivot

Sort sub arrays separately and merge them


to get original array.

06/04/25 Lijo V.P 13600 SCSE VIT


pivot_index = 0 40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index

pivot_index = 0 40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index

pivot_index = 0 40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index

pivot_index = 0 40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index

pivot_index = 0 40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index

pivot_index = 0 40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]

pivot_index = 0 40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]

pivot_index = 0 40 20 10 30 60 50 7 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 60 50 7 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 60 50 7 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 60 50 7 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 60 50 7 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 60 50 7 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 60 50 7 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.

pivot_index = 0 40 20 10 30 7 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.
5. Swap data[small_index] and data[pivot_index]

pivot_index = 0 40 20 10 30 7 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.
5. Swap data[small_index] and data[pivot_index]

pivot_index = 4 7 20 10 30 40 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


7 20 10 30 40 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

<= data[pivot] > data[pivot]

06/04/25 Lijo V.P 13600 SCSE VIT


7 20 10 30 40 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

<= data[pivot] > data[pivot]

06/04/25 Lijo V.P 13600 SCSE VIT


Quicksort Analysis
Assume that keys are random, uniformly
distributed.
What is best case running time?

06/04/25 Lijo V.P 13600 SCSE VIT


Quicksort Analysis
 Assume that keys are random, uniformly
distributed.
 What is best case running time?
 Recursion:
1. Partition splits array in two sub-arrays of size
n/2
2. Quicksort each sub-array

06/04/25 Lijo V.P 13600 SCSE VIT


Quicksort Analysis
 Assume that keys are random, uniformly
distributed.
 What is best case running time?
 Recursion:
1. Partition splits array in two sub-arrays of size
n/2
2. Quicksort each sub-array
 Depth of recursion tree?

06/04/25 Lijo V.P 13600 SCSE VIT


Quicksort Analysis
 Assume that keys are random, uniformly
distributed.
 What is best case running time?
 Recursion:
1. Partition splits array in two sub-arrays of size
n/2
2. Quicksort each sub-array
 Depth of recursion tree? O(log2n)

06/04/25 Lijo V.P 13600 SCSE VIT


Quicksort Analysis
 Assume that keys are random, uniformly
distributed.
 What is best case running time?
 Recursion:
1. Partition splits array in two sub-arrays of size
n/2
2. Quicksort each sub-array
 Depth of recursion tree? O(log2n)
 Number of accesses in partition?

06/04/25 Lijo V.P 13600 SCSE VIT


Quicksort Analysis
 Assume that keys are random, uniformly
distributed.
 What is best case running time?
 Recursion:
1. Partition splits array in two sub-arrays of size
n/2
2. Quicksort each sub-array
 Depth of recursion tree? O(log2n)
 Number of accesses in partition? O(n)

06/04/25 Lijo V.P 13600 SCSE VIT


Quicksort Analysis
 Assume that keys are random, uniformly
distributed.
 Best case running time: O(n log2n)

06/04/25 Lijo V.P 13600 SCSE VIT


Quicksort Analysis
 Assume that keys are random, uniformly
distributed.
 Best case running time: O(n log2n)
 Worst case running time?

06/04/25 Lijo V.P 13600 SCSE VIT


Quicksort: Worst Case
Assume first element is chosen as pivot.
Assume we get array that is already in order:

pivot_index = 0 2 4 10 12 13 50 57 63 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.
5. Swap data[small_index] and data[pivot_index]

pivot_index = 0 2 4 10 12 13 50 57 63 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.
5. Swap data[small_index] and data[pivot_index]

pivot_index = 0 2 4 10 12 13 50 57 63 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.
5. Swap data[small_index] and data[pivot_index]

pivot_index = 0 2 4 10 12 13 50 57 63 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.
5. Swap data[small_index] and data[pivot_index]

pivot_index = 0 2 4 10 12 13 50 57 63 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.
5. Swap data[small_index] and data[pivot_index]

pivot_index = 0 2 4 10 12 13 50 57 63 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.
5. Swap data[small_index] and data[pivot_index]

pivot_index = 0 2 4 10 12 13 50 57 63 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

big_index small_index

06/04/25 Lijo V.P 13600 SCSE VIT


1. While data[big_index] <= data[pivot]
++big_index
2. While data[small_index] > data[pivot]
--small_index
3. If big_index < small_index
swap data[big_index] and data[small_index]
4. While small_index > big_index, go to 1.
5. Swap data[small_index] and data[pivot_index]

pivot_index = 0 2 4 10 12 13 50 57 63 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]

<= data[pivot] > data[pivot]


06/04/25 Lijo V.P 13600 SCSE VIT
Quicksort Analysis
 Assume that keys are random, uniformly
distributed.
 Best case running time: O(n log2n)
 Worst case running time?
 Recursion:
1. Partition splits array in two sub-arrays:
• one sub-array of size 0
• the other sub-array of size n-1
2. Quicksort each sub-array
 Depth of recursion tree?

06/04/25 Lijo V.P 13600 SCSE VIT


Quicksort Analysis
 Assume that keys are random, uniformly
distributed.
 Best case running time: O(n log2n)
 Worst case running time?
 Recursion:
1. Partition splits array in two sub-arrays:
• one sub-array of size 0
• the other sub-array of size n-1
2. Quicksort each sub-array
 Depth of recursion tree? O(n)

06/04/25 Lijo V.P 13600 SCSE VIT


Quicksort Analysis
 Assume that keys are random, uniformly
distributed.
 Best case running time: O(n log2n)
 Worst case running time?
 Recursion:
1. Partition splits array in two sub-arrays:
• one sub-array of size 0
• the other sub-array of size n-1
2. Quicksort each sub-array
 Depth of recursion tree? O(n)
 Number of accesses per partition?

06/04/25 Lijo V.P 13600 SCSE VIT


Quicksort Analysis
 Assume that keys are random, uniformly
distributed.
 Best case running time: O(n log2n)
 Worst case running time?
 Recursion:
1. Partition splits array in two sub-arrays:
• one sub-array of size 0
• the other sub-array of size n-1
2. Quicksort each sub-array
 Depth of recursion tree? O(n)
 Number of accesses per partition? O(n)

06/04/25 Lijo V.P 13600 SCSE VIT


Quicksort Analysis
 Assume that keys are random, uniformly
distributed.
 Best case running time: O(n log2n)
 Worst case running time: O(n2)!!!

06/04/25 Lijo V.P 13600 SCSE VIT


Quicksort Analysis
 Assume that keys are random, uniformly
distributed.
 Best case running time: O(n log2n)
 Worst case running time: O(n2)!!!
 What can we do to avoid worst case?

06/04/25 Lijo V.P 13600 SCSE VIT


Improved Pivot Selection
Pick median value of three elements from
data array:
data[0], data[n/2], and data[n-1].

Use this median value as pivot.

06/04/25 Lijo V.P 13600 SCSE VIT


Improving Performance of
Quicksort
Improved selection of pivot.
For sub-arrays of size 3 or less, apply brute
force search:
Sub-array of size 1: trivial
Sub-array of size 2:
 if(data[first] > data[second]) swap them
Sub-array of size 3: left as an exercise.

06/04/25 Lijo V.P 13600 SCSE VIT


Thank You

06/04/25 Lijo V.P 13600 SCSE VIT

You might also like