Insertion sort is a very simple sorting algorithm which the sorted array is built one element at a time.

The main advantage of insertion sort is that it can efficiently be implemented on data set that are already substantially sorted .

For insertion sort the best case occurs when the array is already sorted ; while the worst case happens when the array is sorted in the reverse order.

Best case :O(n)

Worst case :O(n^2)

Source code :

Output:

###

The number of comparisons of elements in the

The average case time-complexity is O((N-1)*N/4), i.e. O(N

The

The main advantage of insertion sort is that it can efficiently be implemented on data set that are already substantially sorted .

For insertion sort the best case occurs when the array is already sorted ; while the worst case happens when the array is sorted in the reverse order.

Best case :O(n)

Worst case :O(n^2)

__Technique:__- We first divide the array to be sorted into two sets.One that stores the sorted value while the other stores unsorted values.
- The sorting algorithm proceeds until there are elements in the unsorted set.
- Initially we take the first element of the array (index 0)to be in the sorted set while the rest of the elements are in the unsorted set.
- During each iteration of the algorithm, the first element in the unsorted set is picked up and inserted into the correct position of the sorted set.

Source code :

Output:

###
__Complexity:__

The number of comparisons of elements in the *worst case*is```
(N-1) + (N-2) + ... + 1
= (N-1)*N/2
```

i.e. O(N^{2}).The average case time-complexity is O((N-1)*N/4), i.e. O(N

^{2}).The

*best-case*time complexity is when the array is already sorted, and is O(N).
## No comments:

## Post a Comment