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

Check if a Post exists in PHP

Publish Date:2025/04/13 Views:170 Category:PHP

PHP $_POST is a super global variable that can contain key-value pairs of HTML form data submitted through the post method. We will learn different ways to check $_POST if a and contains some data in this article. These methods will use iss

PHP with Ajax

Publish Date:2025/04/13 Views:139 Category:PHP

We will use PHP and ajax by printing a simple sum of two numbers 2 and . Also, print a php array in JSON. 3 object We will also use PHP with ajax by getting the HTML formatted output from the number division in PHP. Printing simple addition

Store Div Id in PHP variable and pass it to JavaScript

Publish Date:2025/04/13 Views:51 Category:PHP

This article shows you how to div id store a in a PHP variable and pass it to JavaScript code. We will answer the following questions. What is div id ? How to div id store in a PHP variable? How to pass variables to JavaScript code? Let’s

Returns the article tag with ID from the action page

Publish Date:2025/04/13 Views:80 Category:PHP

Let's say you're in a login form and you enter the wrong information; in this case, you probably want to go back to the login page. PHP has a built-in function header() to redirect a page to a specific page. But what if the login page is at

Switching PHP versions on Ubuntu

Publish Date:2025/04/13 Views:78 Category:PHP

Different tasks may require running multiple versions of PHP. You may need to switch PHP versions by running two sites on the same server or testing older versions of code using outdated methods. We can switch PHP versions on Ubuntu using t

Resizing images in PHP

Publish Date:2025/04/13 Views:155 Category:PHP

In this tutorial article, we will discuss about resizing images in PHP. Load the image before resizing Before we can resize an image, we must first load it as an image resource in our script. This is file_get_contents() different from using

PHP upload image

Publish Date:2025/04/13 Views:61 Category:PHP

We can upload images in PHP using simple file upload operation, but first, php.ini file upload should be enabled from Files. This tutorial demonstrates how to upload images in PHP. php.ini Enable file upload from file in PHP to upload image

Creating a signature from Hash_hmac() and Sha256 in PHP

Publish Date:2025/04/13 Views:107 Category:PHP

PHP has one of the best encryption functions for data security. Hash_hmac() The encrypt function is one of the most famous encryptors. We'll show you how to use hash_hmac and sha256 encryptors to create 安全签名 one that you can store i

Updating PHP 7.x to 7.4 on CentOS

Publish Date:2025/04/13 Views:131 Category:PHP

This article shows the steps to update the PHP version from 7.x version to 7.4 in CentOS. How to Update PHP from 7.X to 7.4 in CentOS Update operating system packages. yum update -y Check your PHP version in CentOS. php -v Prints a list of

Scan to Read All Tech Tutorials

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

Recommended

Tags

Scan the Code
Easier Access Tutorial