JavaScript implements insertion sort of classic sorting algorithm

Although the code implementation of insertion sort is not as simple and crude as bubble sort and selection sort, its principle should be the easiest to understand, because anyone who has played poker should be able to understand it in seconds. Like sorting a hand of poker, we start with our left hand empty and the cards on the table face down. We then take one card at a time from the table and insert it into the correct position in the left hand. To find the correct position of a card, we compare it with every card already in the hand from right to left. The cards held in the left hand are always sorted and originally were the top cards in the pile on the table. .

1) Algorithm principle

The algorithm description of insertion sort (Insertion-Sort) is a simple and intuitive sorting algorithm. It works by building an ordered sequence. For unsorted data, it scans from back to front in the sorted sequence to find the corresponding position and insert it. In the implementation of insertion sort, in-place sorting is usually used (that is, sorting that only uses O(1) extra space). Therefore, during the scanning process from back to front, it is necessary to repeatedly and gradually shift the sorted elements backward. , providing insertion space for the latest element.

2) Algorithm description and implementation

Generally speaking, insertion sort is implemented on the array using in-place. The specific algorithm is described as follows:

f35d6e602fd7d0f0edfa6f7d103c1b57 Starting from the first element, the element can be considered to have been sorted;

2cc198a1d5eb0d3eb508d858c9f5cbdb Take out the next element, after the sorted element Scan from back to front in the sequence;

5bdf4c78156c7953567bb5a0aef2fc53 If the element (sorted) is larger than the new element, move the element to the next position;

23889872c2e8594e0f446a471a78ec4c Repeat the steps 3. Until you find a position where the sorted element is less than or equal to the new element;

43ad812d3a971134e40facaca816c822 After inserting the new element into that position;

efbfa0de8737dc86eae413541a49df20 Repeat steps 2~5 .

3) JavaScript code implementation

function insertSort(arr) { 
    for (var i = 1; i < arr.length; i++) { 
      var temp = arr[i]; 
      var j = i - 1; 
      while (j >= 0 && arr[j] > temp) { 
        arr[j + 1] = arr[j]; 
         j--; 
      } 
      arr[j + 1] = temp; 
    } 
    return arr; 
 } 
var arr = [1, 45, 37, 5, 48, 15, 37, 26, 29, 2, 46, 4, 17, 50, 52]; 
console.log(insertSort(arr));

Improved insertion sort: Use binary search when finding the insertion position.

Steps:
                                                                                                                                                                                                                                                             In the sequence, the two points were found to find the first number larger than it;
& lt; 3 & gt; insert the new element after the location;

function binaryInsertionSort(arr) { 
   for (var i = 1; i < arr.length; i++) { 
     var key = arr[i],left = 0,right = i - 1; 
     while (left <= right) { 
        var middle = parseInt((left + right) / 2); 
        if (key < arr[middle]) { 
          right = middle - 1; 
        } else { 
          left = middle + 1; 
        } 
     } 
     for (var j = i - 1; j >= left; j--) { 
        arr[j + 1] = arr[j]; 
     } 
     arr[left] = key; 
    } 
    return arr; 
} 
var arr = [1, 45, 37, 5, 48, 15, 37, 26, 29, 2, 46, 4, 17, 50, 52]; 
console.log(binaryInsertionSort(arr));

4) ## Best case: the input array is sorted in ascending order. T(n) = O(n)

Worst case: the input array is sorted in descending order. T(n) = O(n2)
Average situation: T(n) = O(n2)

The above is the entire content of this article. I hope it will be helpful to everyone’s study. I also hope that everyone will learn more. Support PHP Chinese website.

For more articles related to insertion sort using JavaScript to implement the classic sorting algorithm, please pay attention to the PHP Chinese website!