Javascript array.sort principle implementation

  • V8 engine sorting algorithm source (710 line)
  • Js sort principle
  • Ten classic Algorithms

Js provides the sort method, which is convenient for sorting arrays. However, the sort method of JS may be resolved differently by different engines. Based on the implementation of sort sort by V8 engine, this paper analyzes the insertion sort and quicksort used by it.

This article does not attempt to analyze the v8 engine source code, but only the two algorithms used internally

Insertion sort

Here’s a GIF demo.

The basic idea

Iterate over the number group from left to right, and insert the traversed items into the sorted array before each time. By constructing the ordered sequence, scan the unsorted data from back to front in the sorted sequence to find the corresponding position and insert.

Algorithm steps

  1. The first term is sorted by default
  2. Iterating from the second item in the array, fetching the new element currently iterated.
  3. Look forward from the current item, or move back one bit if the item is larger than the new element
  4. Find the position of the new element in the ordered sequence (the item is smaller than the new element, because the new element is behind the element, in the empty space) and put the new element in
  5. Continue traversing, repeating 2-4.

Code implementation

function InsertionSort(arr, from = 0, to = arr.length) {
  // iterate over the second item in the array
  for (var i = from + 1; i < to; i++) {
    // Fetch the new element
    var element = arr[i];
    // Look forward to the new element
    for (var j = i - 1; j >= from; j--) {
      // Cache the search item
      var tmp = arr[j];
      // Calculate whether the insertion position is needed
      // Insert logic can be changed here
      var order = tmp - element;
      if (order > 0) {
        // Instead of insert position, search item moves back
        arr[j + 1] = tmp;
      } else {
        // Is insert position, exit loop, insert element
        break; }}// Exit the loop to insert elements
    arr[j + 1] = element; }};Copy the code

Quick sort

Quicksort, also known as partition swap sort. A quick sort algorithm based on divide-and-conquer strategy. Here the main implementation of in-place idea of quick sort

Algorithm thought

The basic idea of quicksort is that the records to be sorted are separated into two independent parts through a sort. If the keywords of one part of the records are smaller than those of the other part, the two parts of the records can be sorted separately to achieve the order of the whole sequence.

Algorithm steps

  1. Base selection: To select an element in the data structure as the base (pivot)
  2. Partition: According to the size of the value of the base element, partition the disorderly area, all the data smaller than the base element into one interval, all the data larger than the base element into another interval, after the partitioning operation, the position of the base element is the position it should be in after the final sorting
  3. Recursion: for the first two unordered intervals, recursively call the algorithm of step 1 and step 2, until all the unordered intervals only have one element left.

Code implementation

Here according to the implementation method of partition operation is divided into the following two implementation methods

  • A method of squeezing the base element in the middle
    1. Take the first term as the reference element (can be understood as the first term empty pit)
    2. Find the element smaller than the base element from back to front, and fill in the pit, leaving behind the pit.
    3. Find the element larger than the base element from front to back, and fill the rear space to make the front hole empty
    4. Repeat 2 to 3
    5. End when the position is exactly in the middle and place the reference element into the last vacant space
/ * * * * * https://www.runoob.com/w3cnote/quick-sort.html quick sort algorithm@param {*} arr
 * @param {*} left
 * @param {*} right* /

function quickSort(arr, left = 0, right = arr.length - 1) {

  function partition(arr, left, right) {
    const povit = arr[left];
    while (left < right) {
      while (left < right && arr[right] >= povit) {
        right--;
      }
      if (left < right) {
        arr[left] = arr[right]; // add s[right] to s[left] and create a new pit
        left++;
      }

      while (left < right && arr[left] < povit) {
        left++;
      }

      if (left < right) {
        arr[right] = arr[left]; // add s[right] to s[left] and create a new pit
        right--;
      }
    }

    arr[left] = povit;
    return left;
  }


  if (left < right) {
    / / partition
    const partitionIndex = partition(arr, left, right);
    quickSort(arr, left, partitionIndex);
    quickSort(arr, partitionIndex + 1, right);
  }
  return arr;
}
Copy the code
  • The idea of sequential traversal partitioning
    1. Take the rightmost element as the base
    2. Records the last position of the array that is smaller than the base element after alignment
    3. Traverse the array from left to right
    4. Less than the baseline, move to the last position after comparison, and update the last position
    5. After the traversal is complete and the base element is added to the last position.
function quickSort1(arr) {
  / / exchange
  function swap(arr, a, b) {
    [arr[a],arr[b]] = [arr[b],arr[a]]
  }

  / / partition
  function partition(arr, left, right) {
    /** * If you do not know where the final pivot will be placed at the beginning, you can switch the pivot to the back
    const pivot = arr[right];
    /** * The space may contain elements larger than Pivot, so declare a storeIndex variable and initialize it to left to store elements smaller than Pivot in turn. * /
    let storeIndex = left;
    for (let i = left; i < right; i++) {
      if (arr[i] < pivot) {
        /** * loop through the array to find the element less than pivot (elements larger than pivot will be skipped) * swap the element I times to storeIndex and increment storeIndex by 1 to indicate the next possible position to swap */swap(arr, storeIndex, i); storeIndex++; }}// Finally: The pivot is swapped to storeIndex and the base element is placed in its final correct position
    swap(arr, right, storeIndex);
    return storeIndex;
  }

  function sort(arr, left, right) {
    if (left > right) return;

    const storeIndex = partition(arr, left, right);
    sort(arr, left, storeIndex - 1);
    sort(arr, storeIndex + 1, right);
  }

  sort(arr, 0, arr.length - 1);
  return arr;
}
Copy the code