{"id":16471,"date":"2023-05-18T07:40:42","date_gmt":"2023-05-18T07:40:42","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=16471"},"modified":"2024-02-19T06:25:27","modified_gmt":"2024-02-19T06:25:27","slug":"insertion-sort-in-java","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/insertion-sort-in-java\/","title":{"rendered":"Insertion Sort in Java"},"content":{"rendered":"

\"\"<\/p>\n

Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is efficient for sorting small arrays or nearly sorted arrays and is often used as part of more complex sorting algorithms. Understanding how insertion sort works and its implementation in Java is essential for programmers learning about sorting algorithms.<\/p>\n

What is Insertion Sort in Java?<\/h2>\n

Insertion sort is a simple and efficient comparison-based sorting algorithm. It works by dividing the input array into two parts: a sorted portion and an unsorted portion. Initially, the sorted portion contains only the first element of the array, while the rest of the elements are considered unsorted.<\/p>\n

The algorithm iterates through the unsorted portion of the array, taking one element at a time and placing it in its correct position within the sorted portion. This process continues until all elements are sorted, and the entire array is in order.<\/p>\n

To better understand the steps involved in insertion sort, let’s go through a simple example using an array of integers:<\/p>\n

    \n
  1. Start with the second element (index 1) and compare it to the previous element (index 0). If the previous element is larger, swap them.<\/li>\n
  2. Move to the next unsorted element (index 2) and compare it with all the elements in the sorted portion, shifting the larger elements to the right to make space for the current element.<\/li>\n
  3. Repeat this process until all elements are in the sorted portion, and the entire array is sorted.<\/li>\n<\/ol>\n

    Insertion sort has an average and worst-case time complexity of O(n^2), making it less efficient compared to more advanced sorting algorithms like merge sort or quicksort. However, it performs well on small input sizes or partially sorted arrays and has the advantage of being an in-place sorting algorithm, meaning it doesn’t require additional memory beyond the input array.<\/p>\n

    Characteristics of Insertion Sort in Java<\/h3>\n
      \n
    1. This algorithm is one of the most basic, with a straightforward implementation.<\/li>\n
    2. Insertion sort is most effective for small data values.<\/li>\n
    3. Because insertion sort is adaptive, it is appropriate for partially sorted data sets.<\/li>\n<\/ol>\n

      How does Insertion Sort actually Work?<\/h3>\n

      Assume we need to sort the array below.<\/p>\n

      \"\"<\/p>\n

        \n
      1. \n

        The array’s first element is presumed to be sorted. Take the second element and place it in a separate key. Contrast the key with the first element. If the key is greater than the first element, the key is placed in front of the first element. <\/p>\n

        \"\"<\/p>\n<\/li>\n

      2. \n

        The first two elements have now been sorted. Compare the third element to the elements to the left of it. Place it just behind the smaller element. If there is no element smaller than it, put it at the start of the array.<\/p>\n

        \"\"<\/p>\n<\/li>\n

      3. \n

        Likewise, put each unsorted element in its proper place.<\/p>\n

        \"\"<\/p>\n

        \"\"<\/p>\n<\/li>\n<\/ol>\n

        Pseudo Code of Insertion Sort<\/h3>\n
        procedure insertionSort(arr):\n    for i = 1 to n-1\n        key = arr[i]\n        j = i-1\n        while j >= 0 and arr[j] > key\n            swap arr[j+1] with arr[j]\n            j = j - 1\n        end while\n    end for\nend function<\/code><\/pre>\n
        Explanation of Pseudo Code of Insertion Sort<\/strong>
        \nThis algorithm sorts an array of items by inserting an element from the unsorted portion of the array into its proper position in the sorted portion of the array on a repeated basis.<\/p>\n
          \n
        1. Only one argument, ‘A,’ a list of sortable items, is accepted by the procedure.<\/li>\n
        2. The length of the array A is assigned to the variable ‘n’.<\/li>\n
        3. The outer for loop begins at index ‘1’ and loops for ‘n-1’ iterations, where ‘n’ is the array’s length.<\/li>\n
        4. The inner while loop begins at the outer for loop’s current index i and compares each element to its left neighbor. The components are switched out if one component is smaller than its left neighbor.<\/li>\n
        5. The inner while loop moves an element to the left until it is smaller than the element to its left.<\/li>\n
        6. When the inner while loop is completed, the element at the current index is in its correct position in the array’s sorted portion.<\/li>\n
        7. The outer for loop iterates through the array until all elements are correctly positioned and the array is completely sorted.<\/li>\n<\/ol>\n
          Iterative Approach of Insertion Sort<\/h3>\n
          To sort an array of size N in ascending order, use the following syntax:<\/p>\n
            \n
          1. Iterate through the array from arr[1] to arr[N].<\/li>\n
          2. Examine the current element (key) in relation to its predecessor.<\/li>\n
          3. Compare the key element to the elements before it if it is smaller than its predecessor. Move the larger elements up one position to make room for the replaced element.<\/li>\n<\/ol>\n
            Java Code of Insertion Sort – Iterative Approach<\/strong><\/p>\n\t\t\t\t\t\t