Js implementation of six sorting algorithms

This paper will introduce the basic algorithm and advanced algorithm of data sorting. These algorithms only rely on arrays to store data.

 

Array test platform

First, we construct an array test platform class

function CArray(numElements) {
    this.dataStore = [];
    this.numElements = numElements;
    this.toString = toString;
    this.clear = clear;
    this.setData = setData;
    this.swap = swap;
}
function setData() {
    for (var i = 0; i < this.numElements; ++i) {
    this.dataStore[i] = Math.floor(Math.random() * (this.numElements + 1));
    }
}
function clear() {
    for (var i = 0; i < this.numElements; ++i) {
    this.dataStore[i] = 0;
    }
}
function toString() {
    var restr = "";
    for (var i = 0; i < this.numElements; ++i) {
    restr += this.dataStore[i] + " ";
    if (i > 0 && i % 10 == 0) {
        restr += "\n";
    }
    }
    return restr;
}
function swap(arr, index1, index2) {
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

Using test platform classes

var numElements = 100;
var myNums = new CArray(numElements);
myNums.setData();
console.log(myNums.toString());

 

Basic sorting algorithm

These algorithms very realistically simulate the human sorting of data in real life.

 

Bubble sorting

It is one of the slowest sorting algorithms, but it is also one of the easiest sorting algorithms to implement. Bubble sorting is called because when sorting with this sorting algorithm, data values float from one end of the array to the other like bubbles. Suppose you are arranging a set of numbers in ascending order, the larger values float to the right of the array and the smaller values float to the left of the array. The reason why the algorithm moves the values of the adjacent data more than once in the array on the left is that they are greater than the values of the adjacent data in the array.

Bubble sort code

function bubbleSort() {
    var numElements = this.dataStore.length;
    for (var outer = numElements; outer >= 2; --outer) {
        for (var inner = 0; inner < outer - 1; ++inner) {
            if (this.dataStore[inner] > this.dataStore[inner + 1]) {
                this.swap(this.dataStore, inner, inner + 1);
            }
        }
    }
}

The outer layer loop limits the unordered range (from numElements to 2). The inner layer loop starts from the data on the left to compare and exchange step by step, so that the largest number in the unordered range moves to the far right, and the outer layer sorting range continues to shrink until there are two unordered elements left, and then the comparison and exchange completes the sorting

 

Select sort

Select sort to start at the beginning of the array and compare the first element with other elements. After checking all the elements, the smallest element will be placed in the first position of the array, and then the algorithm will continue from the second position. This process continues. When it reaches the penultimate position of the array, all data is sorted.

function selectionSort() {
    var min;
    for (var outer = 0; outer <= this.dataStore.length - 2; ++outer) {
        min = outer;
        for (var inner = outer + 1; inner <= this.dataStore.length - 1; ++inner) {
            if (this.dataStore[inner] < this.dataStore[min]) {
                min = inner;
            }
        }
        swap(this.dataStore, outer, min);
    }
}

 

Insert sort

Insert sort has two cycles. The outer loop moves the array elements one by one, while the inner loop compares the selected elements in the outer loop. If the element selected in the outer loop is smaller than the element selected in the inner loop, the array element will move to the right to make room for this element in the inner loop.

function insertionSort() {
    var temp, inner;
    for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
    temp = this.dataStore[outer];
    inner = outer;
    while (inner > 0 && (this.dataStore[inner - 1] >= temp)) {
        this.dataStore[inner] = this.dataStore[inner - 1];
        --inner;
    }
    this.dataStore[inner] = temp;
    }
}

 

Timing comparison of basic sorting algorithms

10000 random number tests

bubbleSort();// About 100ms
selectionSort();// About 50ms
insertionSort();// About 27ms

Selection sort and insertion sort are faster than bubble sort, and insertion sort is the fastest of the three algorithms.

 

Advanced sorting algorithm

Shell Sort

Hill sort has made a great improvement on the basis of insertion sort. It first compares distant elements, not adjacent elements. This allows elements far from the correct position to return to the right position faster. When this algorithm is used to traverse the data set, the distance between all elements will continue to decrease until it is processed to the end of the data set. At this time, the algorithm compares the adjacent elements. Hill sorting works by defining a sequence of intervals to indicate how far apart elements are compared in the sorting process. We can define the interval sequence dynamically, but the interval sequence used in most scene algorithms can be defined in advance.   

The interval sequence defined by Marchin Ciura in a paper published is 701301132,57,23,10,4,1. Here, we use a small data set to see how the algorithm works.  

function shellsort() {
    var temp;
    for (var g = 0; g < this.gaps.length; ++g) {
    for (var i = this.gaps[g]; i < this.dataStore.length; ++i) {
        temp = this.dataStore[i];
        for (var j = i; j >= this.gaps[g] && this.dataStore[j-this.gaps[g]] > temp; j -= this.gaps[g]) {
        this.dataStore[j] = this.dataStore[j - this.gaps[g]];
        }
        this.dataStore[j] = temp;
    }
    }
}

