In this paper, some sorting algorithms are simply analyzed, and the javascript code implementation is given. Because this article contains a large number of sorting algorithms, so the analysis will not be very detailed, for students who have a certain understanding of sorting algorithms.

This article isn’t much, but it’s a lot of lines of code.

Article starts on my personal blog site: blog. Fstars. Wang / 2019/04/28 /…

The overview

The default data structure to be sorted is an array, and the time complexity is the average time complexity.

Sorting algorithm Time complexity Spatial complexity Is stable
Bubble sort O(n^2) O(1) stable
Insertion sort O(n^2) O(1) stable
Selection sort O(n^2) O(1) unstable
Merge sort O(nlogn) O(n) stable
Quick sort O(nlogn) O(1) unstable

The following code implementation, sort by default is from small to large sort.

All of the code

My JS code implementation is on Github: github.com/F-star/js-D…

The code is for reference only.

Bubble Sort

Let’s say that the data that you want to bubble sort is of length n.

Bubble sort bubbles multiple times, each time comparing adjacent data, and if the previous data is larger than the next data, they are swapped (that is, the larger data is left behind). So each time you swap, at least one of the elements is going to be moved to where it should be. Repeat the bubble n times, or n minus 1 times, and you’re done sorting.

In particular, the i-th (I starting from 0) bubble compares and swaps the first n-i elements of the array as many times as size-i-1.

Bubble sort takes n-1 bubbles in total (you could say n bubbles, but the last bubble is only one element, so don’t compare).

To optimize the

Sometimes, you can only bubble n times, and the array is already ordered, or even the array is already ordered. At this point, we want to: when we find a bubble, the array is ordered, stop the next bubble, and return the current array.

At this point we can declare an exchangeFlag variable before each bubble and set it to false. Set exchangeFlag to true if data is exchanged during the bubbling process. After a bubble, we know whether data was exchanged through an exchangeFlag. If there is no exchange, the array is ordered and you can simply return the array. Otherwise, it’s not sorted, so let’s go to the next bubble.

Code implementation

Const bubbleSort = (a) => {// find the largest (small) number to put in the last position on each iteration. // Optimize: if no data is exchanged during a bubble operation, it is already ordered. // Double loop.if (a.length <= 1) returna; // I < len = I < len - 1 = I < len - 1for (let i = 0, len = a.length; i < len; i++) {
        let exchangeFlag = false; // Whether a change has occurredfor (let j = 0; j < len - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                [a[j], a[j + 1]] = [a[j + 1], a[j]];
                exchangeFlag = true;
            }
            
        }
        console.log(a)
        if (exchangeFlag == false) returna; }} // TestletArray = [199, 3, 1, 2, 8, 21,4, 100, 8]; console.log (bubbleSort(array));Copy the code

Analysis of the

1. The time complexity of bubble sort isO(n^2).

The best time is O(n), that is, after the first n-1 comparison, the original array is ordered, and the bubble is over.

The worst time complexity is O(n^2), when the original array happens to be in reverse order, that is, it needs to bubble n times, (n-1) + (n-2)… After + 1 comparison, the worst time complexity can be obtained by summing and simplifying by the geometric sequence summation formula.

The average time complexity is hard to analyze, it’s O(n^2).

2. Bubble sort is a stable sorting algorithm.

By “stable,” I mean that after sorting, the order of data with equal values remains the same.

If adjacent data are equal, do not switch positions.

3. Bubble sort is an in-place sort algorithm

Sorting in place refers to sorting algorithms whose space complexity is O(1).

Bubble sort only exchanges adjacent data, and there are two temporary variables (temporary variables during the exchange and flag). It only needs constant level temporary space, and the space complexity is O(1).

Insertion Sort

Insertion sort. The essence is to take the data from the unsorted area, put it into the sorted area, the data extracted will be compared with the data in the sorted interval one by one, find the correct position to insert.

We divide the array directly into sorted and unsorted regions. To start, the sorted area has only one element, the first element of the array. There are two ways to insert: look for inserts from front to back and look for inserts from back to front. So I’m going to go back and look for inserts.

Code implementation

const insertionSort = a => {
    for (let i = 0, len = a.length; i < len; i++) {
        letcurr = a[i]; // Stores the current value, and its corresponding index may be overwritten when sortingfor (letj = i - 1; j >= 0; j--) {if (curr < a[j]) {
                a[j + 1] = a[j];
            } else {
                break; } a[j] = curr;} a[j] = curr; }}return a;
}
Copy the code

Analysis of the

1. The time complexity of insertion sort is:O(n^2)

When the data to be sorted is sorted, we only need to compare n-1 times each time we insert the sorted region (note that we are traversing the sorted region backwards). So the best time is order n.

The worst time complexity is O(n^2), which is when the data happens to be in reverse order, and you have to go through all the data in the sorted region each time.

2. Insertion sort is stable sort

