Если вам когда-либо приходилось готовиться к техническому собеседованию, скорее всего, вы знакомы с некоторыми основными методами сортировки. Вы, вероятно, страдали от кодирования пузырьков, методов вставки и сортировки выбором только для того, чтобы позже обнаружить, что временная и пространственная сложность всех из них не совсем идеальна. Тем не менее, если вы планируете получить работу в сфере высоких технологий, вам нужно их знать. В этой статье я собираюсь продемонстрировать добавление функции подкачки к вашим методам сортировки, чтобы очистить ваш код и переместить некоторые ваши функции.

В этом примере мы собираемся использовать метод сортировки вставками, но, как я уже говорил ранее, эта вспомогательная функция будет работать с любым другим методом сортировки. Если вы не знакомы с методом сортировки вставками, в основном то, что мы делаем, — это итерация по элементу массива за раз и определение его места на основе значений вокруг него. Давайте посмотрим поближе:

function insertionSort(array){
  for(let i = 1; i < array.length; i ++){
    let j = i;
    while(j > 0 && array[j] < array[j - 1]){
       swap(j , j - 1, array);
       j -= 1;
   } 
 }
 return array;
}

Мы начинаем итерацию с индекса 1 и работаем в обратном направлении. Мы переназначаем значение i и начинаем нашу работу в обратном направлении с цикла while, который меняет местами j с элементом перед ним, если он меньше числа в предыдущем индексе. Вот анимация, помогающая визуализировать движение:

При каждом добавлении переменной i и вычитании j мы можем гарантировать, что не зайдем слишком далеко в любом направлении. Теперь о настоящей причине, по которой мы здесь, о методе подкачки.

function swap(element1, element2, array){
  const temp = array[element2];
  array[element2] = array[element1];
  array[element1] = temp;
};

Все, что мы делаем, — это присваиваем наш второй элемент временной переменной, чтобы не потерять его. Затем мы присваиваем второму элементу значение первого элемента, а затем, наконец, присваиваем первому элементу значение нашего временного элемента, которое является значением второго элемента. Точно так же мы успешно поменяли местами два элемента в массиве. Мы могли бы так же легко добавить эту функциональность в наш цикл while, и он бы отлично отсортировался, но когда мы разделяем нашу функциональность, наш код не только выглядит чище, но и, если бы это было реальное приложение, мы могли бы повторно использовать этот метод подкачки в других частях. нашего кода. Давайте вместе посмотрим на наш метод сортировки.

function insertionSort(array){
  for(let i = 0; i < array.length; i ++){
    let j = i;
    
    while(j > 0 && array[j] < array[j - 1]){
        swap(j , j - 1, array);
        j -= 1;
      }
    }
  return array;
}
function swap(element1, element2, array){
  const temp = array[element2];
  array[element2] = array[element1];
  array[element1] = temp;
};