super fast sort algorithm in js

[xgqfrms]

super fast sort algorithm in js

sort algorithm

1. Promise.race (return the fast one)
2. Async / Await

// chrome & fast sort 快速排序

// firefox & merge sort 归并排序

const superFastSort = (arr = []) => {
  let result = [];
  // Promise.race + Async / Await
  return result;
}

https://www.cnblogs.com/xgqfrms/p/13090521.html

[xgqfrms]

shuffle 洗牌

算法

1. binary 分组，交叉交换，指定次数

arr = [1, 2, 3, 4];

// ES 6 解构交换 swap
[c, d, a, b] = [1: a, 2: b, 3: c, 4: d];


left = [1, 2];
right = [3, 4];

bug

variable

ES6 解构交换元素

let a = 1;
let b = 2;

[ a, b ] = [ b, a ];

console.log(a); 
// 2
console.log(b); 
// 1

[xgqfrms]

merge sort

https://developer.mozilla.org/en-US/docs/Tools/Performance/Examples/Sorting_algorithms_comparison

https://humanwhocodes.com/blog/2012/10/02/computer-science-and-javascript-merge-sort/

https://bugzilla.mozilla.org/show_bug.cgi?id=224128

[xgqfrms]

https://developer.mozilla.org/en-US/docs/Tools/Performance/Examples/Sorting_algorithms_comparison

https://mdn.github.io/performance-scenarios/js-call-tree-1/index.html

[xgqfrms]

var arrayLength = 1000;
var iterations = 200;
var min = 0;
var max = 1000000;

/**
 * Bubble sort
 */

function swap(items, firstIndex, secondIndex){
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

function bubbleSort(items){

    var len = items.length,
        i, j, stop;

    for (i=0; i < len; i++){
        for (j=0, stop=len-i; j < stop; j++){
            if (items[j] > items[j+1]){
                swap(items, j, j+1);
            }
        }
    }

    return items;
}

/**
 * Selection sort
 */

function selectionSort(items){

    var len = items.length,
        min;

    for (i=0; i < len; i++){

        //set minimum to this position
        min = i;

        //check the rest of the array to see if anything is smaller
        for (j=i+1; j < len; j++){
            if (items[j] < items[min]){
                min = j;
            }
        }

        //if the minimum isn't in the position, swap it
        if (i != min){
            swap(items, i, min);
        }
    }

    return items;
}

/**
 * Quicksort
 */

function partition(items, left, right) {

    var pivot   = items[Math.floor((right + left) / 2)],
        i       = left,
        j       = right;


    while (i <= j) {

        while (items[i] < pivot) {
            i++;
        }

        while (items[j] > pivot) {
            j--;
        }

        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }

    return i;
}

function quickSort(items, left, right) {

    var index;

    if (items.length > 1) {

        left = typeof left != "number" ? 0 : left;
        right = typeof right != "number" ? items.length - 1 : right;

        index = partition(items, left, right);

        if (left < index - 1) {
            quickSort(items, left, index - 1);
        }

        if (index < right) {
            quickSort(items, index, right);
        }

    }

    return items;
}

function sort(unsorted) {
  console.log(bubbleSort(unsorted));
  console.log(selectionSort(unsorted));
  console.log(quickSort(unsorted));
}

function sortAll() {
  for (var i = 2; i <= iterations; ++i) {
    var unsorted = [];
    for (var j = 0; j < arrayLength; j++) {
      var element = Math.floor(Math.random() * (max - min + 1)) + min;
      unsorted.push(element);
    }
    sort(unsorted);
  }
}

var sortButton = document.getElementById("sort");
sortButton.addEventListener("click", sortAll, false);var arrayLength = 1000;
var iterations = 200;
var min = 0;
var max = 1000000;

/**
 * Bubble sort
 */

function swap(items, firstIndex, secondIndex){
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

function bubbleSort(items){

    var len = items.length,
        i, j, stop;

    for (i=0; i < len; i++){
        for (j=0, stop=len-i; j < stop; j++){
            if (items[j] > items[j+1]){
                swap(items, j, j+1);
            }
        }
    }

    return items;
}

/**
 * Selection sort
 */

function selectionSort(items){

    var len = items.length,
        min;

    for (i=0; i < len; i++){

        //set minimum to this position
        min = i;

        //check the rest of the array to see if anything is smaller
        for (j=i+1; j < len; j++){
            if (items[j] < items[min]){
                min = j;
            }
        }

        //if the minimum isn't in the position, swap it
        if (i != min){
            swap(items, i, min);
        }
    }

    return items;
}

/**
 * Quicksort
 */

function partition(items, left, right) {

    var pivot   = items[Math.floor((right + left) / 2)],
        i       = left,
        j       = right;


    while (i <= j) {

        while (items[i] < pivot) {
            i++;
        }

        while (items[j] > pivot) {
            j--;
        }

        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }

    return i;
}

function quickSort(items, left, right) {

    var index;

    if (items.length > 1) {

        left = typeof left != "number" ? 0 : left;
        right = typeof right != "number" ? items.length - 1 : right;

        index = partition(items, left, right);

        if (left < index - 1) {
            quickSort(items, left, index - 1);
        }

        if (index < right) {
            quickSort(items, index, right);
        }

    }

    return items;
}

function sort(unsorted) {
  console.log(bubbleSort(unsorted));
  console.log(selectionSort(unsorted));
  console.log(quickSort(unsorted));
}

function sortAll() {
  for (var i = 2; i <= iterations; ++i) {
    var unsorted = [];
    for (var j = 0; j < arrayLength; j++) {
      var element = Math.floor(Math.random() * (max - min + 1)) + min;
      unsorted.push(element);
    }
    sort(unsorted);
  }
}

var sortButton = document.getElementById("sort");
sortButton.addEventListener("click", sortAll, false);

[xgqfrms]

demos

js custom array sort

type JSONValue = null | boolean | number | string | JSONValue[] | { [key: string]: JSONValue };
type Fn = (value: JSONValue) => number

function sortBy(arr: JSONValue[], fn: Fn): JSONValue[] {
  return arr.sort((a, b) => fn(a) - fn(b) > 0 ? 1 : -1);
};


// arr = [5, 4, 1, 2, 3]
// arr.sort((a,b) => a - b > 0 ? 1 : -1);
//升序 ascending

https://leetcode.com/problems/sort-by/?envType=study-plan-v2&envId=30-days-of-javascript