We need to add the definition of interval sequence in the CArray class:

this.gaps = [5,3,1];

 

Calculate dynamic interval sequence

Sedgewick's algorithm determines the initial interval value through the following code fragment:

var N = this.dataStore.length;
var h = 1;
while (h < N/3) {
    h = 3 * h + 1;
}

After the interval value is determined, this function can run like the previously defined shellsort() function. The only difference is that it returns to the last statement before the outer loop to calculate a new interval value:

h = (h-1)/3;

Hill sorting of dynamically calculated interval sequences

function shellsort1() {
    var N = this.dataStore.length;
    var h = 1;
    while (h < N/3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (var i = h; i < N; i ++) {
            for (var j = i; j >= h && this.dataStore[j] < this.dataStore[j-h]; j -= h) {
                this.swap(this.dataStore, j, j - h);
            }
        }
        h = (h-1)/3;
    }
}

For sorting test of 10000 random numbers:

myNums.shellsort(); // About 20ms
myNums.shellsort1(); // About 8ms

 

Merge sort

Merge sort combines a series of ordered subsequences into a large complete ordered sequence. We need two ordered subarrays, then insert from the smallest data by comparing the data size, and finally merge to get the third array. However, in practice, there are still some problems in merge sorting. We need more space to merge and store two sub arrays.

Bottom up merge sort generally speaking, merge sort will be realized by recursive algorithm. However, this approach is not feasible in JavaScript because the depth of recursion is too deep. Therefore, we use a non recursive way to implement this algorithm. This strategy is called bottom-up merge sorting. This algorithm first decomposes the data set into a set of arrays with only one element. Then create a set of left and right sub arrays and merge them slowly. Each merge saves part of the ordered data until all the data of the last remaining array has been sorted perfectly. Algorithm code

function mergeSort() {
    var arr = this.dataStore;
    if (arr.length < 2) {
    return;
    }
    var step = 1;
    var left, right;
    while (step < arr.length) {
    left = 0;
    right = step;
    while (right + step <= arr.length) {
        this.mergeArrays(arr, left, left+step, right, right+step);
        left = right + step;
        right = left + step;
    }
    if (right < arr.length) {
        this.mergeArrays(arr, left, left+step, right, arr.length);
    }
    step *= 2;
    }
}

function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
    var rightArr = new Array(stopRight - startRight + 1);
    var leftArr = new Array(stopLeft - startLeft + 1);
    k = startRight;
    for (var i = 0; i < (rightArr.length-1); ++i) {
    rightArr[i] = arr[k];
    ++k;
    }
    k = startLeft;
    for (var i = 0; i < (leftArr.length-1); ++i) {
    leftArr[i] = arr[k];
    ++k;
    }
    rightArr[rightArr.length - 1] = Infinity;
    leftArr[leftArr.length - 1] = Infinity;
    var m = 0;
    var n = 0;
    for (var k = startLeft; k < stopRight; ++k) {
    if (leftArr[m] <= rightArr[n]) {
        arr[k] = leftArr[m];
        m++;
    } else {
        arr[k] = rightArr[n];
        n++;
    }
    }
}

 

Quick sort

Quick sorting is one of the fastest sorting algorithms for dealing with large data sets. It is a divide and conquer algorithm, which decomposes the data into different subsequences containing smaller elements and larger elements by recursive method. The algorithm repeats this step until all data are in order. This algorithm first selects an element in the list as the reference value (pivot). Data sorting is carried out around the benchmark value, moving the elements in the list that are less than the benchmark value to the bottom of the array and the elements that are greater than the benchmark value to the top of the array.

Algorithm pseudo code

  1. Select a base element to separate the list into two subsequences
  2. Reorder the values of all elements before the benchmark, and reorder the values of all elements below the benchmark
  3. Repeat steps 1 and 2 for subsequences of smaller elements and subsequences of larger elements respectively. The procedure is as follows:
function qSort(list) {
    var list;
    if (list.length == 0) {
        return [];
    }
    var lesser = [];
    var greater = [];
    var pivot = list[0];
    for (var i = 1; i < list.length; i ++) {
        if (list[i] < pivot) {
        lesser.push(list[i]);
        } else {
        greater.push(list[i]);
        }
    }
    return this.qSort(lesser).concat(pivot, this.qSort(greater));
}

Output the sorting process before the qSort function returns

console.log(lesser.concat(pivot, greater).toString());

10000 random number sorting test

qSort(); // About 17ms

Fast sorting algorithm is very suitable for large data sets; Performance degrades when dealing with small data sets.

Resource search website Encyclopedia https://www.renrenfan.com.cn Guangzhou VI design companyhttps://www.houdianzi.com

(attached) test platform code

