Sorting Algorithms - Insertion Sort

What is the Insertion Sorting Method

Insertion Sort is a simple but effective sorting algorithm, whose basic idea is to insert an element to be sorted one by one into a sequence of elements that have already been sorted, until all the elements have been inserted, thus obtaining an ordered sequence.

The specific steps are as follows:

Assuming that initially, the first element forms itself into an ordered sequence, it can be regarded as a sorted part.
Starting with the second element, compare it to the sorted sequence from right to left and find the right place to insert it.
Compare the elements to be inserted with the elements in the sorted sequence one by one, and if the element to be inserted is smaller, move the sorted element one position to the right to make room for the element to be inserted.
Repeat step 3 until the insertion location is found or the sorted sequence has been traversed.
Inserts the element to be inserted into the found insertion position.
Repeat steps 2-5 until all elements have been inserted in the correct positions and sorting is complete.

The time complexity of the insertion sort method is O(n^2), where n denotes the number of elements to be sorted. In practice, insertion sort performs well for small or partially ordered sequences, but is relatively inefficient for large-scale disordered sequences.

It is worth noting that insertion sort is a stable sorting algorithm, i.e., the relative order of equal elements remains the same after sorting. This makes it advantageous in some specific scenarios.

Summary: Insertion Sort is a simple and practical sorting algorithm that constructs ordered sequences by comparing and inserting operations one by one. Although the time complexity is high, good performance can be obtained for small and partially ordered sequences.

Code Demo

Provides a sample code that implements insertion sorting using Python:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # Current element to be inserted
        j = i - 1     # Subscript of the last element of the sorted part
        # Move elements larger than the element to be inserted to the right
        while j &gt;= 0 and arr[j] &gt; key:
            arr[j + 1] = arr[j]
            j -= 1
        # Insert the element to be inserted at the right place
        arr[j + 1] = key
# Test examples
array = [9, 5, 2, 8, 1, 7]
insertion_sort(array)
print("Sorting results:", array)

Running the above code will output the sorted results:

Sort by: [1, 2, 5, 7, 8, 9]

This code obtains an ordered array by iterating over the array to be sorted and inserting each element into the correct position in the sorted subarray. Hopefully this example will help you understand the process of implementing the insertion sort algorithm.

algorithm optimization

Dichotomous search insertion: In the insertion sorting process, you can use dichotomous search to determine the correct location of the element to be inserted. The specific steps are as follows:
- Compare the element to be inserted with the middle element of the sorted section.
- If the element to be inserted is smaller than the center element, the insertion position is limited to the left half; otherwise, the insertion position is limited to the right half.
- Repeat the above steps to narrow down the search until the location of the element to be inserted is determined.
- After inserting the element to the correct position, move the whole of the sorted part of the element one position to the right to make room for the element to be inserted.
Early termination: In the process of insertion sort, if you find that the element to be inserted is already in the correct position, you can terminate the inner loop early to reduce the number of unnecessary comparisons.

The following is sample code that has been optimized for the insertion sort algorithm:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # Current element to be inserted
        left = 0      # Starting position of the sorted section
        right = i - 1 # Subscript of the last element of the sorted part
        # Use binary lookup to find the correct location of the element to be inserted
        while left &lt;= right:
            mid = (left + right) // 2
            if arr[mid] &lt; key:
                left = mid + 1
            else:
                right = mid - 1
        # Insert the element to be inserted at the right position and terminate the inner loop early (if already in the right position)
        for j in range(i - 1, left - 1, -1):
            if arr[j] == key:
                break
            arr[j + 1] = arr[j]
        else:
            arr[left] = key
# Test examples
array = [9, 5, 2, 8, 1, 7]
insertion_sort(array)
print("Sorting results:", array)

With the above optimizations, the insertion sort algorithm can sort arrays more efficiently. We hope this optimized example can meet your needs.

experience

For algorithm optimization, here are some insights:

Understanding the Time Complexity of Algorithms: Before optimizing an algorithm, it is important to first assess and understand the time complexity of the algorithm to be optimized. Only by understanding the time complexity characteristics of the algorithm can the optimization be targeted.
Finding Bottleneck Points: When performing algorithm optimization, you need to find bottleneck points that affect the performance of the algorithm. These bottleneck points are usually critical operations or repetitive computations that cause the algorithm to be inefficient. By optimizing the bottleneck points, the overall performance of the algorithm can be improved.
Utilizing Space for Time: Sometimes the execution of an algorithm can be accelerated by using extra space to store intermediate results or by using auxiliary data structures. This strategy of utilizing space for time is effective in some cases.
Deep understanding of data structures and algorithms: Good data structure selection and algorithm design are the basis of efficient algorithms. A deep understanding of various data structures and algorithms, and familiarity with their characteristics and application scenarios can help us better optimize our algorithms.
Analysis and selection based on actual situation: different algorithmic optimization methods are applicable to different problems and scenarios. According to the specific needs and actual situation, choose the appropriate optimization strategy. When performing algorithm optimization, the readability, maintainability and extensibility of the code should also be considered.
Testing and Evaluation: Adequate testing and evaluation of the optimized algorithm is necessary. By comparing the performance of the algorithm and the correctness of the results before and after optimization, the effectiveness of the optimization can be verified and further adjustments and improvements can be made as needed.

When performing algorithm optimization, the readability, maintainability and scalability of the code are also taken into account.

In short, algorithm optimization is a process of continuous learning and practice. Through in-depth understanding of algorithmic principles, mastering appropriate optimization techniques and experience, and analyzing and practicing in combination with actual problems, we can continuously improve the efficiency and performance of our algorithms.

This article on the sorting algorithm of the insertion sorting method analysis of the article is introduced to this, more related to the analysis of the insertion sorting method, please search for my previous posts or continue to browse the following articles hope that you will support me in the future!