This is the 7th day of my participation in the August More Text Challenge

preface

Own algorithm has a little weak, decided to tear algorithm.

Hope I can stick to it!!

Binary search

define

When you are young, you should play A guessing game: Child A thinks of A number between 1 and 100 in his mind, and child B needs to guess the word in his mind. During the guessing process, child A will prompt child B to guess whether the number is big or small.

So in the process of guessing how can the fastest guess? With this problem in mind, the definition of binary lookup is created:

If you need to find a target value in an ordered array, you can check whether the middle value is the target value each time and return it if it is. If not, the value is combined with the beginning or end of the array to form a new range, and the intermediate value is evaluated again in this new range. Keep repeating until the operation is found or not found.

scenario

In an ordered array, find if a target value exists in the array and return its index if it does, or -1 if it does

process

  1. According to the definition of dichotomy, we need to define a start index and an end index to represent the dynamic interval
  2. Take the middle value of the interval if the middle value is equal to the target valuereturnIndex and end the loop
  3. If the median value is greater than the target value, the target value is between the median value and the first value
  4. If the median value is less than the target value, the target value is between the median value and the last value
  5. After the judgment of 4 or 5, a new interval can be formed, and then repeat 2-4 in this new interval

The illustration

Code implementation

 function binarySearch(list, target) {
   let startIndex = 0
   let endIndex = list.length - 1
   while(startIndex <= endIndex) {
     let middleIndex = Math.floor((startIndex + endIndex) / 2)
     let middleValue = list[middleIndex]
     if (middleValue === target) {
       return middleIndex
     } else if (middleValue > target) {
       endIndex = middleIndex - 1
     } else if (middleValue < target) {
       startIndex = middleIndex + 1
     }
   }
   return -1
 }
Copy the code

The problem

  • MiddleValue > target and middleValue < target

    Because the current median value is already compared and does not equal the target value, it needs to be added and subtracted to point to the new value

  • Can a while loop condition be startIndex < endIndex?

    No, because startIndex is going to equal endIndex.

  • StartIndex + endIndex / 2 why do I round down?

    If you don’t round it then if you divide by 2 you get a decimal;

    If you want to round up, an index greater than the length of the array will appear, at which point the value will not be fetched.

The keyword

Set the dynamic interval, traverse the dynamic interval, take the middle value of the interval and judge the target.

Bubble sort

process

  1. Compare two adjacent elements in an array, starting with the first element
  2. If the front one is larger than the back one, they switch places, and vice versa
  3. Keep repeating 2 until you get to the end of the array
  4. The last one in the array is definitely going to be the largest one in the array when you compare it
  5. Start the next loop, repeating 1-5 until all elements of the array are compared
  6. 5 After the execution is complete, only the position of the last value can be determined. Other values need to be compared again. Therefore, a loop needs to be set in the outer layer to control the number of cycles

The illustration

Code implementation

 function bubbleSort(list) {
   for (let i = 0; i < list.length - 1; i++) {
     for (let k = 0; k < list.length - 1 - i; k++) {
       if (list[k] > list[k + 1]) {
         const temp = list[k]
         list[k] = list[k + 1]
         list[k + 1] = temp
       }
     }
   }
   return list
 }
Copy the code

The problem

  • Why I < list.length – 1 in the outer loop condition?

    In the demo, if the condition is I < list.length, it equals I < 8. The last loop before ending the condition is I = 7, and the order of the array is correct at I = 6 when it is iterated over 7. So when I is equal to 7, the loop is like an empty loop, so I don’t loop at all.

  • Why does the inner loop have -i?

    When the first comparison is done, the last one in the array must be the largest, so there is no need to compare the last one next time.

    The first one is the last one that doesn’t need to be compared, the second one is the last two that don’t need to be compared…

    Finally, the number of outer loops is the number of times we have compared, which is the number of times we don’t need to compare behind the array, so we subtract that.

The keyword

Two adjacent elements are compared one by one, and only the position of the last value can be determined at a time.

Selection sort

process

  1. Store the index of the first value, assuming its corresponding value is the minimum
  2. The looping array compares the lowest value to the value after the lowest value
  3. If there is less than the minimum value, the index of the previous minimum value is replaced
  4. After the loop is complete, if the minimum stored during initialization is not equal to the final minimum, the two positions are replaced
  5. 4. After completion, the position of the minimum value can be determined
  6. Repeat 1-5, except this time the index for the second value is stored.

The illustration

Code implementation

function selectSort(list) { for (let i = 0; i < list.length - 1; i++) { let cache = i for (let k = i + 1; k < list.length; k++) { if (list[k] < list[cache]) { cache = k } } if (cache ! == i) { const temp = list[cache] list[cache] = list[i] list[i] = temp } } return list }Copy the code

Pay attention to the point

 if (list[k] < list[cache]) {
   cache = k
 }
Copy the code

The inner loop is not finished after the smaller value is reached in the judgment, but continues to iterate. The inner loop cannot be finished here, because it is possible that the current found value is not the smallest, and the smallest value may be later.

The keyword

Select the first value as the minimum and iterate over the following values to determine the minimum value first.

Insertion sort

process

  1. The cache is assumed to be minimum, starting from the second
  2. Compare from cache to the left
  3. If a value on the left is larger than the cache, continue the comparison to the left
  4. If there is no value left, swap the cache with the value larger than the cache
  5. If there is a value left, continue the comparison until there is no value left, or a value smaller than the cache is encountered. The last value larger than the cache is swapped with the cache
  6. Repeat 1-5, except that the third value is used as the assumed minimum cache in step 1

The illustration

Code implementation

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

I don’t have any value on the left-hand side in the code when k is equal to 0.

The problem

  • Arr [j] = temp can be written as arr[I] = temp?

    Can not be

    1. So the conditions that I’m going to execute here arej=== 0Or the element on the left is not as large as the cached one (arr[index - 1] > temp), one is to insert to the beginning of the array, one is to keep the original position.
    2. becauseiIs the index of the element currently being compared, andjIt’s the index after comparison. It’s possible in the process of comparisonjMoved to the left several times, not when the value in the cache was insertediThe corresponding position

The keyword

Start caching the second value in turn, comparing it each time with the value on the left.

Quick sort

The core is to achieve through recursion, constantly looking for the base value to establish a new partition, constantly looking for the base value in the partition.

process

  1. Optionally find a reference value in the array, if the array has only one element or is emptyreturn
  2. Iterate over all elements in the array other than this reference value
  3. Greater than the reference valuerightArrIs less than the reference valueleftArr 中
  4. willleftArr 和 rightArrPerform steps 1 through 4 respectively
  5. willleftArrExecution result + baseline value +rightArrExecution result

The illustration

Code implementation

 function quickSort(list) {
   if (list.length <= 1) return list
   const pivotIndex = list.length - 1
   const pivot = list.splice(pivotIndex, 1)[0]
   const leftArr = []
   const rightArr = []
   for (let i = 0; i < list.length; i++) {
     const item = list[i];
     if (item > pivot) {
       rightArr.push(item)
     } else if (item < pivot) {
       leftArr.push(item)
     }
   }
   
   return quickSort(leftArr).concat([pivot], quickSort(rightArr))
 }
Copy the code

The keyword

It is implemented recursively, constantly determining base values and partitions.

The source address

learn-algorithm-javascript