Insertion Sort

Insertion Sort

• The basic idea of this method is to insert an unsorted element in it's correct position in a sorted set of element.
• Insertion sort is simple sorting algorithm that works similar to the way you sort playing cards in your hand.

• Advantages of Insertion Sort

1. It is  a simple sorting method.
2. No additional data structure is required.
3. It is stable sorting method.
4. Best case time complexity is Ω (n).
5. It also exhibits good performance when deling with a small list.

• Disadvantages of Insertion Sort

1. It does not perform as well as other, better sorting algorithm.
2. The insertion sort does not deal well with a huge list.
3. The insertion sort is particularly useful only when sorting a list of few items.
4. worst case time complexity is O(n²). 

    ⊚Complexity of Insertion Sort

• Time Complexity

1. Best Case: Ω (n)
2. Woest Case: O(n²)

• Space Comlplexity

1. Worst Case: O(1)

• Stable: YES

CODE

👇

1. #include<stdio.h>
2. int comp_cnt;
3. void main()
4. {
5.      int a[20], i, n;
6.     void insertion(int a[], int n);
7.     printf("How many elements you want to enter ? \n");
8.     scanf("%d", &n);
9.     printf("Enter %d elements \t", n);
10. for(i=0; i<n; i++)
11. {
12. scanf("%d", &a[i]);
13. }
14. insertion(a,n);
15.         printf("Sorted elements are \t");
16. for(i=0; i<n; i++)
17. {
18.     printf("%d\t", a[i]);
19. }
20. printf("\n Total number of comparisions %d \n", comp_cnt);
21. }
22. void insertion(int a[20], int n)
23. {
24. int i, k, new;
25. for(k=1; k<n; k++)
26. {
27.     new=a[k];
28.     for(i=k-1; i>=0; i--)
29.     {
30.         comp_cnt++;
31.         if(a[i]>new)
32.                {
33.             a[i+1]=a[i];
34.         }//if
35.         else
36.                  break;
37.              }inner for
38.                  a[i+1]=n
39. }//outer for
40. }//insertion function

👉Execute👈

//Output

/*

How many elements you want to enter ? 

5

Enter 5 elements 6

5

1

8

3

Sorted elements are 1 3 5 6 8

 Total number of comparisions 8 

*/

                                                                      //ThE ProFessoR