Если вам когда-либо приходилось готовиться к техническому собеседованию, скорее всего, вы знакомы с некоторыми основными методами сортировки. Вы, вероятно, страдали от кодирования пузырьков, методов вставки и сортировки выбором только для того, чтобы позже обнаружить, что временная и пространственная сложность всех из них не совсем идеальна. Тем не менее, если вы планируете получить работу в сфере высоких технологий, вам нужно их знать. В этой статье я собираюсь продемонстрировать добавление функции подкачки к вашим методам сортировки, чтобы очистить ваш код и переместить некоторые ваши функции.
В этом примере мы собираемся использовать метод сортировки вставками, но, как я уже говорил ранее, эта вспомогательная функция будет работать с любым другим методом сортировки. Если вы не знакомы с методом сортировки вставками, в основном то, что мы делаем, — это итерация по элементу массива за раз и определение его места на основе значений вокруг него. Давайте посмотрим поближе:
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; };