JIYIK CN >

Current Location:Home > Learning > ALGORITHM >

Learning path of sorting algorithm - direct insertion sort

Author:JIYIK Last Updated:2025/03/19 Views:

This article follows up on Insertion Sort (Concepts) and presents the implementation steps and code for direct insertion sort. Since the Concepts section already has a large number of illustrations, it would be a bit long-winded to provide further illustrations in this article, so the steps and code are listed directly here.

Implementation steps:

  1. Treat the first element of the first sequence to be sorted as an ordered sequence, and the second element to the last element as an unsorted sequence.
  2. Scan the unsorted sequence from beginning to end once, and insert each scanned element into the appropriate position of the ordered sequence (one thing to note here is that if there is an element in the ordered sequence that is equal to the element to be inserted, the element to be inserted will be found after this element. This insertion sort is stable. If it is inserted in front of this element, then this insertion sort is unstable.

Implementation code (PHP code):

The first implementation code is to traverse backwards from the first element, find the corresponding position, and then move and insert the element. The code is as follows

$arr1 = array(
15,77,23,43,90,87,68,32,11,22,33,99,88,66,44,113,
224,765,980,159,456,7,998,451,96,0,673,82,91,100
);
for($i=1;$i<count($arr1);$i++){
    $p = $arr1[$i];
    for($j=0;$j<$i;$j++){
        if($arr1[$j]>$p){
            break;
        }
    }
    for($k=$i-1;$k>=$j;$k--){
        $arr1[$k+1] = $arr1[$k];
    }
    $arr1[$j] = $p;
}

The second implementation code is to traverse forward from the previous element of the current element to be sorted (that is, the last element of the ordered sequence), find the corresponding position, and then move and insert the element. The code is as follows

$arr2 = array(
15,77,23,43,90,87,68,32,11,22,33,99,88,66,44,113,
224,765,980,159,456,7,998,451,96,0,673,82,91,100
);
for($i=1;$i<count($arr2);$i++){
    $p = $arr2[$i];
    for($j=$i-1;$j>=0;$j--){
        if($arr2[$j]>$p){
            $arr2[$j+1] = $arr2[$j];
        }else{
            break;
        }
    }
    $arr2[$j+1] = $p;
}

The above two codes can both implement insertion sorting. However, after writing the codes, we tested the two codes and found that the second method runs faster than the first method by printing the running time. The following are the running times of each method after running 5 times (Note: the above is the first case, and the following is the second case)

The above time comparison actually means that the same algorithm will take different time if implemented in different ways. The test data above are just simple numbers, and the speed is only in microseconds. There is no obvious difference for us, but when applied to projects, for complex and large data, a good implementation can save us a lot of time. So even in the stage of learning principles, we should optimize the code as much as possible.

For direct insertion sort, whether it is the first implementation or the second implementation, their time complexity is the same, both are O(n²)

For reprinting, please send an email to 1244347461@qq.com for approval. After obtaining the author's consent, kindly include the source as a link.

Article URL:

Related Articles

Learning the sorting algorithm - Binary Insertion Sort

Publish Date:2025/03/19 Views:142 Category:ALGORITHM

This article follows the insertion sort (concept article) and presents the implementation steps and implementation code of the binary insertion sort Binary Insertion Sort Algorithm Steps Treat the first element of the first sequence to be s

The road to learning sorting algorithms - table insertion sort

Publish Date:2025/03/19 Views:193 Category:ALGORITHM

Table insertion sort was briefly mentioned in Insertion sort (concept) . I briefly summarized it and wrote this article. You can refer to it if you need it. Table insertion sort, as the name implies, uses an index table to sort the original

The road to learning sorting algorithms - Hill sort

Publish Date:2025/03/19 Views:50 Category:ALGORITHM

Hill sort is named after the designer of the algorithm, Hill. It is an improvement of Hill on the basis of insertion sort and can be said to be a special insertion sort. Here are the properties of insertion sort: First of all, the insertion

The road to learning sorting algorithms - merge sort

Publish Date:2025/03/19 Views:157 Category:ALGORITHM

Let's first look at the definition of merge sort Merge sort is an effective sorting algorithm based on the merge operation. This algorithm is a very typical application of the Divide and Conquer method. Merge the ordered subsequences to obt

The road to learning sorting algorithms - quick sort

Publish Date:2025/03/19 Views:121 Category:ALGORITHM

Quick sort is a sorting algorithm developed by Tony Hall. On average, sorting n items requires O(n log n) comparisons. In the worst case, O(n2) comparisons are required, but this is uncommon. In fact, quick sort is often significantly faste

The road to learning sorting algorithms - heap sort

Publish Date:2025/03/19 Views:145 Category:ALGORITHM

Like other sorting algorithms, let's first look at the definition of heap sort. Heapsort : refers to a sorting algorithm designed using the heap data structure. A heap is a structure that approximates a complete binary tree and satisfies th

Common sorting algorithms

Publish Date:2025/03/19 Views:66 Category:ALGORITHM

This article introduces several commonly used sorting algorithms in software engineering. The core codes of all sorting algorithms are introduced in "Core Codes of Common Sorting Algorithms" 1. Insertion Sort The basic idea of ​​inserti

Scan to Read All Tech Tutorials

Social Media
  • https://www.github.com/onmpw
  • qq:1244347461

Recommended

Tags

Scan the Code
Easier Access Tutorial