Binary Insertion Sort.pptx

Binary insertion sort is a sorting algorithm similar to insertion sort, but instead of using linear search to find the position where the element should be inserted, we use binary search. Thus, we reduce the number of comparisons for inserting one element from O(N) (Time complexity in Insertion Sort) to O(log N).

1. Binary Insertion Sort Algorithm Syed Jafer K https://syedjaferk.hashnode.dev/

2. Binary Insertion Sort Binary insertion sort is a sorting algorithm similar to insertion sort, but instead of using linear search to find the position where the element should be inserted, we use binary search . Thus, we reduce the number of comparisons for inserting one element from O(N) (Time complexity in Insertion Sort) to O(log N). 29 10 14 37 14 https://syedjaferk.hashnode.dev/

3. 29 10 14 37 14 First Pass Key (index) = 1 Since we consider the first element is in the sorted array, we will be starting from the second element. Then we apply the binary search on the sorted array. Key Sorted Array https://syedjaferk.hashnode.dev/

4. 29 10 14 37 14 After Binary Search in Sorted array In this scenario, we can see that the middle element in sorted array ( 29 ) is greater than the key element 10 . So the position of the key element is 0. Then we can shift the remaining elements by 1 position. 10 29 14 37 14 https://syedjaferk.hashnode.dev/ position of 10 is 0. p osition of 29 moved to next position.

5. Second Pass Key = 2 Now the key element is 14. We will apply binary search in the sorted array to find the position of the key element. 10 29 14 37 14 Key Element Sorted Array https://syedjaferk.hashnode.dev/

6. 10 29 14 37 14 After Binary Search in Sorted array In this scenario, by applying binary search, we can see key element to be placed at index 1 (between 10 and 29). Then we can shift the remaining elements by 1 position. 10 14 29 37 14 https://syedjaferk.hashnode.dev/ position of 14 is 1. position of 29 moved to next position.

7. Third Pass Key = 2 Now the key element is 37. We will apply binary search in the sorted array to find the position of the key element. 10 14 29 37 14 Key Element Sorted Array https://syedjaferk.hashnode.dev/

8. 10 14 29 37 14 After Binary Search in Sorted array In this scenario, by applying binary search, we can see key element is placed in its correct position. https://syedjaferk.hashnode.dev/

9. Fourth Pass Key = 4 Now the key element is 14. We will apply binary search in the sorted array to find the position of the key element. Key Element Sorted Array https://syedjaferk.hashnode.dev/ 10 14 29 37 14

10. 10 14 29 37 14 After Binary Search in Sorted array In this scenario, by applying binary search, we can see key element to be placed at index 2 (between 14 and 29). Then we can shift the remaining elements by 1 position. 10 14 14 29 37 https://syedjaferk.hashnode.dev/ position of 14 is 2. Now we can see all the elements in the array is sorted

11. Best Case Average Case Worst Case O(N Log N) O(N) 2 O(N) 2 https://syedjaferk.hashnode.dev/