Summary of seven sorting algorithms implemented in JavaScript (recommended!)

Preface

The so-called sorting algorithm is to re-sort one or more groups of data according to a predetermined pattern through specific algorithm factors. This new sequence follows certain rules and reflects certain regularities. Therefore, the processed data is easy to screen and calculate, which greatly improves the computing efficiency. For sorting, we first require it to have a certain stability, that is, when two identical elements appear in a sequence at the same time, after a certain sorting algorithm, the relative positions of the two before and after sorting do not change. In other words, even if two elements are exactly the same, they are distinguished during the sorting process and confusion is not allowed.

Bubble Sort

Bubble sort is an entry-level algorithm, but it also has some interesting ways to play with it. Generally speaking, there are three ways to write bubble sort:

Compare and swap two by two at a time, bubbling the maximum/minimum value to the last digit;
Optimized writing method: Use a variable to record whether an exchange has occurred in the current round of comparison. If no exchange has occurred, it means that the order is already in order and no further sorting is done.

Basic Algorithm

The space complexity is O(1) and the time complexity is O(n2)

const sort = (arr) => {
    for (let i = 0, len = arr.length; i < len-1; i++){
        for (let j = 0; j < len-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }
    return arr
}

After each round of the outermost for loop, the maximum value of the remaining numbers will be moved to the last digit of the current round, and some adjacent numbers will be exchanged in the middle to become orderly. The total number of comparisons is (n-1)+(n-2)+(n-3)+…+1(n−1)+(n−2)+(n−3)+…+1.

The second way of writing is improved based on the basic algorithm:

const sort = (arr) => {
    for (let i = 0, len = arr.length; i < len - 1; i++) {
        let isSwap = false
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                isSwap = true
            }
        }
        if (!isSwap) {
            break;
        }
    }
    return arr;
};

The space complexity is O(1); the time complexity is O(n2) - preferably O(n);

Each time the outermost for loop passes through a round, the maximum value of the remaining numbers is still moved to the last digit of the current round. The advantage of this method over the first one is that if no exchange occurs in a round of comparison, the sorting stops immediately because the remaining numbers must be in order at this time.

Selection Sort

The idea of ​​selection sort is to traverse the array in a double loop, find the subscript of the smallest element after each round of comparison, and swap it to the first place.

Basic Algorithm

