Javascript sort algorithm implementation

Bubble sort

  • The idea behind bubble sort is to compare the ith element with the corresponding element on I +1 and swap them if the first arr[I] is greater than arr[I +1]
  • Bubble sort uses a two-layer loop. The first loop defines the range of the comparison. After each round of comparison, the last element must be the maximum in the ARR, so the next round can be done without considering the NTH bit, and the range of the comparison becomes 0 to n-1, and the third round will be 0 to n-2. By analogy, the zeroth digit after n comparisons is only the smallest in arR, and the second loop is used for comparison sorting
  • In terms of algorithm time, bubble sort is order n^2.

To achieve:

Function swap(arr, I, j) {let temp = arr[I]; arr[i] = arr[j]; arr[j] = temp; } function bubbleSort(arr){ if(arr === null || arr.length < 2) return; for(let end = arr.length - 1; end > 0; end--){ for(let i = 0; i < end; i++){ if(arr[i] > arr[i+1]) { swap(arr, i, i+1) } } } }Copy the code

Selection sort

  • The idea behind selective sorting is to find a minimum value at the current position each time, for example, at 0Find a minimum value in the n-1 range and put it at position 0, and then at 1Find a minimum value in the n-1 range and put it at 1, at 2Find the smallest value in the range n minus 1 and put it at position 2, which is 0The values at position 2 are already sorted
  • The first layer is also to control the range of sorting, because we have sorted the part is not considered, the second layer is responsible for finding the minimum index subscript, in the process of selecting sorting we need to define a variable to mark the position of the lowest value.
  • The algorithm for selection sort is order n^2.

! Selection sort and bubble sort algorithm time complexity is O (n ^ 2), but the selection is a kind of unstable sorting algorithms, such as 6 9 0 8, given a sequence in the first trip to compare, we will find a with the first 6 0, in the comparison of the process, the first 6 and the second was disrupted in the original sequence, The best and worst algorithms for selecting sort are both O(n^2).

To achieve ~

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function selectSort(arr) {
  if(arr === null || arr.length < 2) return;
  for(let i = 0; i < arr.length - 1; i++){
    let minIndex = i;
    for(let j = 0; j < arr.length; j++) {
    	minIndex = arr[j] < arr[minIndex] ? j : minIndex;
    }
    swap(arr, i, minIndex)
  }
}
Copy the code

Insertion sort

  • Compare the number in the I +1 bit with the number in the I bit, and swap if arr[I +1] is less than the number in the I bit
  • Similarly, insert sort has a two-layer loop, with the outer loop controlling the sort range and the inner loop responsible for the comparison swap
  • The average time complexity of the insertion sort algorithm is O(n^2), and the worst time complexity is the comparison of 1 + 2 + 3 +… Summation N^2/2, N^2, N^2, the best time. Is the given array is ordered, each row inserts an element, only need to examine the previous element, in this case the time complexity is O(n)

! Although the complexity of insertion sort, selection sort and bubble sort algorithm is O(n^2), but the insertion sort is related to the data state, in the case of ordered data, the algorithm time complexity is low. But bubble sort has nothing to do with the state of the data,

To achieve

function swap(arr, i, j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function insertSort(arr){ if(arr === null || arr.length < 2) return; for(let i = 1; i < arr.length; i++){ for(let j = i - 1; j > 0 && arr[j] > arr[j+1]; j--) { swap(arr, j, j+1); }}}Copy the code

Merge sort

The idea of merging sort algorithm is as follows:

  • The middle position index of the given target array ARR is found, and the data sample is divided into two parts for sorting. The middle position index is denoted as mid
  • Sort the split array separately, making sure that the left and right arrays are sorted, so that the array can be sorted using an outer row
  • To simulate the C language ‘pointer’ to the left and right side of the array,
  • Prepare an auxiliary array to hold the results of the left and right arrays
  • Judge the boundary conditions in the process of sending out the left and right arrays. One array completes a round of comparison first and copies the data of the other array to the auxiliary array
  • Finally, copy the data from the auxiliary array into the target array ARR, and merge sort will be done

If you find it hard to understand, here’s an example:

Let arr = [5,3,7,4,9,1]; Let arrLeft = [3,5,7] let arrRight = [1,4,9] // prepare an auxiliary array, Arr. Length let helpArr = new Array(6); // Set p1 to the starting position of the left array, p2 to the starting position of the right array, and then compare the values of the elements corresponding to p1 and p2. * At first p1 points to 3 and p2 points to 1, arr[p1] > arr[p2] stores arr[p2] in auxiliary array [1]; Arr [p1] < arr[p2] and arr[p1] < arr[p2]. The auxiliary array is [1,3]. Arr [p1] > arr[p2], store arr[p2] in auxiliary array [1, 3, 4]; Arr [p1] < arr[p2]; arr[p1] < arr[p2]; Copy the left array (1,3,4,5,7) into helpArrCopy the code

~ now use the code complete realization of merge sort, and then merge sort complexity analysis

function mergeSort(arr) { if(arr === nnull || arr.length < 2) return; mergeProcess(arr, 0, arr.length-1); } /** * @param {*number} R */ function mergeProcess(arr, L) R) {L = R if(L === R) return; // let mid = (L + R) / 2; MergeProcess (arr, L, mid); MergeProcess (arr, mid + 1, R); Merge (arr, L, mid, R); } function merge(arr, L, mid, R) {let helpArr = new Array(r-l + 1); let i = 0; // let p1 = L; // let p2 = mid + 1; while(p1 <= mid && p2 <= R) { helpArr[i++] = arr[p1++] < arr[p2++] ? arr[p1++] : arr[p2++]; While (p1 <= mid) {// helpArr[i++] = arr[p1++]; } while(p2 <= R) {helpArr[i++] = arr[p2++]} j < helpArr.length; j++) { arr[L+j] = helpArr[j] } }Copy the code
Complexity analysis of merge sort algorithm
  1. Merge sort divides the total data sample size N into two parts, N/2 on the left side and N/2 on the right side, plus the complexity O(N) of copying the auxiliary array to the original array. The total algorithm complexity is T(N) = 2T(N/2) + O(N).
  2. Merge sort algorithm uses recursive short hair, so we try to use the algorithm complexity analysis method of recursive algorithm to analyze, because the division of the two sub-processes is consistent, so we can use the master formula to analyze T(N) = aT(b*(N/2)) + O(N^d); Recursive algorithm a=2, b = 1, d = 1, log(b, a) = d, so merge sort complexity is T(N) = N logN;

! The time complexity of merge sort, O(N*lonN), is O(N^2)