<!DOCTYPE html>
<html lang="en">
<head>
</head>
<body>
  <script>
    function CArray(numElements) {
      // this.dataStore = [72, 54, 58, 30, 31, 78, 2, 77, 82, 72];
      this.dataStore = [];
      // this.dataStore = [44, 75, 23, 43, 55, 12, 64, 77 ,33];
      this.numElements = numElements;
      this.toString = toString;
      this.clear = clear;
      this.setData = setData;
      this.swap = swap;
      this.bubbleSort = bubbleSort;
      this.selectionSort = selectionSort;
      this.insertionSort = insertionSort;
      this.shellsort = shellsort;
      this.shellsort1 = shellsort1;
      this.mergeSort = mergeSort;
      this.mergeArrays = mergeArrays;
      this.qSort = qSort;
      this.gaps = [5, 3, 1];
    }
    function setData() {
      for (var i = 0; i < this.numElements; ++i) {
        this.dataStore[i] = Math.floor(Math.random() * (this.numElements + 1));
      }
    }
    function clear() {
      for (var i = 0; i < this.numElements; ++i) {
        this.dataStore[i] = 0;
      }
    }
    function toString() {
      var restr = "";
      for (var i = 0; i < this.numElements; ++i) {
        restr += this.dataStore[i] + " ";
        if (i > 0 && i % 10 == 0) {
          restr += "\n";
        }
      }
      return restr;
    }
    function swap(arr, index1, index2) {
      var temp = arr[index1];
      arr[index1] = arr[index2];
      arr[index2] = temp;
    }
    function selectionSort() {
        var min;
        for (var outer = 0; outer <= this.dataStore.length - 2; ++outer) {
            min = outer;
            for (var inner = outer + 1; inner <= this.dataStore.length - 1; ++inner) {
                if (this.dataStore[inner] < this.dataStore[min]) {
                    min = inner;
                }
            }
            swap(this.dataStore, outer, min);
        }
    }
    function bubbleSort() {
        var numElements = this.dataStore.length;
        for (var outer = numElements; outer >= 2; --outer) {
            for (var inner = 0; inner < outer - 1; ++inner) {
                if (this.dataStore[inner] > this.dataStore[inner + 1]) {
                    this.swap(this.dataStore, inner, inner + 1);
                }
            }
        }
    }
    function insertionSort() {
      var temp, inner;
      for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
        temp = this.dataStore[outer];
        inner = outer;
        while (inner > 0 && (this.dataStore[inner - 1] >= temp)) {
          this.dataStore[inner] = this.dataStore[inner - 1];
          --inner;
        }
        this.dataStore[inner] = temp;
      }
    }
    function shellsort() {
      var temp;
      for (var g = 0; g < this.gaps.length; ++g) {
        for (var i = this.gaps[g]; i < this.dataStore.length; ++i) {
          temp = this.dataStore[i];
          for (var j = i; j >= this.gaps[g] && this.dataStore[j-this.gaps[g]] > temp; j -= this.gaps[g]) {
            this.dataStore[j] = this.dataStore[j - this.gaps[g]];
          }
          this.dataStore[j] = temp;
        }
      }
    }
    function shellsort1() {
      var N = this.dataStore.length;
      var h = 1;
      while (h < N/3) {
          h = 3 * h + 1;
      }
      while (h >= 1) {
          for (var i = h; i < N; i ++) {
              for (var j = i; j >= h && this.dataStore[j] < this.dataStore[j-h]; j -= h) {
                  this.swap(this.dataStore, j, j - h);
              }
          }
          h = (h-1)/3;
      }
    }
    function mergeSort() {
      var arr = this.dataStore;
      if (arr.length < 2) {
        return;
      }
      var step = 1;
      var left, right;
      while (step < arr.length) {
        left = 0;
        right = step;
        while (right + step <= arr.length) {
          this.mergeArrays(arr, left, left+step, right, right+step);
          left = right + step;
          right = left + step;
        }
        if (right < arr.length) {
          this.mergeArrays(arr, left, left+step, right, arr.length);
        }
        step *= 2;
      }
    }
    function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
      var rightArr = new Array(stopRight - startRight + 1);
      var leftArr = new Array(stopLeft - startLeft + 1);
      k = startRight;
      for (var i = 0; i < (rightArr.length-1); ++i) {
        rightArr[i] = arr[k];
        ++k;
      }
      k = startLeft;
      for (var i = 0; i < (leftArr.length-1); ++i) {
        leftArr[i] = arr[k];
        ++k;
      }
      rightArr[rightArr.length - 1] = Infinity;
      leftArr[leftArr.length - 1] = Infinity;
      var m = 0;
      var n = 0;
      for (var k = startLeft; k < stopRight; ++k) {
        if (leftArr[m] <= rightArr[n]) {
          arr[k] = leftArr[m];
          m++;
        } else {
          arr[k] = rightArr[n];
          n++;
        }
      }
    }
    function 

Posted by Assorro on Mon, 02 May 2022 18:25:33 +0300