This is the 8th day of my participation in Gwen Challenge

An overview of the

Bubble sort is the first sorting algorithm that many novice programmers come into contact with. It is also the simplest algorithm among all sorting algorithms, but it is the least efficient one among many sorting algorithms.

Bubble sort compares all two adjacent items and swaps them if the first is larger than the second. Items move up to the correct order, like bubbles rising to the surface, hence the name bubble sort.

Bubble sort full resolution

If you have such an array of unequal values, place the scale at the right end of the array and compare the numbers to the left and right of the scale.

In this case, we will compare 7 and 6.

After comparison, if the number on the right of the two trees is smaller, the positions of the two numbers are switched.

Since 6 is less than 7, these two numbers have to be swapped.

When the comparison is complete, the scale is moved one position forward to the left.

Repeat the comparison of numbers

Because 6 is greater than 4, we don’t have to swap.

When the comparison is complete, the scale is then moved one position further to the left.

The repeated comparison of two numbers and the scale moving forward one position to the left…

Until the balance moves to the left.

Now the leftmost number is sorted

Return the scale to the right and do the same thing, sorting the other arrays (ignoring the sorted numbers)

Each time the same operation is repeated, one number on the left is sorted until all numbers are sorted.

At this point, this array of unequal numbers has been sorted.

Code to achieve bubble sort

To facilitate the comparison or exchange of adjacent numbers in sorting, define some constants and methods for comparison and exchange

// A constant object for comparison (to keep code elegant)
export const Compare = {
  LESS_THAN: -1.// If the first element is less than the second, it returns -1
  BIGGER_THAN: 1.If the first element is greater than the second, it returns 1
  EQUALS: 0 // If the element has the same reference, it returns 0
};
// Compare the methods used
export function defaultCompare(a, b) {
  // If the element has the same reference, it returns 0
  if (a === b) {
    return Compare.EQUALS;
  }
  // If the first element is less than the second, it returns -1, otherwise it returns 1
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
/** * swap function *@param {*} Array passes in the array to swap (in this case the heap) *@param {*} A passes in the node a * to be swapped@param {*} B passes in the node b */ to be swapped
export function swap(array, a, b) {
  // ES5
  /* const temp = array[a]; // To swap two values in an array, we need an auxiliary variable to copy the first element to swap array[a] = array[b]; // Then assign the second element to the position of the first element array[b] = temp; * / // Finally, the copied value of the first element is overwritten to the position of the second element
  / / ES6 writing (poorly) https://bugzilla.mozilla.org/show_bug.cgi?id=1177319
  [array[a], array[b]] = [array[b], array[a]];
}
Copy the code

Implement bubble sort

The basic idea of bubble sort is to compare two adjacent elements each time and swap them if they are in the wrong order. *@param {array} Array Array to be sorted *@param {function} CompareFn // Compare with defaultCompare * by default@returns {array} Returns the sorted array */
export function bubbleSort(array, compareFn = defaultCompare) {
  const { length } = array; // Declare a variable named length to store the length of the array
  for (let i = 0; i < length; i++) { // In the loop, bubble sort can only locate one item at a time, so each item in the array needs to be sorted in one round, the number of rounds is the same as the length of the array
    // console.log('--- ');
    for (let j = 0; j < length - 1; j++) { // Inner loop, compare the current item with the next item, sort n numbers, n-1 times
      // console.log('compare ' + array[j] + ' with ' + array[j + 1]);
      if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) { // If the two terms are out of order (the current term is larger than the next)
        // console.log('swap ' + array[j] + ' with ' + array[j + 1]);
        swap(array, j, j + 1); // Swap them (positions j+1 will be swapped to position j)}}}// Returns the sorted array
  return array;
}
Copy the code

The bubble sorting algorithm mentioned above does not ignore the sorted numbers, leading to more useless comparison judgment on the sorted numbers.

Therefore, the algorithm can be improved to ignore the sorted numbers when comparing:

The basic idea of bubble sort is to compare two adjacent elements each time and swap them if they are in the wrong order. *@param {array} Array Array to be sorted *@param {function} CompareFn // Compare with defaultCompare * by default@returns {array} Returns the sorted array */
export function modifiedBubbleSort(array, compareFn = defaultCompare) {
  const { length } = array; // Declare a variable named length to store the length of the array
  for (let i = 0; i < length; i++) { // In the loop, bubble sort can only locate one item at a time, so each item in the array needs to be sorted in one round, the number of rounds is the same as the length of the array
    // console.log('--- ');
    for (let j = 0; j < length - 1 - i; j++) { / / inner loop, with the current item and the next item, prioritize, n number only for n - 1, again from inner loop minus the outer loop has run through round number I (have ran round number number is right, do not need to compare again)
      // console.log('compare ' + array[j] + ' with ' + array[j + 1]);
      if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) { // If the two terms are out of order (the current term is larger than the next)
        // console.log('swap ' + array[j] + ' with ' + array[j + 1]);
        swap(array, j, j + 1); // Swap them (positions j+1 will be swapped to position j)}}}// Returns the sorted array
  return array;
}
Copy the code