What is Insertion Sort. Its basic information

it consists of the introduction , algorithms and code output. https://educationgateway.org/
This pptx also consists of advantages and disadvantages of insertion sort.

1. educationgateway.org Insertion-Sort

2. INTRODUCTION The idea of insertion sort is similar to the idea of sorting playing cards

3. INSERTION-SORT Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part

4. INSERTION-SORT CONT........ 5 1 6 3 4 3 Lets take this Array. As we can see here, in insertion sort, we pick up a key, and compares it with elemnts ahead of it, and puts the key in the right place 5 has nothing before it. 1 is compared to 5 and is inserted before 5. 6 is greater than 5 and 1. 2 is smaller than 6 and 5, but greater than 1, so its is inserted after 1. And this goe s on. ..

5. ALGORITHM INSERTION-SORT (A) 1. for j=2 to A.length 2. key= A[j] 3. // Insert A [j] into the sorted sequence A[i.. j - 1 ] 4. i = j - 1 5. while i > 0 and A[i] > ky 6. A[i + 1] = A[i] 7. i = i - 1 8. A[i + 1] = key

6. CODE

7. CODE OUTPUT

8. ADVANTAGES Simple Efficient for small data sets One of the faster O(n^2) performance algorithms Does not require extra memory Low overhead Best case is O(n) Nearly sorted input

9. DISADVANTAGES Poor performance with large lists Expensive with many elements Not as quick as merge sort or quicksort Worst case is O(n^2) - Input Array/List in reverse order

10. TIME COMPLEXITY Best case: O(n) Average case: O(n^2) • W orst case: O(n^2)

11. Thanks