1. Introduction

The algorithm is king.

Want to learn the front end, first practice good internal skills, only deep internal skills, the front road will go further.

The author wrote the beauty of JavaScript data structure and algorithm series with the language is JavaScript, aimed at the introduction of data structure and algorithm and convenient later review.

Bubble sort, selection sort, and insertion sort are compared together because they all have an average time complexity of O(n2).

Take the question with you: Why is insert sort more popular than bubble sort? Read on.

2. How to analyze a sorting algorithm

Complexity analysis is the essence of the whole algorithm learning.

  • Time complexity: The amount of time an algorithm takes to execute.
  • Space complexity: The amount of memory required to run a program.

For a detailed explanation of time and space complexity, see the beauty of JavaScript data structures and algorithms – Time and Space complexity.

Learning sorting algorithm, we in addition to learning its algorithm principle, code implementation, more important is to learn how to evaluate, analyze a sorting algorithm.

To analyze a sorting algorithm, we should start from three aspects: execution efficiency, memory consumption and stability.

2.1 Execution Efficiency

1. Best case, worst case, average case time complexity

When we analyze the time complexity of sorting algorithm, we should give the time complexity of best case, worst case and average case respectively. In addition, you need to say what the best and worst time complexity is for the raw data to be sorted.

2. Coefficient, constant and low order of time complexity

As we know, time complexity reflects an increasing trend when the data size n is large, so it ignores coefficients, constants and low orders.

However, in actual software development, we may sort 10, 100, 1000 such small scale data, so, when comparing the performance of the sorting algorithm of the same time complexity, we need to take coefficients, constants, and low order into consideration.

3. Number of comparisons and number of swaps (or moves)

This video and the next video are all about sorting algorithms based on comparison. The execution process of comparison based sorting algorithm involves two operations, one is the comparison of the size of elements, and the other is the exchange or movement of elements.

Therefore, if we analyze the efficiency of sorting algorithms, we should also take into account the number of comparisons and swaps (or moves).

2.2 Memory Consumption

So you look at space complexity.

You also need to know the following terms:

  • Internal sort: All sort operations are done in memory;
  • External sort: Because the data is too large, the data is placed on disk, and the sort can only be carried out by disk and memory data transfer;
  • In situ sorting: in situ sorting algorithm, is specifically refers to the space complexity is O(1) sorting algorithm. Among them, bubble sort is in place sort algorithm.

2.3 stability

  • Stable: If there are values in the sequence to be sortedequalThe original order of equal elements after sortingThe same. For example, a was before B, but a = B, after sorting, A is still before B;
  • Unstable: If there are values in the sequence to be sortedequalThe original order of equal elements after sortingchange. For example, a was originally in front of B, and a = B, after sorting, A comes after B;

3. Bubble sort

thought

  • Bubble sort only operates on two adjacent pieces of data.
  • Each bubbling operation compares two adjacent elements to see if they meet the size relationship requirements. If you don’t, switch them.
  • One bubble moves at least one element to its proper position, n times, and n numbers are sorted.

The characteristics of

  • Advantages: sorting algorithm based, simple and practical easy to understand.
  • Disadvantages: more times of comparison, lower efficiency.

implementation

Const bubbleSort = arr => {console.time() const bubbleSort = arr => {console.time()'Improved bubble sort time before');
	const length = arr.length;
	if (length <= 1) return; // I < length-1 because the outer layer only needs length-1, the first length comparison is redundant.for (leti = 0; i < length - 1; I ++) {// j < length-i-1 because the inner layer of length-i-1 to length-1 is arranged, do not need to compare again.for (let j = 0; j < length - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				const temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	console.log('Pre-improved ARR :', arr);
	console.timeEnd('Improved bubble sort time before');
};
Copy the code

Optimization: When no data is exchanged during a bubbling operation, it indicates that the bubbling operation is in complete order and no further bubbling operation is required.

