YouTip

\\n\\n

Insertion Sort

\\n\\n

Insertion Sort, also commonly known as direct insertion sort, is an efficient algorithm for sorting a small number of elements.

\\n\\n

Insertion sort is one of the simplest sorting methods. Its basic idea is to insert a record into an already sorted ordered list, thereby forming a new ordered list with one more record.

\\n\\n

In its implementation, a double loop is used. The outer loop iterates over all elements except the first one. The inner loop searches for the correct insertion position within the sorted portion preceding the current element and performs the necessary shifts.

\\n\\n

\\n\\n

Working Principle

\\n\\n

The core idea of insertion sort is "building a sorted sequence". It logically divides the array (or list) to be sorted into two parts:

\\n\\n

\\n
1. Sorted part: Initially, the first element of the array is typically considered a sorted sequence by itself.
\\n
2. Unsorted part: From the second element to the last element.
\\n

\\n\\n

The algorithm repeatedly takes the first element from the unsorted part and inserts it into its correct position within the sorted part, until the unsorted part is empty, at which point the entire array is sorted.

\\n\\n

Applicability Notes

\\n\\n

The average time complexity of insertion sort is also O(n^2), and the space complexity is constant O(1). The specific time complexity is also related to the initial order of the array.

\\n\\n

In insertion sort, the best case occurs when the array to be sorted is already ordered. In this case, only a comparison with the previous element is needed for each number, requiring a total of N-1 comparisons, resulting in a time complexity of O(N). The worst case is when the array is in reverse order, requiring the maximum number of comparisons, which is O(n^2).

\\n\\n

Process Illustration

\\n\\n

Assume the first n-1 (where n>=2) numbers are already sorted. Now, insert the n-th number into the previously sorted sequence and find its appropriate position, so that the sequence after inserting the n-th number is also sorted.

\\n\\n

By inserting all elements in this manner until the entire sequence is sorted, this process is called insertion sort.

\\n\\n

The entire process of insertion sort from smallest to largest is illustrated as follows:

\\n\\n

First round: Starting comparison from the 6 in the second position, it is smaller than the 7 before it, so their positions are swapped.

\\n\\n

\\n\\n

Second round: The 9 in the third position is larger than the 7 in the previous position, so no swap is needed.

\\n\\n

\\n\\n

Third round: The 3 in the fourth position is smaller than the 9 in the previous position, so they swap positions, and comparison continues forward.

\\n\\n

\\n\\n

Fourth round: The 1 in the fifth position is smaller than the 9 in the previous position, so they swap positions, and comparison continues forward.

\\n\\n

\\n\\n

......

\\n\\n

This process continues until the last element is compared.

\\n\\n

Java Example Code

\\n\\n

Source code package download: Download

\\n\\n

Partial code:

\\n\\n

InsertionSort.java file code:

\\n\\n