const sort = (arr) => {
    for (let i = 0, len = arr.length; i < len - 1; i++) {
        let minIndex = i
        for (let j = i+1; j < len; j++) {
            if (arr[i] > arr[j]) {
                minIndex = j
            }
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
    return arr;
};

Binary Selection Sort - Optimization

The selection sort algorithm can also be optimized. Since the minimum value is found in each round of traversal, why not find the maximum value as well? This is the idea of ​​binary selection sort.

Using binary selection sort, recording the minimum and maximum values ​​in each round of selection, can reduce the range of the array that needs to be traversed by half.

const sort = (arr) => {
    for (let i = 0, len = arr.length; i < len / 2; i++) {
        let minIndex = i;
        let maxIndex = i;
        for (let j = i + 1; j < len-i; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
            if (arr[maxIndex] < arr[j]) {
                maxIndex = j;
            }
        }
        if (minIndex === maxIndex) break;
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        if (maxIndex === i) {
            maxIndex = minIndex;
        }
        const lastIndex = len - i - 1;
        [arr[maxIndex], arr[lastIndex]] = [arr[lastIndex], arr[maxIndex]];
    }
    return arr; 
};

Insertion Sort

The idea of ​​insertion sort is very simple. There is a very common scenario in life: when playing poker, we sort the cards as we draw them. Each time we draw a card, we insert it into the appropriate position in the existing cards in our hand, gradually completing the entire sort.

There are two ways to write insertion sort:

• Exchange method: When inserting new numbers, keep exchanging them with the previous numbers until they find their appropriate position.
• Moving method: During the process of inserting a new number, it is constantly compared with the previous number, and the previous number is constantly moved backwards. When the new number finds its position, it can be inserted once.
  

Insertion sort by swapping

const sort = (arr) => {
    for (let i = 1, len = arr.length; i < len; i++) {
        let j = i;
        while (j >= 1 && arr[j] < arr[j - 1]) {
            [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
            j--
        }
    }
    return arr;
};

When there are less than two numbers, there is no sorting problem, and of course no insertion is required, so we insert directly from the second number forward.

Mobile method

We found that in the exchange method insertion sort, the numbers have to be exchanged each time. But in reality, the newly inserted number does not necessarily fit into the position of the number it is swapped with. That is to say, it has just been moved to the new position for a short time. After the next comparison, if it needs to be exchanged again, it will be immediately moved to the position of the previous number.

From this, we can think of an optimization solution: let the newly inserted number be compared first, and the numbers that are larger than it in front are constantly moved backwards until a suitable position for the new number is found and then inserted.

In this solution, we need to temporarily store the newly inserted numbers. The code is as follows:

const sort = (arr) => {
    for (let i = 1, len = arr.length; i < len; i++) {
        let j = i-1;
        let cur = arr[i];
        while (j >= 0 && cur < arr[j]) {
            arr[j+1] = arr[j]
            j--;
        }
        arr[j+1] = cur
    }
    return arr;
};

Shell sort

In July 1959, Donald Shell, a Ph.D. in mathematics from the University of Cincinnati, published the Shell sort algorithm in Communications of the ACM, which became one of the first algorithms to reduce the time complexity to below O(n2). Although the worst time complexity of the original Shell sort is still O(n2), the optimized Shell sort can reach O(n1.3) or even O(n7/6).

Shell sort is essentially an optimization of insertion sort. It takes advantage of the simplicity of insertion sort and overcomes the disadvantage of insertion sort that it only exchanges two adjacent elements at a time. Its basic idea is:

• The array to be sorted is divided into multiple sub-arrays according to a certain interval, and each group is inserted and sorted separately. Here, grouping by interval does not mean taking a continuous array, but taking a value at a certain interval to form a group.
• Gradually reduce the interval for the next round of sorting
• In the last round, the interval is set to 11, which is equivalent to directly using insertion sort. But after the previous "macro-control", the array is basically ordered, so the insertion sort at this time only needs a small amount of swapping to complete. For example, the process of Shell sorting the array [8, 3, 34, 6, 4, 1, 44, 45, 43, 2, 23] is as follows:
  

First pass (5-interval sorting): Split the subarray into five groups according to the interval of 5, namely [8, 1, 23], [3, 44], [34, 45], [6, 43], [4, 2]. Insert them into sorted order. After sorting, they become: [1, 8, 23], [3, 44], [34, 45], [6, 43], [2, 4] respectively. The entire array becomes [1, 3, 34, 6, 2, 8, 44, 45, 43, 4, 23].

Second pass (2-interval sorting): Split the subarray into two groups according to interval 2, namely [1, 34, 2, 44, 43, 23], [3, 6, 8, 45, 4]. Insertion sort them, and after sorting they become: [1, 2, 23, 34, 43, 44], [3, 4, 6, 8, 45], and the entire array becomes [1, 3, 2, 4, 23, 6, 34, 8, 43, 45, 44]. There is a very important property here: after we complete the 2-interval sorting, the array still remains in 5-interval order. In other words, sorting with smaller intervals does not worsen the result of the previous step.

The third pass (11 interval sort, equal to direct insertion sort): split the subarray according to interval 1 into a group, which is the entire array. Perform insertion sort on it. After the first two sortings, the array is basically in order, so this step only requires a small amount of swapping to complete the sorting. After sorting, the array becomes [1, 2, 3, 4, 6, 8, 23, 34, 43, 44, 45], and the sorting is completed.

const sort = arr => {
    const len ​​= arr.length;
    if (len < 2) {
        return arr;
    }
    let gap = Math.floor(len / 2);
    while (gap > 0) {
        for (let i = gap; i < len; i++) {
            let j = i;
            let cur = arr[i];
            while (j >= 0 && cur < arr[j - gap]) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = cur;
        }
        gap = Math.floor(gap / 2);
    }
    return arr;
}

Heap Sort

The heap sort process is as follows:

1. Use the sequence to build a big top heap, take out the number at the top of the heap (put it at the end of the array to be sorted);
2. Adjust the remaining numbers, build a new big top pile, and take out the top number of the pile again;
3. Repeat the process over and over to complete the entire sorting process.
   

function sort(arr) {
    for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
        adjustHeap(arr, i, arr.length)
    }
    for (let j = arr.length - 1; j > 0; j--) {
        [arr[0], arr[j]] = [arr[j], arr[0]]
        adjustHeap(arr, 0, j)
    }
}

function adjustHeap(arr, i, length) {
    let tmp = arr[i]
    for (let k = i * 2 + 1; k < length; k = k * 2 + 1) {
        if (k + 1 < length && arr[k] < arr[k + 1]) {
            k++;
        }
        if (arr[k] > tmp) {
            arr[i] = arr[k];
            i = k;
        } else {
            break;
        }
        arr[i] = tmp;
    }
}

Quick Sort

The quick sort algorithm was proposed by CAR Hoare in 1960. Its time complexity is also O(nlogn), but among the several sorting algorithms with a time complexity of O(nlogn), it is more efficient in most cases, so quick sort is widely used. In addition, the divide-and-conquer idea adopted by quick sort is very practical, which makes quick sort very popular among interviewers, so it is particularly important to master the idea of ​​quick sort.

The basic idea of ​​the quick sort algorithm is:

1. Take a number from the array, called the pivot
2. Traverse the array, put the numbers larger than the cardinality to its right, and the numbers smaller than the cardinality to its left. After the traversal is completed, the array is divided into two areas: left and right
3. Treat the left and right areas as two arrays and repeat the first two steps until the sorting is complete.
4. In fact, each traversal of quick sort puts the cardinality in the final position. The first round of traversal sorts out 1 cardinality, the second round of traversal sorts out 2 cardins (one cardinality for each area, but if an area is empty, only one cardinality can be sorted out in this round), the third round of traversal sorts out 4 cardins (similarly, in the worst case, only one cardinality can be sorted out), and so on. The total number of traversals is logn~n times, and the time complexity of each round of traversal is O(n), so it is easy to analyze that the time complexity of quick sort is O(nlogn)~O(n2), and the average time complexity is O(nlogn).

const partition = (arr, start, end) => {
    let pivot = arr[start]; // Take the first number as the base let left = start + 1; // Start partitioning from the second number let right = end; // Right boundary // Exit the loop when left and right meet while (left < right) {
        // Find the first position greater than the cardinality while (left < right && arr[left] <= pivot) left++;
        // Swap these two numbers so that the left partition is less than or equal to the cardinality, and the right partition is greater than or equal to the cardinality if (left != right) {
            [arr[left], arr[right]] = [arr[right], arr[left]];
            right--;
        }
    }
    // If left and right are equal, compare arr[right] and pivot separately
    if (left == right && arr[right] > pivot) right--;
    // Swap the base and the middle if (right != start) [arr[left], pivot] = [pivot, arr[left]];
    // Return the subscript of the middle value return right;
}

