DSA PROJECT
INSERTION SORT ALGORITHM
Code
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = [Link];
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1], that are greater than key, to one position
ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
}
Explanation:
• The above code is the of Insertion sort with the traditional method that
has the worst time complexity in the.
2
DSA PROJECT
• It’s time complexity in best case is O(n).
• It’s time complexity in worst case is O(n^2).
• It’s time complexity in average case is O(n^2).
Methodology
Insertion sort
Best Case
Let’s have an array of 5 elements.
1 2 3 4 5
Comparison
S US
1 2 3 4 5
Second Comparison
S US
1 2 3 4 5
Third Comparison
S US
1 2 3 4 5
3
DSA PROJECT
Fourth Comparison
S US
1 2 3 4 5
Fifth Comparison
S
1 2 3 4 5
Time Complexity
1+1+1+1+1….
O(n)
Worst Case
Let’s have an array of 5 elements.
5 4 3 2 1
4
DSA PROJECT
Comparison
First pass S US
5 4 3 2 1
Comparison = 1
Second Pass
S US
4 5 3 2 1
1
Comparison = 2
Third pass
S US
3 4 5 2 1
Comparison = 3
Fourth pass
S US
2 3 4 5 1
Comparison = 4
5
DSA PROJECT
Fifth pass
S
1 2 3 4 5
Comparison = 5
Time Complexity
1+2+3+4+5….
O(n^2)
6
DSA PROJECT
Binary Insertion Sort
Code
public class BinaryInsertionSort {
public static void binaryInsertionSort(int[] arr) {
int n = [Link];
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Find the correct position for the key element using binary search
int insertionIndex = binarySearch(arr, key, 0, j);
// Shift elements to the right to make space for the key element
for (int k = i; k > insertionIndex; k--) {
arr[k] = arr[k - 1];
}
// Insert the key element at its correct position
arr[insertionIndex] = key;
}
}
7
DSA PROJECT
private static int binarySearch(int[] arr, int key, int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
return left;
Explanation:
• This is the improved/better version of insertion sort code
(called as Binary insertion sort).
• This algorithm/code decreases comparison, because of
lowering comparisons time complexity get reduced.
• This implements the Binary search that returns the exact
location of the key to be inserted.
• Although the time complexity remains approximately the same,
comparison get fewer, as a result algo get more efficient.
• It’s time complexity in best case is O(n).
• It’s time complexity in worst case is n(logn).
• Its time complexity in average case is n(logn).
8
DSA PROJECT
Best Case
Let’s have an array of 5 elements.
1 2 3 4 5
Comparison
First
S US
1 2 3 4 5
Second Comparison
S US
1 2 3 4 5
9
DSA PROJECT
Third Comparison
S US
1 2 3 4 5
Fourth Comparison
S US
1 2 3 4 5
Fifth Comparison
S
1 2 3 4 5
Time Complexity
1+1+1+1+1….
O(n)
10
DSA PROJECT
Worst Case
Let’s have an array of 5 elements.
5 4 3 2 1
Comparison
First pass S US
5 4 3 2 1
Second Pass
S US
4 5 3 2 1
1
Third pass
S US
3 4 5 2 1
11
DSA PROJECT
Fourth pass
S US
2 3 4 5 1
Fifth pass
S
1 2 3 4 5
Time Complexity
n(logn).
12
DSA PROJECT
Output
Thank you!
13