package ;\\n\\n/**\\n\\n* Insertion Sort\\n\\n*/\\n\\npublic class InsertionSort {\\n\\n    //Core code---Start\\n\\n    public static void sort(Comparable[] arr){\\n\\n        int n = arr.length;\\n\\n        for(int i =0; i 0; j --)\\n\\n                if( arr.compareTo( arr)<0)\\n\\n                    swap( arr, j , j-1);\\n\\n                else\\n\\n                    break;\\n\\n        }\\n\\n    }\\n\\n    //Core code---End\\n\\n    private static void swap(Object[] arr, int i, int j){\\n\\n        Object t = arr;\\n\\n        arr= arr;\\n\\n        arr= t;\\n\\n    }\\n\\n    public static void main(String[] args){\\n\\n        int N =20000;\\n\\n        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);\\n\\n        InsertionSort.sort(arr);\\n\\n        for(int i =0; i < arr.length; i ++){\\n\\n            System.out.print(arr);\\n\\n            System.out.print(' ');\\n\\n        }\\n\\n    }\\n\\n}

\\n\\n

---

\\n\\n

Algorithm Implementation and Code Analysis

\\n\\n

After understanding the principle, let's look at the specific code implementation. Here are versions in two common languages: Python and Java.

\\n\\n

Python Implementation

\\n\\n

Example

\\n\\n

def insertion_sort(arr):\\n\\n    """\\n\\n    Insertion SortAlgorithm Implementation (Ascending order)\\n\\n    :param arr: List to be sorted\\n\\n    :return: Sorted list (Modify in place, and also return)\\n\\n    """\\n\\n    # Iterate from the second element Start to the last element (Index 1 to n-1)\\n\\n    for i in range(1, len(arr)):\\n\\n        current_value = arr  # The current element to be inserted, first 'held in hand'\\n\\n        j = i - 1  # j Points to the last element of the sorted sequence\\n\\n        # Inner loop: For current_value in the sorted part arr[0..i-1] Looking for insertion position in\\n\\n        # Condition 1: j >= 0 Ensure not out of bounds to before the head of the list\\n\\n        # Condition 2: arr > current_value Indicates that the current compared element is larger than the 'one in hand', needs to move backward\\n\\n        while j >= 0 and arr > current_value:\\n\\n            arr[j + 1] = arr  # Move larger elements one position backward to make space\\n\\n            j -= 1  # Continue comparing the next element to the left\\n\\n        # Loop Ends, indicating the insertion position is found (j+1)\\n\\n        # At this point, arr <= current_value Or j == -1\\n\\n        arr[j + 1] = current_value  # Set"The one in hand"Element inserted into the correct position\\n\\n    return arr\\n\\n# Test code\\n\\nif __name__ == "__main__":\\n\\n    # Test data\\n\\n    test_data = [64, 34, 25, 12, 22, 11, 90]\\n\\n    print("Before sorting:", test_data)\\n\\n    sorted_data = insertion_sort(test_data.copy())  # Using a copySort, without affecting the original data\\n\\n    print("After sorting:", sorted_data)\\n\\n    # Another test: mostly sorted data\\n\\n    nearly_sorted_data = [1, 3, 2, 4, 6, 5, 8, 7]\\n\\n    print("nNearly sorted data Before sorting:", nearly_sorted_data)\\n\\n    print("After sorting mostly sorted data:", insertion_sort(nearly_sorted_data.copy()))

\\n\\n

Java Implementation

\\n\\n

Example

\\n\\n

public class InsertionSort {\\n\\n    public static void insertionSort(int[] arr) {\\n\\n        // Iterate from the second element Start to the last element (Index 1 to n-1)\\n\\n        for (int i = 1; i = 0 && arr > currentValue) {\\n\\n                arr[j + 1] = arr; // Element moved backward\\n\\n                j--;\\n\\n            }\\n\\n            // Insert the current element into the correct position\\n\\n            arr[j + 1] = currentValue;\\n\\n        }\\n\\n    }\\n\\n    // Overloaded method, supports sorting a part of an integer array\\n\\n    public static void insertionSort(int[] arr, int left, int right) {\\n\\n        for (int i = left + 1; i = left && arr > currentValue) {\\n\\n                arr[j + 1] = arr;\\n\\n                j--;\\n\\n            }\\n\\n            arr[j + 1] = currentValue;\\n\\n        }\\n\\n    }\\n\\n    public static void main(String[] args) {\\n\\n        // Test data\\n\\n        int[] testData = {64, 34, 25, 12, 22, 11, 90};\\n\\n        System.out.print("Before sorting: ");\\n\\n        printArray(testData);\\n\\n        int[] dataToSort = testData.clone(); // Using a copy\\n\\n        insertionSort(dataToSort);\\n\\n        System.out.print("After sorting: ");\\n\\n        printArray(dataToSort);\\n\\n    }\\n\\n    private static void printArray(int[] arr) {\\n\\n        for (int num : arr) {\\n\\n            System.out.print(num + " ");\\n\\n        }\\n\\n        System.out.println();\\n\\n    }\\n\\n}

\\n\\n

---

\\n\\n

Algorithm Characteristics Analysis

\\n\\n

Understanding an algorithm's performance and application scenarios is crucial. The characteristics of insertion sort can be summarized as follows:

\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n

Characteristic	Description	Explanation
Time Complexity	Average and Worst Case: $O(n^2)$	Requires nested loops for comparison and element movement. For n elements, in the worst case (completely reversed), approximately $frac{n(n-1)}{2}$ comparisons and movements are needed.
	Best Case: $O(n)$	When the input array is already nearly sorted, the inner loop executes rarely or exits immediately, requiring only n-1 comparisons.
Space Complexity	$O(1)$	It is an in-place sorting algorithm, requiring only constant extra space (such as variables like `current_value`, `j`, etc.).
Stability	Stable	When two elements are equal, their relative order remains unchanged after sorting. This is because the algorithm only moves elements when it encounters a value greater than the current value.
Applicable Scenarios	1. Small-scale data 2. Data is nearly sorted 3. As a subroutine in advanced sorting algorithms (e.g., Quick Sort, Merge Sort)	In these cases, its simple logic and low constant overhead may make it perform better than more complex $O(n log n)$ algorithms.

\\n\\n

Time Complexity Formula Derivation (Worst Case)

\\n\\n

In the worst case (array completely reversed):

\\n\\n

\\n
• The 1st element (index 0) is inserted, requiring 0 comparisons.
\\n
• The 2nd element (index 1) is inserted, requiring 1 comparison and 1 movement.
\\n
• The 3rd element (index 2) is inserted, requiring 2 comparisons and 2 movements.
\\n
• ...
\\n
• The n-th element (index n-1) is inserted, requiring n-1 comparisons and n-1 movements.
\\n

\\n\\n

The total number of comparisons and movements is: $0 + 1 + 2 + ... + (n-1) = frac{n(n-1)}{2}$

\\n\\n

Therefore, the time complexity is $O(n^2)$.

\\n\\n

---

\\n\\n

More Code Examples