Learning the sorting algorithm - Binary Insertion Sort
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 sorted as an ordered sequence, and the second element to the last element as an unsorted sequence.
- Scan the unsorted sequence from beginning to end, and insert each scanned element into the appropriate position of the ordered sequence. Binary insertion sort uses the binary search method to find the appropriate position in the ordered sequence to insert the unsorted elements. (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 way of insertion sorting is stable. If it is inserted in front of this element, then this way of insertion sorting is unstable)
Implementation code (PHP code)
$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($arr);$i++){
if($arr[$i]<$arr[$i-1]){
//使用二分查找法查找适当的位置
$low = 0;
$high = $i-1;
$pos = floor(($low+$high)/2);
$key = $arr[$i];
while($low<$high){
if($arr[$pos]>$key){
$high = $pos-1;
}elseif($arr[$pos]<=$key){
$low = $pos+1;
}
$pos = floor(($low+$high)/2);
}
//二分查找法结束
if($arr[$pos]>$arr[$i]){
$pos = $pos-1;
}
for($j=$i-1;$j>$pos;$j--){
$arr[$j+1]=$arr[$j];
}
$arr[$j+1] = $key;
}
}
The above is the implementation code of Binary Insertion Sort. From the code, we can see that the only difference between Binary Insertion Sort and Direct Insertion Sort is the code for finding the position. The rest are the same. Binary Insertion Sort needs to move the same elements as Direct Insertion Sort. Therefore, its time complexity is also O(n²).
But further analysis shows that even though the time complexity of the two is the same, binary insertion sort is faster than direct insertion sort overall. The following is a test I did (the data required here cannot be the data in the above code. Here I constructed an array of 100 data for testing)
$arr = 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,36,57,1334,5567,4432,11178,9997,88851,
4449,33332,9992,76853,67434,1239,98716,5349,90718,3589,213450,6754,24,
562,77,16,127,361,572,13343,55674,44325,1117,99979,88850,44491,3333,99923,
7685,6743,12395,9871,53497,9071,35899,21345,67541,24,56,774,16,127,111,112,
113,114,115,116,117,118,119,110,101,102,103,104,105,106,107,108,109,1000);
The direct insertion sort code uses the following paragraph
for($i=1;$i<count($arr);$i++){
$p = $arr[$i];
for($j=$i-1;$j>=0;$j--){
if($arr[$j]>$p){
$arr[$j+1] = $arr[$j];
}else{
break;
}
}
$arr[$j+1] = $p;
}
Based on the same set of data, we run these two codes multiple times and record the time taken for each. The following is the time comparison for each time. The one above is binary insertion sort and the one below is direct insertion sort.
From the above comparisons, we can find that the time required for binary insertion is shorter than that required for direct insertion. The larger the amount of data, the more obvious the time difference between the two methods. Therefore, in actual projects, if we really need to use the insertion sort algorithm, I personally recommend using binary insertion sort. Binary insertion may not be better than direct insertion in terms of space usage, because binary insertion requires more other variables than direct insertion. So when we only have dozens of data, run the above two codes again, you will be surprised to find that the time of the former (binary insertion) is actually longer than the latter (direct insertion). This is because so many variables need to allocate memory for them, and the time spent accounts for a large proportion of the entire running process, so the time of the former is longer than the latter. However, as the amount of data increases, the proportion of time allocated for variables gradually becomes smaller and smaller, which can be almost ignored. Therefore, when the amount of data is large, the time of the former is shorter than the latter. Moreover, with the current hardware level, in my opinion, the advantage of time can make up for the relative lack of space. If in actual situations our data volume really reaches the point where the advantage of time can no longer make up for the space, then there are other sorting algorithms for us to choose.
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.
Related Articles
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 - merge sort (non-recursive implementatio
Publish Date:2025/03/19 Views:188 Category:ALGORITHM
-
In the article "Merge Sort", we introduced the principles and operation steps of merge sort, and finally implemented the sorting algorithm using PHP code. In the program, we used the principle of recursion to implement the algorithm. In fac
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 - quick sort (non-recursive implementatio
Publish Date:2025/03/19 Views:78 Category:ALGORITHM
-
In the article "Quick Sort", we introduced the principles and steps of quick sort, and implemented the algorithm using recursion. In the previous article, we also mentioned the use of non-recursive methods to implement the algorithm. In thi
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
The road to learning sorting algorithms - selection sort
Publish Date:2025/03/19 Views:160 Category:ALGORITHM
-
Selection sort is a simple and intuitive sorting algorithm. Its basic idea is to select a maximum (or minimum) element in an unsorted sequence and put it at the end (note: this is the end of the unsorted sequence, which can be considered as