Const bubbleSort2 = arr => {console.time()'Improved bubble sort time');
	const length = arr.length;
	if (length <= 1) return; // I < length-1 because the outer layer only needs length-1, the first length comparison is redundant.for (let i = 0; i < length - 1; i++) {
		let hasChange = false; // j < length-i-1 because the position of the inner layer from length-i-1 to length-1 is already lined up, so there is no need to compare again.for (let j = 0; j < length - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				const temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				hasChange = true; // Indicates data exchange}}if(! hasChange)break; / / iffalseAll elements are in place and no data is exchanged. Exit} console.log('Improved ARR :', arr);
	console.timeEnd('Improved bubble sort time');
};
Copy the code

test

// Test const arr = [7, 8, 4, 5, 6, 3, 2, 1]; bubbleSort(arr); Const arr2 = [7, 8, 4, 5, 6, 3, 2, 1]; bubbleSort2(arr2); // Improved ARR: [1, 2, 3, 4, 5, 6, 7, 8] // Improved bubbling sort time: 0.318115234375msCopy the code

Analysis of the

  • First, is bubble sort an in-place sort algorithm? The bubbling process only involves the exchange operation of adjacent data and only requires constant level temporary space, so its space complexity is O(1), which is aIn situSorting algorithm.
  • Second, is bubble sort a stable sorting algorithm? In bubble sort, only swapping can change the order of two elements. In order to ensure the stability of bubble sorting algorithm, when two adjacent elements have the same size, we do not exchange, and the data of the same size will not change the order before and after sorting. So bubble sort isstableSorting algorithm.
  • Third, what is the time complexity of bubble sort? Best case: T(n) = O(n), when data is already in positive order. Worst case: T(n) = O(n2), when the data is in reverse order. Average case: T(n) = O(n2).

animation

4. Insert sort

Insertion sort is divided into direct insertion sort and optimized split insertion sort and Hill sort, we usually say that the insertion sort refers to direct insertion sort.

First, direct insertion

thought

General people playing poker, sorting cards, are according to the size of the card (from small to large or from large to small) sorting cards, that every touch a new card, scan their cards, the new card inserted into the corresponding position.

How insert sort works: By building an ordered sequence, unsorted data is scanned from back to front in the sorted sequence to find the appropriate location and insert.

steps

  • Starting with the first element, the element can be considered sorted;
  • Fetch the next element and scan back to front in the sorted element sequence;
  • If the element (sorted) is larger than the new element, move the element to the next position;
  • Repeat step 3 until you find a place where the sorted element is less than or equal to the new element;
  • After inserting a new element into that position;
  • Repeat steps 2 to 5.

implementation

// insert sort const insertionSort = array => {const len = array.length;if (len <= 1) return

	let preIndex, current;
	for (leti = 1; i < len; i++) { preIndex = i - 1; // Current = array[I]; // Current elementwhile(preIndex >= 0 && array[preIndex] > current) {// One of the preconditions is that the element to be compared is larger than the current element. // Move the element to be compared by one preIndex--; // Move cursor forward one bit}if(preIndex + 1 ! Array [preIndex + 1] = array[preIndex + 1] = current; // Insert the current element into the reserved space console.log('array :', array); }}return array;
};
Copy the code

test

// Test const array = [5, 4, 3, 2, 1]; console.log("Original array :", array); insertionSort(array); / / the original array: [5, 4, 3, 2, 1] / / array: [4, 5, 3, 2, 1] / / array: [3, 4, 5, 2, 1] / / array: [2, 3, 4, 5, 1] / / array: [1, 2, 3, 4, 5]Copy the code

Analysis of the

  • First, is insertion sort an in-place sort algorithm? Insert sort doesn’t require extra storage to run, so the space complexity is O(1), so this is aIn situSorting algorithm.
  • Second, is insertion sort a stable sorting algorithm? In insert sort, for elements that have the same value, we can choose to insert the elements that appear later after the elements that appear earlier, so we can keep the original order, so insert sort isstableSorting algorithm.
  • Third, what is the time complexity of insert sort? Best case: T(n) = O(n), when data is already in positive order. Worst case: T(n) = O(n2), when the data is in reverse order. Average case: T(n) = O(n2).