When traversing sorted areas, if the values are the same, just put them in the last position.

3. Insertion sort is an in-place sort algorithm

You don’t need extra space, you’re exchanging data on an array, so insertion sort is sort in place.

Selection Sort

Selection sort also has a sorted region and an unsorted region. It differs from insertion sort in that selection sort takes the smallest value from the unsorted range and places it at the end of the sorted range.

To reduce memory consumption, we also exchange data directly on the array.

Why insertion sort is better than bubble sort

Insertion sort and bubble sort both take O(n^2) time and exchange the same number of elements, but insertion sort is better. The reason is that the bubble sort swap requires an intermediate TMP variable to swap two elements, which becomes three assignments. Insertion sort, which traverses the sorted area from back to front, does not require an intermediate traversal. It is a direct override of some elements by a backward assignment operation.

Data exchange operations in bubble sort:if(a[j] > a[j+1]) {int TMP = a[j]; a[j] = a[j+1]; a[j+1] = tmp; flag =true; } Insert sort to move data:if(a[j] > value) { a[j+1] = a[j]; // Data movement}else {
  break;
}
Copy the code

In addition, insertion sort can be optimized to become hill sort. I’m not going to go into specifics here.

Code implementation

const selectionSort = a => {
    let tmp;
    for (let i = 0, len = a.length; i < len; i++) {

        letMin = a[I], // Save the minimum value for size comparison. minIndex = i; // Store the index of the lowest value in an unsorted interval (for easy element exchange)for (let j = i; j < len; j++) {
            if (a[j] < min) {
                minIndex = j;
                min =a[j]
            }
        }
        tmp = a[minIndex];
        a[minIndex] = a[i];
        a[i] = tmp;
    }
    return a;
}
Copy the code

Analysis of the

1. The time complexity of selection sort is O(n^2).

The best time is O(n^2). Because every time I find the minimum value in the unsorted region, I have to go through all the elements in the unsorted region n minus 1 times, so the time complexity is O(n^2).

The worst time complexity is also O(n^2) for the same reason.

2. Select sort is a place sort algorithm

We find the smallest element in the unsorted region, swap that element with the element next in the sorted region (that is, the first element in the sorted region), and then I moves backwards. Only elements are exchanged and only constant memory space is used (a temporary traversal is required to exchange two pieces of data), so select sort is an in-place sort algorithm.

3. Selection sort is an unstable sorting algorithm

Unstable, because every time you have to find the minimum value and swap with the previous element, you destroy the stability. So let’s take a counterexample: 3, 3, 2, after the first switch, it’s 2, 3, 3, and the order of the 3’s relative to the 3’s is changed.

Of course, you can also create an empty array of the size of the array to be used as the sorted area. So you don’t have to swap elements, so it’s sort stable, but it takes extra memory to do that, so it becomes a non-place sort algorithm.

Merge sort

Merge sort uses the idea of divide and conquer. The core of the idea of divide and conquer is to decompose a large problem into several smaller problems, which can be solved and merged into the original problem. Divide-and-conquer is usually implemented recursively. The difference between divide and conquer and recursion is that divide and conquer is a processing idea for solving a problem, and recursion is a programming technique.

Merge sort, it splits the array down the middle into left and right parts. Then continue to divide each of the two parts down the middle until no more can be divided. The two parts are then sorted and merged (the merged array is ordered), and then sorted and merged again and again, and finally merged into an ordered array.

Explain the merge function. It combines two ordered arrays into one ordered array by creating an empty array the size of the larger of the two ordered arrays. Set the pointer I and j to the first element of the two arrays, take the smaller one and add it to the array, and move the pointer to the corresponding array backward. Repeating this process until one array is empty pushes the remaining elements from the other array into the new array.

In addition, the merge() function can be optimized with sentry. I haven’t studied the details, but I will consider implementation when I have time.

Code implementation

The code implementation of merging uses recursion, so the code is not very readable.

const mergeSort = a => {
    mergeSortC(a, 0, a.length - 1)
    return a;
}