const quickSort = (arr, start, end) => {
    if (start >= end) return;
    const middle = partition(arr, start, end)
    quickSort(arr, start, middle - 1);
    quickSort(arr, middle + 1, end);
}

const sort = arr => {
    quickSort(arr, 0, arr.length -1);
}

Merge Sort

Merge sort is an effective sorting algorithm based on the merge operation. This algorithm is a very typical application of the Divide and Conquer method. Merge the ordered subsequences to obtain a completely ordered sequence; that is, first order each subsequence, and then order the subsequence segments. If two ordered lists are merged into one ordered list, it is called a 2-way merge.

Algorithm Description

• Split the input sequence of length n into two subsequences of length n/2;
• Merge sort is applied to these two subsequences respectively;
• Merge two sorted subsequences into a final sorted sequence.
  

const merge = (left, right) => {
    let result = [];
    while (left.length > 0 && right.length > 0) {
        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 sort = (arr) => {
    let len ​​= arr.length;
    if (len < 2) {
        return arr;
    }
    const middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(sort(left), sort(right));
};

Summarize

This concludes this article about seven sorting algorithms implemented in JavaScript. For more relevant JavaScript sorting algorithm content, please search 123WORDPRESS.COM’s previous articles or continue to browse the following related articles. I hope everyone will support 123WORDPRESS.COM in the future!