data structures using passes but we still have to continue with rest of the passes so once we have detected that the array is sortedthe algorithm must not be executed further this is the optimization over the original bubble sort algorithm in order to stop the execution of further passes after the array is sortedwe can have variable flag which is set to true before each pass and is made false when swapping is performed the code for the optimized bubble sort can be given asvoid bubble_sort(int *arrint nint ijtempflag for( = <ni++for( = < - - ++if(arr[ ]>arr[ + ]flag temp arr[ + ]arr[ + arr[ ]arr[jtempif(flag = /array is sorted returncomplexity of optimized bubble sort algorithm in the best casewhen the array is already sortedthe optimized bubble sort will take (ntime in the worst casewhen all the passes are performedthe algorithm will perform slower than the original algorithm in average case alsothe performance will see an improvement compare it with the complexity of original bubble sort algorithm which takes ( in all the cases insertion sort insertion sort is very simple sorting algorithm in which the sorted array (or listis built one element at time we all are familiar with this technique of sortingas we usually use it for ordering deck of cards while playing bridge the main idea behind insertion sort is that it inserts each item into its proper place in the final list to save memorymost implementations of the insertion sort algorithm work by moving the current data element past the already sorted values and repeatedly interchanging it with the preceding value until it is in its correct place insertion sort is less efficient as compared to other more advanced algorithms such as quick sortheap sortand merge sort technique insertion sort works as followsthe array of values to be sorted is divided into two sets one that stores sorted values and another that contains unsorted values the sorting algorithm will proceed until there are elements in the unsorted set suppose there are elements in the array initiallythe element with index (assuming lb is in the sorted set rest of the elements are in the unsorted set the first element of the unsorted partition has array index (if lb during each iteration of the algorithmthe first element in the unsorted set is picked up and inserted into the correct position in the sorted set