Insertion Sort

Insertion sort is a simple and efficient sorting algorithm that builds the final sorted array one item at a time. It's an in-place sorting algorithm, which means it doesn't require additional memory for sorting. Here's a detailed algorithm for insertion sort, along with an example:

Algorithm: Insertion Sort

1. Start with the second element (index 1) in the array. This is the key element to be inserted into the sorted portion of the array.
2. Compare the key element with the element(s) to its left in the sorted portion of the array.
3. Move elements greater than the key element one position to the right until you find an element that is less than or equal to the key element, or until you reach the beginning of the array.
4. Insert the key element into the position where you stopped moving elements in step 3.
5. Repeat steps 1-4 for each element in the array, moving from left to right.
6. The array is now sorted.

Example

We'll perform insertion sort on this array:

Initial Array: [12, 11, 13, 5, 6] (index 0 is considered sorted initially)

Pass 1:

Key element: 11

Compare with 12 (element to its left). 11 < 12.
Move 12 to the right: [11, 12, 13, 5, 6]
Insert 11 at its correct position: [11, 12, 13, 5, 6]

Pass 2:

Key element: 13
Compare with 12 (element to its left). 13 > 12.
No need to move elements.
Insert 13 at its correct position: [11, 12, 13, 5, 6]
Pass 3:
Key element: 5
Compare with 13 (element to its left). 5 < 13.
Move 13 to the right: [11, 12, 5, 13, 6]
Compare with 12 (element to its left). 5 < 12.
Move 12 to the right: [11, 5, 12, 13, 6]
Compare with 11 (element to its left). 5 < 11.
Move 11 to the right: [5, 11, 12, 13, 6]
Insert 5 at its correct position: [5, 11, 12, 13, 6]
Pass 4:

Key element: 6
Compare with 13 (element to its left). 6 < 13.
Move 13 to the right: [5, 11, 12, 6, 13]
Compare with 12 (element to its left). 6 < 12.
Move 12 to the right: [5, 11, 6, 12, 13]
Compare with 11 (element to its left). 6 > 11.
Move 11 to the right: [5, 6, 11, 12, 13]
Insert 6 at its correct position: [5, 6, 11, 12, 13]

Final Sorted Array: [5, 6, 11, 12, 13]

After each pass, the left portion of the array is sorted, and the right portion remains unsorted. The algorithm continues this process until the entire array is sorted.

Pseudo Code

InsertionSort(arr):

    n = length of arr

    for i from 1 to n - 1:

        key = arr[i]

        j = i - 1

        // Move elements of arr[0..i-1] that are greater than key

        // to one position ahead of their current position

        while j >= 0 and arr[j] > key:

            arr[j + 1] = arr[j]

            j = j - 1

        arr[j + 1] = key

n is the number of elements in the array arr.
The outer loop runs from index 1 to n - 1 (inclusive). It iterates through the unsorted portion of the array.
Inside the loop, key is set to the current element at index i.
The inner while loop compares the key with the elements to its left (sorted portion of the array) and shifts larger elements one position to the right until it finds the correct position for key.
Once the correct position for key is found, it is inserted into that position in the sorted portion of the array.
The outer loop continues until all elements in the array are sorted.

Here's the time and space complexity analysis of the Insertion Sort algorithm:

Time Complexity:

Best-case Time Complexity: The best-case time complexity occurs when the input array is already sorted in ascending order. In this case, Insertion Sort makes only one pass through the array to check that each element is in the correct order. The time complexity is O(n), where n is the number of elements in the array.

Worst-case Time Complexity: The worst-case time complexity occurs when the input array is sorted in descending order, and every element needs to be moved to the beginning of the array. In this case, Insertion Sort makes n passes through the array, and during each pass, it may need to compare and shift all previous elements. The time complexity is O(n^2).

Average-case Time Complexity: On average, when the input is random or partially sorted, Insertion Sort performs better than its worst-case scenario but worse than its best-case scenario. The average-case time complexity is also O(n^2).

Space Complexity:

Insertion Sort is an in-place sorting algorithm, which means it doesn't require additional memory to sort the array. It sorts the array by moving elements within the original array without using any auxiliary data structures. Therefore, the space complexity of Insertion Sort is O(1), indicating that it uses a constant amount of extra space for temporary variables, regardless of the size of the input array.

In summary:Best-case time complexity: O(n)
Worst-case time complexity: O(n^2)
Average-case time complexity: O(n^2)
Space complexity: O(1)

Insertion Sort is efficient for small datasets or when you know that the dataset is almost sorted, but it becomes less efficient for larger datasets due to its quadratic worst-case time complexity. For large datasets, more efficient sorting algorithms like Merge Sort or Quick Sort are typically preferred.

C Program- Insertion sort

/*******************************************************************************/

#include<stdio.h>

void insertionsort(int arr[],int n)

{

int i,j,key;

for(i=1;i<n;i++)

{

    key=arr[i];

    j=i-1;

    while(j>=0 && arr[j] > key)

        {

        arr[j+1]=arr[j];

        j=j-1;

        }

    arr[j+1]=key;

}

}

int main(){

int size,i;

printf("Enter size of the array: ");

scanf("%d",&size);

int arr[size];

printf("Enter %d elements: ",size);

for(i=0;i<size;i++)

scanf("%d",&arr[i]);

insertionsort(arr,size);

printf("Sorted elements: ");

for(i=0;i<size;i++)

printf(" %d",arr[i]);

return 0;

}