Insertion sort is another simple sorting algorithm that works by dividing the input list into a sorted and an unsorted region. It iterates through the unsorted region, taking one element at a time and inserting it into its correct position in the sorted region. This process continues until the entire list is sorted.

Here's an explanation of the insertion sort algorithm:

1. Start with an unsorted list of elements.

2. Consider the first element as the sorted region.

3. Iterate through the remaining unsorted region, taking one element at a time.

4. Compare the current element with the elements in the sorted region, moving elements in the sorted region that are greater than the current element one position to the right.

5. Insert the current element into its correct position in the sorted region.

6. Repeat steps 3-5 until all elements in the unsorted region have been processed.

7. The final result is a sorted list.

Here's an example implementation of the insertion sort algorithm in C:

#include <stdio.h>

// Function to perform insertion sort
void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        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 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Test the algorithm
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    insertionSort(arr, n);
    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

In this example, the `insertionSort` function performs the insertion sort algorithm on the given array. The `printArray` function is used to display the array before and after sorting. In the `main` function, we create an array, print it, call `insertionSort` to sort the array, and then print the sorted array.

The output will be:

Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

As you can see, the insertion sort algorithm gradually builds the sorted region by inserting elements into their correct positions, resulting in a sorted array.

Program

To implement an insertion sort program in any programming language, including DAA (Design and Analysis of Algorithms), you can follow these steps:

1. Start by defining an array of elements that you want to sort.

2. Implement the insertion sort algorithm, which builds the final sorted array one element at a time. It iterates over the unsorted part of the array, comparing each element with the sorted part and inserting it at the correct position.

Here's an example of an insertion sort implementation in DAA:

# Insertion sort implementation in DAA
    def insertion_sort(arr):
        n = len(arr)

        # Traverse through 1 to n
        for i in range(1, n):
        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 -= 1

    arr[j + 1] = key

# Example usage
arr = [64, 34, 25, 12, 22, 11, 90]
print("Unsorted array:", arr)

insertion_sort(arr)

print("Sorted array:", arr)

In the above code, the `insertion_sort` function takes an array (`arr`) as input and sorts it using the insertion sort algorithm. The outer loop iterates from the second element to the last element of the array. The inner loop compares the current element with the elements in the sorted part of the array and shifts them to the right if they are greater than the key. Finally, the key is inserted at the correct position. The sorted array is then printed.

The time complexity of the insertion sort algorithm is O(n^2) in the worst and average cases, and O(n) in the best case when the input array is already sorted. The space complexity is O(1) since it doesn't require any extra space beyond the input array.

Time Complexity

The time complexity of the Insertion Sort algorithm is O(n^2) in the worst and average cases, and O(n) in the best case.

In the worst case, when the input array is in reverse order, the Insertion Sort algorithm needs to make comparisons and shifts for each element in the array. For each element at index i, it compares and shifts i times to find the correct position in the sorted portion of the array. This results in a total of 1 + 2 + 3 + ... + (n-1) = (n*(n-1))/2 = O(n^2) comparisons and shifts.

In the best case, when the input array is already sorted in ascending order, the Insertion Sort algorithm still needs to make comparisons but no shifts are required because each element is already in its correct position. In this case, the time complexity reduces to O(n).

The average case time complexity of Insertion Sort is also O(n^2) because, on average, half of the elements will require shifting for each element.

It's important to note that Insertion Sort is efficient for small input sizes or when the input array is almost sorted. However, for larger datasets, other sorting algorithms such as Quicksort or Mergesort generally provide better average and worst-case time complexities.

Space Complexity

The space complexity of the Insertion Sort algorithm is O(1) because it uses a constant amount of extra space.

Insertion Sort operates directly on the input array without requiring additional data structures or dynamic memory allocation. It uses a few variables to keep track of the indices and the key element during the sorting process. However, the amount of space used by these variables remains constant regardless of the size of the input array.

This makes Insertion Sort advantageous in terms of space complexity when compared to sorting algorithms that require additional arrays or data structures for auxiliary operations. The space required by Insertion Sort is minimal and does not increase with the input size.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc