Data Structures (BCA) 3rd Sem Previous Year Solved Question Paper 2022

Insertion sort is a simple comparison-based sorting algorithm. It builds the final sorted array one item at a time. It works by taking one element from the unsorted part of the array and placing it in its correct position within the sorted part of the array. Here's the algorithm for insertion sort:

Algorithm for Insertion Sort:

    1. Start with the second element (index 1) of the array. Assume this element is the first element of the sorted part of the array.
    2. Compare the second element with the first element (the only element in the sorted part).
    3. If the second element is smaller, swap the two elements.
    4. Move to the third element and compare it with the elements in the sorted part of the array, shifting larger elements to the right until the correct position is found.
    5. Continue this process for the remaining elements in the unsorted part of the array, inserting each element into its correct position within the sorted part.

Example of Insertion Sort:

Let's use an example to illustrate how insertion sort works. We want to sort an array of integers in ascending order:
Unsorted Array: [64, 25, 12, 22, 11]
    1. Start with the second element (25) as the first element of the sorted part.
    2. Compare 25 with the first element (64) and swap them because 25 is smaller.
        ◦ Array after the first pass: [25, 64, 12, 22, 11]
    3. Move to the third element (12) and compare it with the elements in the sorted part of the array (25 and 64).
    4. Since 12 is smaller than 64, we swap 12 with 64 and then compare 12 with 25, which is also smaller.
        ◦ Array after the second pass: [12, 25, 64, 22, 11]
    5. Continue this process for the remaining elements:
        ◦ 22 is compared with 64 (swapped with 64), 25 (swapped with 25), and 12 (swapped with 12).
        ◦ 11 is compared with 64 (swapped with 64), 25 (swapped with 25), 22 (swapped with 22), and 12 (swapped with 12).
        ◦ The array is now sorted.

The sorted array is now complete: [11, 12, 22, 25, 64].

Insertion sort has a time complexity of O(n^2) in the worst case, making it less efficient than more advanced sorting algorithms like merge sort or quicksort for larger datasets. However, it is a simple and easy-to-implement algorithm that works well for small datasets and is efficient for nearly sorted data.