preface

When front-end engineers develop regular projects, they rarely write sorting algorithms. Even if you need to sort something, you can easily do it using array.sort() provided by JS, with very little low-level sorting code to write.

However, some business scenarios apply special data structures, such as the need to implement linked list sorting, heap sorting, then use the idea of sorting algorithm. In addition, algorithmic questions in front-end interviews occasionally appear in written tests, requiring candidates to be able to write by hand.

This article sorted out bubble sort, quick sort, insertion sort, selection sort, odd and even sort and binary search in order, these algorithms are not difficult to implement, take some time to understand.

Bubble sort

Bubble sort iterates through the sequence to be sorted, comparing the size of two adjacent elements in turn, and swapping their values if the order is wrong. The average time complexity of bubble sort is O(n ^ 2).

Algorithm principle

There is an array [4,3,2,1] that requires sorting from smallest to largest.

  • The first iteration starts at the first element and will4and3Compare and find4than3Large, the two element values are swapped. An array of values for,4,2,1 [3].
  • The traversal continues,4and2Compare, find4than2Large, the two element values are swapped. An array of values for,2,4,1 [3].
  • In the same way4and1Compare, swapping two element values. An array of values for,2,1,4 [3].
  • The results of the first iteration pick the maximum4Put it at the end of the array. The second round of traversal begins3and2Compare and find3than2Large, the two element values are swapped. An array of values for,3,1,4 [2].
  • The traversal continues,3and1Compare, swapping two element values. An array of values for,1,3,4 [2].
  • The first round has already picked the maximum4I put it at the end, so4You can skip the second round of comparisons. At the end of the second iteration, the sublarge value is selected3I put it in the second to last position.
  • And the same is true for the third round2Put it in the third from the bottom of the array,3and4Does not participate in the third round comparison, and the array value is[1, 2, 3, 4].

The test code

function bubbleSort(list){ function swap(a,b){ let c = list[a]; list[a] = list[b]; list[b] = c; } for(let i = 0; i<list.length; i++){ for(let j = 0; j<list.length - 1 -i; j++){ if(list[j] > list[j+1]){ swap(j,j+1); } } } return list; } the console. The log (the bubbleSort ([1,4,6,3, 1-2,7,5,9,8,22,1,34])); // [-2, -1, 1, 1, 3, 4, 5, 6, 7, 8, 9, 22, 34]Copy the code

Quick sort

Quicksort takes a base number (usually the first element), then iterates through all subsequent elements, placing the smaller ones to the left and the larger ones to the right (or vice versa if you sort by the largest). Then, the left and right parts of the data are sorted recursively according to this method, so as to finally realize the whole data into an ordered sequence.

The average time complexity of quicksort is O(nlogn).

Algorithm principle

There are arrays [3,5,4,1,2] that require sorting from smallest to largest.

  • Take the first element3Start iterating through subsequent elements as a base number.
  • 5than3Big, in the3To the right. Same thing4Also on the3On the right.1In the3On the left.2In the3On the left.
  • After the last round of operations, the data becomes zero[1, 2] 3 [5, 4].Now let two words sequence again[1, 2]and[5, 4]Execute the first two processes separately.[1, 2]Turned out to be1 [2]And the[5, 4]Turned out to be[4] 5.
  • 1 [2]and[4] 5Two subsequences[2]and[4]There’s only one element that can be used as the end condition for recursion.
  • And then finally the integration of the values becomes theta1 [2] 3 [4] 5, achieving the goal of sorting.

The test code

If (data.length <= 1){return data; if(data.length <= 1){return data; } const anchor = data.shift(); const left = []; const right = []; data.forEach((v)=>{ if(v <= anchor){ left.push(v); }else{ right.push(v) } }) return execuate(left).concat([anchor]).concat(execuate(right)); } return execuate(list); } the console. The log (quickSort ([,1,6,100, 2-3,3,12, 9,7,2,8,3,22,4,1,6,8])); // [-2, -1, 1, 1, 3, 4, 5, 6, 7, 8, 9, 22, 34]Copy the code

Binary search