animation

Two, half insert

Insertion sort also has an optimization algorithm called split insertion.

thought

Split insertion sort is an upgraded version of direct insertion sort. Since the first part of insertion sort is an sorted array, we do not need to find insertion points in order, but simply compare their intermediate values with the size of the element to be inserted.

steps

  • Array [I] is compared with array[m]. If array[I] < array[m], it indicates that the element array[I] to be inserted should be in the range of 0 to M indexes. Otherwise, it should be between the index m to i-1 of the array.
  • Repeat Step 1, narrowing the search by half each time until you find the insertion location.
  • Moves all elements in the array after the insertion position one bit back.
  • Inserts the ith element at the specified position.

Note: x>>1 is the right shift in bitwise operations, indicating a right shift, equivalent to x divided by 2 and rounded, i.e. X >>1 == math.floor (x/2).

Const binaryInsertionSort = array => {const len = array.length;if (len <= 1) return;

	let current, i, j, low, high, m;
	for (i = 1; i < len; i++) {
		low = 0;
		high = i - 1;
		current = array[i];

		while(low <= high) {// step 1: m = (low + high) >> 1; // Note: x>>1 == math.floor (x/2).if(array[I] >= array[m]) {// If (array[I] >= array[m]) { // Insert point in high half}else{ high = m - 1; // Insert point in lower half}}for(j = i; j > low; Array [j] = array[j-1]; array[j] = array[j-1]; console.log('array2 :', JSON.parse(JSON.stringify(array))); } array[low] = current; // Step 4: Insert the element} console.log('array2 :', JSON.parse(JSON.stringify(array)));
	return array;
};
Copy the code

test

const array2 = [5, 4, 3, 2, 1];
console.log('original array2:', array2); binaryInsertionSort(array2); / / original array2: [5, 4, 3, 2, 1] / / array2: [5, 5, 3, 2, 1] / / array2: [4, 5, 5, 2, 1] / / array2: [4, 4, 5, 2, 1] // array2 : [3, 4, 5, 5, 1] // array2 : [3, 4, 4, 5, 1] // array2 : [3, 3, 4, 5, 1] // array2 : [2, 3, 4, 5, 5] // array2 : [2, 3, 4, 4, 5] // array2 : [2, 3, 3, 4, 5] // array2 : [2, 2, 3, 4, 5] // array2 : [1, 2, 3, 4, 5]Copy the code

Note: Like direct insert sort, half-insert sort swaps adjacent elements with different values each time, and does not change the order between elements with the same value, so it is stable.

Hill sort

Hill sort is an algorithm with O(nlogn) average time complexity, which will be discussed in the next chapter along with merge sort, quicksort and heapsort, but not in this article.

5. Select sort

Train of thought

The implementation of selection sort algorithm is similar to insertion sort, which is divided into sorted and unsorted intervals. But select sort will find the smallest element in the unsorted range each time and place it at the end of the sorted range.

steps

  1. First find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence.
  2. Find the smallest (largest) element from the remaining unsorted elements and place it at the end of the sorted sequence.
  3. Repeat the second step until all elements are sorted.

implementation

const selectionSort = array => {
	const len = array.length;
	let minIndex, temp;
	for (let i = 0; i < len - 1; i++) {
		minIndex = i;
		for (let j = i + 1; j < len; j++) {
			if(array[j] < array[minIndex]) {// Find minIndex = j; }} temp = array[I]; array[i] = array[minIndex]; array[minIndex] = temp; console.log('array: ', array);
	}
	return array;
};
Copy the code

test

// Test const array = [5, 4, 3, 2, 1]; console.log('original array:, array); selectionSort(array); / / the original array: [5, 4, 3, 2, 1] / / array: [1, 4, 3, 2, 5] / / array: [1, 2, 3, 4, 5] / / array: [1, 2, 3, 4, 5] / / array: [1, 2, 3, 4, 5]Copy the code

Analysis of the

  • First, is selection sort an in situ sort algorithm? The selection sort space complexity is O(1), which is aIn situSorting algorithm.
  • Second, is selection sort a stable sorting algorithm? Selection sort destroys stability by finding the minimum of the remaining unsorted elements and swapping places with the previous element. So, selection sort is oneunstableSorting algorithm.
  • Third, what is the time complexity of selection sort? The selection sort is traversed n2 over 2 times to sort whether it is forward or reverse, so the complexity of best, worst, and average is the same. Best case: T(n) = O(n2). Worst-case: T(n) = O(n2). Average case: T(n) = O(n2).

animation

6. Answer the opening paragraph

Why is insertion sort more popular than bubble sort?

Bubble sort and insert sort both have O(n2) time complexity and are in place sorting algorithms. Why is insert sort more popular than bubble sort?

It’s about degree of reverse order, degree of full order, degree of order.

  • Degree of order: Is the number of pairs of elements in an array that have an ordered relationship. Pairs of ordered elements are expressed mathematically like this:
Pairs of ordered elements: A [I] <= a[j], if I < j.Copy the code

  • Full order: The degree of order of a fully ordered array is called full order.

  • Reverse order: exactly the opposite of order (default from small to large order).

Reverse element pairs: A [I] > a[j], if I < j.Copy the code

Similarly, for an array in reverse order, such as 6,5,4,3,2,1, the order is 0; For a perfectly ordered array, like 1, 2, 3, 4, 5, 6, the order is n times n minus 1 over 2, which is full order 15.

why

  • No matter how optimized bubble sort is, the number of elements swapped is a fixed value, which is the degree of reverse order of the original data.
  • Insert sort is the same, no matter how optimized it is, the number of element moves is equal to the degree of reverse order of the original data.
  • However, the data exchange of bubble sort is more complicated than the data movement of insert sort. Bubble sort requires three assignments, while insert sort requires only one. Once the data volume is large, the difference becomes obvious.

7. Complexity comparison of sorting algorithms

Complexity contrast

The name of the The best On average, The worst memory The stability of note
The bubbling n n2 n2 1 Yes .
insert n n2 n2 1 Yes .
choose n2 n2 n2 1 No .

Algorithm visualization tool

An algorithm visualization tool is recommended.

Algorithm-visualizer is an interactive online platform that allows you to visualize algorithms in your code and see the process of code execution.

The effect is shown below.

8. Article output plan

The beauty of JavaScript data structures and algorithms series of articles, adhere to about 3-7 days to update a tentative plan as shown in the following table.

The title link
Time and space complexity Github.com/biaochenxuy…
Linear tables (arrays, linked lists, stacks, queues) Github.com/biaochenxuy…
Implementing a front-end route, how to implement browser forward and backward? Github.com/biaochenxuy…
Stack and heap memory, shallow copy and deep copy Github.com/biaochenxuy…
recursive Github.com/biaochenxuy…
Nonlinear tables (tree, heap) Github.com/biaochenxuy…
Bubble sort, select sort, insert sort Github.com/biaochenxuy…
Merge sort, quicksort, Hill sort, heap sort Wonderful to be continued
Count sort, bucket sort, radix sort Wonderful to be continued
Top 10 classic rankings Wonderful to be continued
Highly recommended GitHub data structures and algorithms project worth front-end learning Github.com/biaochenxuy…

If there is any mistake or not precise place, please be sure to give correction, thank you very much.

9. The last

Give it a thumbs up if you like.

All the code and test cases in this article have been posted on my GitHub.

Reference article:

  • The beauty of data structures and algorithms
  • Top 10 Classic Sorting Algorithms
  • JS can be used to get all sorts of algorithms