Dr.
Supriyo Mandal,
Data Structures and Ph.D. (IIT Patna)
Algorithms Postdoc (ZBW, University of Kiel, Germany)
Bubble Sort
ü In-place Sorting Algorithm
ü Comparison-Based Sorting Algorithm
ü Stable Sorting Algorithm
Bubble Sort
Optimized Bubble Sort
Bubble Sort – Time Complexity : O(�2 ) : worst case
Total Number of Comparisons (Exact Count):
�(�−1)
For n elements: (� − 1) + (� − 2) + (� − 3) + . . . . . . . . . + 1 =
2
Best case O(�2 )
O(�) : if we use flag: If array is sorted.
Avg case : O(�2 )
Case Time Complexity
Best (optimized) O(n)
Best (normal) O(n²)
Average O(n²)
Worst O(n²)
Insertion Sort
ü In-place Sorting Algorithm
ü Comparison-Based Sorting Algorithm
ü Stable Sorting Algorithm
Case Input Condition Time Complexity
Best Case Already sorted O(n)
Average Case Random order O(n²)
Worst Case Reverse sorted O(n²)
Selection Sort
ü In-place Sorting Algorithm
ü Comparison-Based Sorting Algorithm
ü unstable Sorting Algorithm
Case Input Condition Time Complexity
Best Case Already sorted O(n²)
Average Case Random order O(n²)
Worst Case Reverse sorted O(n²)
Divide Conquer and Combine Algorithm
Divide Conquer and Combine Algorithm
Merge Sort
Quick Sort
MERGE SORT
vout-place
vstable
vcomparison based
MERGE SORT
Merge Sort is based on Divide Conquer and Combine(MERGE)
Approach
Merge Sort uses MERGE operation to perform sorting
Merging Two Sorted List
Merge process will combine two sorted list List1 and
List2 and produce third sorted list List3
m n
LIST -1 LIST-2
LIST-3
m+n
Merging Two Sorted List
Initially
List-1 5 8 9 List-2 4 7 10
i j
List-3 3+3=6
Pick the smaller element and place into list-3
Merging Two Sorted List
Step-1
List-1 5 8 9 List-2 4 7 10
i j
List-3 4 3+3=6
Pick the smaller element and place into list-3
Merging Two Sorted List
Step-2
List-1 5 8 9 List-2 4 7 10
i j
List-3 4 5
Pick the smaller element and place into list-3
Merging Two Sorted List
Step-3
List-1 5 8 9 List-2 4 7 10
i j
List-3 4 5 7
Pick the smaller element and place into list-3
Merging Two Sorted List
Step-4
List-1 5 8 9 List-2 4 7 10
i j
List-3 4 5 7 8 9
Pick the smaller element and place into list-3
Merging Two Sorted List
Step-5
List-1 5 8 9 List-2 4 7 10
i j
List-3 4 5 7 8 9
Pick the smaller element and place into list-3
Merging Two Sorted List
Step-6
List-1 5 8 9 List-2 4 7 10
i j
List-3 4 5 7 8 9 10
As List-1 is eunuchated and place rest of the elements of List-2 into list-3 one by one
Merging Two Sorted List
Merging Algorithm:
1. Create List-3 of size List-1 + List-2 .
2. Simultaneously traverse List-1 and List-2.
• Pick smaller of current elements in List-1 and List-2 ,
• copy this smaller element to the next position in List-3
• and move ahead in List-3 and the List whose element is picked.
3. If there are remaining elements in List-1 or List-2 , copy them in List-3 .
Merging Two Sorted List
Cost of merging 2 sorted list of size m and n
= O(m + n)
Unsorted
MERGE
SORT
Sorted
Merge Sort
Merge
Process
Analyzing Merge Sort
T(n)
T(n/2)
T(n/2)
O(n)
Recurrence Relation: T(n) = 2T(n/2) + O(n) = O(nlogn)
Note: Merge Sort is LEAST dependent on the order of input data set
QUICK SORT
v inplace sorting
v unstable [2 7 2 10]
v comparison base sorting
QUICK SORT
Quick Sort is also based on Divide and Conquer Approach.
Quick sort uses PARTITION process to perform sorting
Developed by Tony Hoar in 1959
Also known as Partition Exchange Sort
Partition Process QUICK SORT
Goal: The goal is to find the correct position for the pivot in the sorted array.
Step-1
Choose the pivot element from given Array(HOW?)
Step-2
Perform Partitioning : rearranging the elements in the array so that
elements smaller than the pivot are moved to its left, and elements greater
than the pivot are moved to its right.
How to pick pivot element?
A critical decision that can significantly impact the efficiency of the sorting process
Some common strategies
1. First or last element :
10 5 12 1 9 8 20 3 6 23
Partition Process
Pivot
3 5 6 1 9 8 10 20 12 23
Less Than Pivot More Than Pivot
The Cost of Partition: O(n)
Quick Sort: Worst case
If the data is Sorted
1 2 3 4 5
The Recurrence Relation is
T(n) = T(1) + T(n - 1) + O(n)
1 2 3 4 5
T(n) = T(n-1) + O(n) = O(n2)
2 3 4 5
3 4 5
4 5
Quick Sort: Worst case
If the data is Reverse Sorted
5 4 3 2 1
4 3 2 1 5 The Recurrence Relation is
T(n) = T(n-1) + T(1) + O(n)
3 2 1 4
T(n) = T(n-1) + O(n)
2 1 3 = O(n2)
1 2
Quick Sort: Best Case
If the Partition process divides the data set in almost equal half
n
The Recurrence Relation is
n/2 n/2
T(n) =T(n/2) +T(n/2) + O(n)
T(n) =2T(n/2) + O(n)
n/4 n/4 n/4 n/4
T(n) =O(nlogn)
Quick Sort: Best Case
If the Partition process divides the data set as follows
n
The Recurrence Relation is
90% 10% 90� 10�
� � =� +� +�
100 100
9� �
90% 10% 90% 10% � � =� +� +�
10 10
T(n) =O(nlogn)
Quick Sort: Best Case
If the Partition process divides the data set as follows
n
The Recurrence Relation is
60% 40% 60� 40�
� � =� +� +�
100 100
3� 2�
60% 40% 60% 40% � � =� +� +�
5 5
T(n) =O(nlogn)
Radix SORT
vout-place (counting sort)
vin-place (bubble sort or insertion sort)
vstable
vnon-comparison based
v scan element from right side [107, 107, 2, 10]
107 9 91 139 532
Radix SORT
107 9 91 139 532
0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9
0 1 1 0 0 0 0 1 0 2
0 1 2 3 4 5 6 7 8 9
0 1 2 2 2 2 2 3 3 5
0 1 2 3 4 5 6 7 8 9
91 532 107 9 139 sorted based on least significant
digit
source : [Link]
[Link]
Radix SORT
Complexity O(d*(n+B)) : we use counting sort
O(d*�2 ) : we will use bubble sort / insertion sort
Bucket Sort