Author: Yan Yi @ Edamame

Chrome browser and Firefox browser on some algorithm implementation differences, encountered a problem before, made a record, and we discuss the following.

I. Problem description

The interface returns the same data. After sorting, the same page is displayed differently in two browsers.

Second, problem location

1. The front-end sorting algorithm is wrong

2. Other factors

After recombing, I found that “sort” was written incorrectly.

Sort (), if it takes no arguments, sorts the elements in the array alphabetically, in alphabetical order.

If a collation function is passed in sort(), you can customize the sort.

Here are the rules:

1. The comparison function should take two arguments, a and b

2, If a is less than B, a should precede B in the sorted array, then return a value less than 0. If a is equal to b, 0 is returned. If a is greater than b, return a value greater than 0.

After the modification, in the process of breaking point verification, it was found that the results of each browser traversal were different, although the final sorting results were the same.

Further investigation revealed that the two browser kernels used different algorithms for sorting.

Firefox sort uses merge sort, Chrome uses insert sort, QuickSort (InsertionSort for arrays less than 10, QuickSort for arrays larger)

Three, the basic implementation and comparison of several algorithms

Merge Sort (Merge Sort)

Basic idea: combine two ordered sequences into an ordered sequence, including top-down and bottom-up methods. The difference lies in the grouping size. The former tends to be divided into two groups at first, while the latter tends to be divided into multiple groups with only one element in each group.

Basic demo:

   // A general implementation of merge sort
    const merge = (left, right) = > {
        const result = [];
        while (left.length && right.length) {
            if(left[0] <= right[0]) {
                result.push(left.shift()); 
            } else {
                result.push(right.shift())
            }
        }
        while(left.length) result.push(left.shift());
        while(right.length) result.push(right.shift());
        return result;
    }
    const mergeSort = arr= > {
        const len = arr.length;
        if (len < 2) {
            return arr;
        }
        let middle = Math.floor(len/2);
        let left = arr.slice(0, middle);
        let right = arr.slice(middle);
        return merge(mergeSort(left), mergeSort(right))
    }
Copy the code

2. Quick Sort

The basic idea is to select a cardinality in the array, place those larger than the cardinality in the right subarray, and those smaller than the cardinality in the left subarray, and then do the same for the left and right arrays until the array is divided into only one element.

Basic demo:

    // A general implementation of quicksort
    const quickSort1 = arr= > {
    if (arr.length <= 1) {
        return arr;
    }
    const midIndex = Math.floor(arr.length / 2);
    const valArr = arr.splice(midIndex, 1);
    const midIndexVal = valArr[0];
    const left = []; 
    const right = []; 
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < midIndexVal) {
            left.push(arr[i]);
        } else{ right.push(arr[i]); }}return quickSort1(left).concat(midIndexVal, quickSort1(right));
};
Copy the code

1, Insertion Sort

This applies when most elements are already sorted.

Basic idea: divide the whole array into two subarrays, one is sorted, one is not sorted, remove a number from the unsorted array each time, put it into the sorted array, until the unsorted array is empty.

Basic demo:

    // A general implementation of insert sort
    const insertionSort = (nums) = > {
        for (let i = 1; i < nums.length; ++i) {
            let preIndex = i - 1;
            let temp = nums[i];
            while (j >=0 && nums[preIndex] > temp) {
                nums[preIndex+1] = nums[preIndex];
                preIndex--;
            }
            nums[preIndex+1] = temp;
        }
        return nums;
    }
Copy the code

Four, performance analysis

Time complexity:

• Merge sort (O(nlogn))
• Quick sort (O(nlogn))
• Insertion sort (O(n²))

Stability:

• Merge sort (stable)
• Quicksort (unstable)
• Insertion sort (stable)

Optimization scheme:

• Insertion sort: Split insertion with binary lookup

const binarySearch = (arr, maxIndex, value) = > {
        let min = 0;
        let max = maxIndex;
        while (min <= max) {
            const mid = Math.floor((min + max) / 2);
            if (arr[mid] <= value) {
                min = mid + 1;
            } else {
                max = mid - 1; }}return min;
    }
const insertionSort2 = (arr) = > {
        for (let i = 1, len = arr.length; i < len; i++) {
            const temp = arr[i];
            const insertIndex = binarySearch(arr, i - 1, arr[i]);
            for (let preIndex = i - 1; preIndex >= insertIndex; preIndex--) {
                arr[preIndex + 1] = arr[preIndex];
            }
            arr[insertIndex] = temp;
        }
        return arr;
    }
Copy the code

• Merge sort: space optimization, array.splice instead of array.slice, to reduce space consumption; For the smaller subarrays, insert sort is used.
• Quicksort: in-place

 const swap = (arr, i, j) = > {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    };
    const partition = (arr, left, right) = > {
        let pivot = left, // Set the pivot value
        index = pivot + 1;
        for (let i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }; 
    const quickSort = (arr, left, right) = > {
        let len = arr.length, index;
        left = typeofleft ! ='number' ? 0 : left;
        right = typeofright ! ='number' ? len- 1 : right;
        if (left < right ) {
            index = partition(arr, left, right);
            quickSort(arr, left, index - 1);
            quickSort(arr, index + 1, right);
        }
        return arr;
    }
Copy the code