Dichotomy is an efficient query algorithm, not a sorting algorithm. But because it comes up so often in interviews, it’s worth doing a tidbits.

Dichotomy can only be used for queues that are sorted by size. Take the array as an example, first find the middle element of the array, if the element is exactly equal to the target element, the loop search process ends, otherwise perform the next step.

If the target element is greater than or less than the middle element, only the half of the region that is greater than or less than the middle element is searched, and the previous step is repeated. The time complexity of dichotomy is O(log2n).

Algorithm principle

There is an array [3,4,5,10,23,24,30] and find the value 5.

  • The dichotomy first finds the middle element of the array10With the5Compare5Big.
  • So you can infer that10All of the elements on the right-hand side5Big, just need to care10The element on the left.
  • 10The element on the left[three, four, five]Repeat the above steps to extract the median value4With the5Compare5Small.
  • abandon4The ones on the left, you only care about the ones on the right. I’m left with just one element5, can be used as the end condition of the loop. If it’s equal to the target value, it’s found. If it’s not, it’s not there.

The test code

Function halfSelect(list,target){let start = 0; let end = list.length - 1; while(start<=end){ let mid = Math.floor((start + end)/2); If (list[mid] === target){return mid; }else if(list[mid] < target){ start = mid + 1; }else{ end = mid - 1; } } return -1; } the console. The log (halfSelect (,0,1,2,5,6,7,8,10,45,47] [- 1, 2)); / / 3Copy the code

Dichotomy is also very useful in practical applications, such as the array list to obtain the following data structure:

