В алгоритме пузырьковой сортировки есть ошибка, из-за которой некоторые нумерованные списки сортируются неправильно в NodeJS

Question

Я новичок, когда дело доходит до алгоритмов, и начинаю снизу с сортировкой пузырьков. Я создал свою реализацию, и она, кажется, работает 9/10 раз, сортируя список чисел от 1 до 100.

Однако бывают редкие случаи, когда он не сортируется должным образом, и будет 1 случайное число, которое не будет отсортировано полностью.

Не уверен, где ошибка в моем коде, и что он переполнен стеком для справки.

algorithims.js

const sortArr = [51, 54, 63, 98, 100, 86, 80, 52, 88, 6, 75, 22, 64, 66, 84, 91, 12, 73, 9, 90, 41, 85, 37, 2, 46, 57, 58, 1, 31, 87, 78, 93, 82, 55, 47, 20, 43, 21, 70, 50, 53, 15, 19, 39, 11, 30, 33, 83, 7, 77]


//This bubblesort algoritihm sorts a numbered list

let bubbleSort = (arr) => {
  let counter = 0

  for (let i = 0; i <= sortArr.length; i++) {
    if (sortArr[i] > sortArr[i + 1]) {
      counter += 1
      sortArr.splice(i, 0, sortArr[i + 1])
      sortArr.splice(i + 2, 1)
    }
  }

  if (counter > 1) {
    bubbleSort(sortArr)
  } else {
    console.log(sortArr)
  }

};

bubbleSort(sortArr);

Answer 1

Это должно быть counter >= 1, а не counter > 1.

Потому что для случая, подобного 3,5,3,3 Замена одного элемента делает его 3,3,5,3, и он будет показывать значения массива, а не переходить к другим рекурсивным вызовам.

Но, Стандартная пузырьковая сортировка использует вложенный цикл. Может разорвать внешний цикл, если все отсортировано (как вы сделали с вашей переменной счетчика).

Кроме того, замена элемента может быть выполнена намного быстрее с использованием старой доброй временной переменной.

temp = a;
a = b;
b = temp

ИЛИ крутой,

a ^= b;
b ^= a;
a ^= b