How does insertion sort work

Explain the Insertion sort algorithm.

• Insertion sort is based on the principle of inserting the element into the proper position in the previously sorted list. if take (N-1)passes to sort N element of the array.
• In this sort, the first element is considered to be sorted and the remaining elements are in the unsorted list. One element from the unsorted list is picked-up and inserted in the sorted list to its proper position. This process is continued until the unsorted list is finished.

Initially: Data[1] is itself sorted. And the remaining elements are unsorted.

Pass1:  Data[2] is inserted either before Data[1] or after Data[1] so that Data[1] and Data[2] are sorted.

Pass2: Data[3] is inserted to its proper position in Data[1] Data[2] so the Data[1], Data[2] and Data[3] are sorted.

Pass3: Data[4] is inserted to its proper position in Data[1], Data[2], Data[3]so that Data[1], Data[2], Data[3] and Data[4] are sorted.

.

.

.

PassN-1: Data[N] is inserted in Data[1], Data[2]…Data[N-1] so that Data[1], Data[2]…Data[N] are sorted.

Algorithm: Insertion_sort(Data[],N)

• This is the algorithm for inserted sort to sort the array in ascending order.
• Data[]-Array of elements
• N-size of array
• i,j-index variable
• temp-temporary variable

Here’s an explanation of the insertion sort algorithm in c

Step 1 : Start
Step 2 : Repeat the steps 3, 4, 5 and 6 for i = 2 to N
Step 3 : Set temp = Data[i]
Step 4 : Set j = i - 1
Step 5 : Repeat while j > 0 and temp < data[i]
      a) Set Data[j+1] = Data[j]
      b) Set j = j - 1
Step 6 : Set Data[j+1] = temp
Step 7 : Stop

what is the insertion sort

Insertion sort is a simple sorting algorithm that works by repeatedly inserting an element from an unsorted portion of the array into its correct position within a sorted portion of the array. The algorithm starts with an initially sorted section of the array consisting of a single element (usually the first element), and then iteratively expands this sorted section by one element at a time.

The algorithm works as follows:

1. Start with the second element in the array (assuming the first element is already sorted).
2. Compare the second element with the first element. If the second element is smaller, swap them.
3. Move to the next element (the third element) and compare it with the elements in the sorted section from right to left. Insert the element into its correct position within the sorted section by shifting the larger elements from one position to the right.
4. Repeat step 3 for all the remaining elements, each time expanding the sorted section by one element.
5. Once all the elements are inserted into their correct positions, the array is sorted.

Insertion sort has a time complexity of O(n^2), where n is the number of elements in the array. It is considered efficient for small input sizes or partially sorted arrays but becomes less efficient for larger arrays compared to more advanced sorting algorithms like to merge sort or quicksort.

Here’s an explanation of the insertion sort algorithm in Java

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int 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;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 12, 1, 6, 3};
        
        System.out.println("Original array: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Here’s an explanation of the insertion sort algorithm in Java:

javaCopy codepublic class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int 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;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 12, 1, 6, 3};
        
        System.out.println("Original array: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

In this Java implementation, we have a method called insertionSort that takes an array of integers as input and sorts it using the insertion sort algorithm.

The insertionSort the method iterates through the array starting from the second element (i = 1). It selects the current element (key) and compares it with the elements in the sorted portion of the array (arr[0..i-1]). If an element in the sorted portion is greater than the key, it is shifted one position to the right to make room for the key. This process continues until the correct position the key is found.

Finally, the main the method demonstrates the usage of insertionSort by creating an array, sorting it using the method, and printing the original and sorted arrays.

When you run the code, the output will be:

Original array: [5, 2, 8, 12, 1, 6, 3]
Sorted array: [1, 2, 3, 5, 6, 8, 12]

This demonstrates how the insertion sort algorithm arranges the elements of the array in ascending order.