List = [{id: 12, name: "zhang", the age: 18}, {id: 17, name: "zhang", the age: 18}, {id: 23, name: "zhang", the age: 18}, {id: 45, name: "zhang", the age: 18}, {id: 62, the name: "zhang", the age: 18}, {id: 108, the name: "zhang", the age: 18},...Copy the code

Suppose the list contains 10,000 pieces of data, and now we need to find the name and age of id 42576. If traversing 10,000 pieces of data is too violent, what is the maximum number of traversals using dichotomy? (Interview questions)

The time complexity of the dichotomy is O(log2n), which means that if the total length of the array is 4,2 to the second power is 4, you only need to traverse it at most twice. If the total length of data is 10000000, the value of 2 is greater than 10000 only after 14 times. Therefore, you need to traverse the 10000 data for a maximum of 14 times.

The algorithm prepared above is the most basic form, dichotomy and a lot of extended deformation writing method, can practice.

Such as array contains a repeating element, such as halfSelect,4,5,5,5,5,5,5,10,23,24,30 [3], (5). Then the algorithm written above does not calculate the index of 5 to be 2.

Other requirements are to find the index closest to the size of the target value, such as halfSelect([3,4,5,10,23,24,30],6), where the value 5 is closest to 6 and should return the index 5.

Insertion sort

The basic idea of insertion sort is to iterate from front to back, and the records obtained from each iteration are inserted into the ordered list that follows, thus forming a new ordered list.

The time of direct insertion sort is O(n ^ 2).

Algorithm principle

There are arrays [5,1,7,3], sorted from smallest to largest.

  • Take the second element of the array1, and the first element5The comparison,1than5Small, on the5The array value is,5,7,3 [1].
  • At this time1, 5It’s already a sorted subsequence. The loop continues, fetching the third element7, expected insertion1, 5Appropriate position in a subsequence. Due to the7than1, 5The largest element in the subsequence is still larger, and nothing is done. The array value is still zero,5,7,3 [1].
  • The subsequence becomes theta1, 5, 7The loop continues, fetching the fourth element3, expecting to insert at the right place in the subsequence.3In the first place and7The comparison,3than7Small, so insert7The array value is,5,3,7 [1].
  • 3Continue to work with5The comparison,3than5Small,3insert5The array value isHc-positie [1].
  • 3Continue to work with1The comparison,3than1Large, do not do any operations. then3The most suitable insertion position is in1with5In between.

The test code

function insertSort(list){ for(let i = 0; i<list.length-1 ; i++){ let j = i+1; const value = list[j]; While (j > 0 && list] [j - 1 > value) {/ / array and a linked list is different, the effect of the implementation into more trouble. / / before an element value can be assigned to an element, after implementation elements move to the right of a whole, and then to insert the element values of exchange, so as to simulate the insertion of the effect list[j] = list[j-1]; j--; } list[j] = value; } return list; } the console. The log (insertSort ([1,4,6,3, 1-2,7,5,9,8,22,1,34])); // [-2, -1, 1, 1, 3, 4, 5, 6, 7, 8, 9, 22, 34]Copy the code

Selection sort

Selection sort is a simple and intuitive sorting algorithm. The basic idea is to find the smallest element in the unsorted sequence and place it at the beginning of the sorted sequence. Then from the remaining unsorted elements continue to find the next smallest element, placed in the second position in the sorted sequence. Repeat until all elements are sorted, O(n²).

Algorithm principle

There are arrays [5,1,7,3], sorted from smallest to largest.

  • Store the first element of the array, value 5, as the global minimum, iterate through,5 is greater than 1, and the global minimum is updated to 1. So we’re going to continue, so 1 is less than 7, so we don’t do anything. So we’re going to continue, so 1 is less than 3, so we don’t do anything

  • The first iteration determines that the global minimum is 1 and places it at the beginning of the array. The array becomes [1,5,7,3].

  • [5,7,3] repeat the above two steps to determine that the global minimum is 3 and replace it with 5 to change the array value to [1,3,5,7]. Subsequent traversals continue until all sorts are complete.

The test code

/** * selectSort */ function selectSort(list){let min_index; for(let i = 0; i<list.length; i++ ){ min_index = i; For (let j = I +1; j<list.length; j++){ if(list[j] < list[min_index]){ min_index = j; } } swap(i,min_index); Function swap(ii,mmin_index){let c = list[ii]; list[ii] = list[mmin_index]; list[mmin_index] = c; } return list; } the console. The log (selectSort (,6,4,9,3,5,7,22,4,8,3,12 [1])); // [1, 3, 3, 4, 4, 5, 6, 7, 8, 9, 12, 22]Copy the code

Parity sorting

Odd-even sorting is a relatively simple sorting algorithm originally invented for parallel computing of local interconnections. The basic idea is that the odd columns are sorted, then the even columns are sorted, then the odd columns are sorted again, then the even columns are sorted again, and the process is repeated until the entire column is sorted.

The time of odd and even sort is O(n ^ 2).

Algorithm principle

There are arrays [24,10,7,23,3,5,11] sorted from smallest to largest.

  • We do odd sorting first, and the odd numbers that participate in odd sorting are24,7,3Will the.24with10The comparison,10The value is less than27, the two values are swapped.
  • At the same time7and23The comparison,3and5The result of the first odd sort swap array is,24,7,23,3,5,11 [10].
  • In the second round of even sorting, the even numbers involved in even sorting are24,23,5Will the.24with7The comparison,7The value of is small, and the two values are swapped. At the same time23and3The comparison,5and11The result of the second even sort swap array is,7,24,3,23,5,11 [10].
  • The third round repeats the above odd sort operation, and the array result is,10,3,24,5,23,11 [7].
  • The fourth round repeats the above even sort operation and the array result is,3,10,5,24,11,23 [7].
  • The fifth round repeats the above odd sort operation, and the array result is,7,5,10,11,24,23 [3].
  • Round 6 repeats the above even sort operation, and the array result is,5,7,10,11,23,24 [3].

The test code

function oddEvenSort(list){ function swap(a,b){ let c = list[a]; list[a] = list[b]; list[b] = c; } // The outer loop controls the total number of odd and even loops. The worst case is when the maximum value is at the beginning of the queue and the loop goes through list.length-1 to the end of the queue. i < list.length - 1; i++){ let start = (i+1)%2 ! = 0? 1-0. While (start < list.length-1){if(list[start] > list[start +1]){swap(start,start+1); } start+=2; } } return list; } the console. The log (oddEvenSort ([24,10,7,23-3,5,5,3,3,5,11])); // [-3, 3, 3, 5, 5, 5, 7, 10, 11, 23, 24]Copy the code