const mergeSortC = (a, p, r) => {
    if (p >= r) return
    letq = Math.floor( (p + r) / 2 ); Length >= left. Length mergeSortC(a, p, q); mergeSortC(a, q+1, r); Merge (a, p, q, r) // p->q (q+1) ->r; } /** * merge (merge two ordered arrays into one) */function merge(a, p, q, r) {
    leti = p, j = q+1, m = new Array(r - q); // Save the array of merged datalet k = 0;
    while (i <= q && j <= r) {
        if (a[i] <= a[j]) {
            m[k] = a[i];
            i++;
        } else{ m[k] = a[j] j++; } k++; } // First find the remaining elements of the two arrays. // Then put the remaining elements into the array m.let start = i,
        end = q;
    if (j <= r) {
        start = j;
        end = r;
    }

    while(start <= end) { m[k] = a[start]; start++; k++; } // copy m data to a.for(leti = p; i <= r; i++) { a[i] = m[i-p]; }}Copy the code

Performance analysis

1. Merge sort takes order nlogn time.

Here’s a simple derivation from the column, “The Beauty of Data Structures and Algorithms.”

Problem A is decomposed into subproblems B and C. Let the time for solving a, B and C be T(a), T(b), Y(c), then

T(a) = T(b) + T(c) + K
Copy the code

And the time to merge two ordered subarrays is order n, so we have

T (1) = C; When n=1, only the execution time of constant level is required, so it is expressed as C. T(n) = 2 times T(n/2) + n; n>1Copy the code

This simplifies to T(n)=Cn+nlog base 2n. So merge sort takes order nlogn time.

Merge sort is a stable sort

The merge swap happens during the merge, so if you compare the left and right subarrays and you find that they’re equal, you take the left element, and you’re in order.

Merge sortnotIn situ sorting

Merge sort is great, but it’s O(n) in space. Because to merge, you need to request a temporary array, which is not larger than n in length. If you have a lot of data, merge sort because it’s O(n), it’s very memory intensive. So when it comes to sorting big data, we prefer quicksort to merge sort. Although the latter is unstable, it is an in-place sorting algorithm.

Quick sort

Quicksort, or quicksort for short. Quicktypesetting uses the partitioning idea.

The quicksort takes an element of the array as its pivot point and divides the array into three parts:

  1. Less than pivot
  2. pivot
  3. That’s greater than or equal to pivot.

We take the left and right subarrays, and we do the same thing as we did before, until the interval shrinks to zero, at which point the array becomes ordered.

In merge sort, we use a merge() function, and in quicksort, we have a partition() method. The function of this method is to randomly select a pivot based on the range provided, exchange the data in the array between the pivot, and finally place the data smaller than the pivot on the left, and the data larger than the pivot on the right, and then return the index of the pivot as the reference point for the next recursion.

The partition() partition function has a clever way of implementing it in place. It works a little bit like selection sort. So first we pick a pivot, and everything after pivot moves one unit forward, and then pivot goes to the end. Then we’re going to go left to right, and if the element is smaller than pivot, we’re going to put it in the processed region, and we’re going to do something like insert, and we’re going to swap it directly; If not, do not do the operation, continue to the next element, until the end. Finally, place the pivot in the “processed interval” as well. So that’s sorting in place.

In addition, the algorithm of “finding the KTH largest element in an unordered array” can be realized by modifying the partition appropriately.

Code implementation

const quickSort = a => {
    quickSortC(a, 0, a.length - 1)
    returna; } /** * recursion function * parameter meaning is the same as partition method. * /function quickSortC(a, q, r) {
    if(q >= r) {// End the iteration when the supplied array length is 1.return a;
    }
    letp = partition(a, q, r); quickSortC(a, q, p - 1); quickSortC(a, p + 1, r); } /** * select a random element as pivot, partition in place, Return its subindex * * @param {Array} a @param {number} p start index * @param {number} r End index * @returnThe index value of the benchmark for subsequent recursion. * /export functionPartition (a, p, r) {// Pivot takes the last partition by default.letpivot = a[r], tmp, i = p; // The trailing index of the sorted interval. // Similar to selection sort, put the elements less than pivot into the processed intervalfor (; p < r; p++) {
        if(a[p] < pivot) {// Put a[I] in the interval. tmp = a[p]; a[p] = a[i]; a[i] = tmp; [x, y] = [y, x] i++; } // Insert pivot (a[r]) into the processed interval TMP = a[I]; a[i] = a[r]; a[r] = tmp;return i;   
}
Copy the code

Both quicksort and merge sort use the idea of divide and conquer, and the recursive formula is very similar to the recursive code. The difference is that merge sort is bottom-up, and the sorting process occurs during the subarray merge process. Quicksort is top-down, and when you partition, the array tends to be ordered, until you get to a range of 1, and it becomes ordered.

Performance analysis

1. Quicksort time is O(nlogn)

The time complexity recursion for quicksort is the same as for merge. So, the time complexity of quicksort is also order nlogn. But this formula only works if the interval is equally divided every time (i.e., the best time).

Of course, the average complexity is also O(nlongn), but it’s not easy to derive, so I won’t analyze it.

In extreme cases, when the array is already in order and the last element is taken as pivot, the partition is extremely unequal, and it takes about n partitioning operations to complete the quicksort. On average, about N /2 elements are scanned per partition. So, the worst time for quicksort is order n^2.

2. Quicksort is an unstable sort

The partitioning process of quicksort involves an exchange operation, which is an unstable sort like a selection sort.

3. Quicksort is in place

In order to implement in-place sorting, we previously did a clever job with the parition partition function.

At the end

That’s about it. That’s a simple summary. If there is a mistake in the article, please leave me a message.

reference

The beauty of data structures and algorithms