Быстрая сортировка в js

Я нашел этот статья на среде и пытаюсь понять, что на самом деле делает код.

это код:

помощник

const defaultComparator = (a, b) => {
  if (a < b) {
    return -1;
  }
  if (a > b) {
    return 1;
  }
  return 0;
};

функция сортировки

const quickSort = (
  unsortedArray,
  comparator = defaultComparator
) => {

  // Create a sortable array to return.
  const sortedArray = [ ...unsortedArray ];

  // Recursively sort sub-arrays.
  const recursiveSort = (start, end) => {

    // If this sub-array is empty, it's sorted.
    if (end - start < 1) {
      return;
    }

    const pivotValue = sortedArray[end];
    let splitIndex = start;
    for (let i = start; i < end; i++) {
      const sort = comparator(sortedArray[i], pivotValue);

      // This value is less than the pivot value.
      if (sort === -1) {

        // If the element just to the right of the split index,
        //   isn't this element, swap them.
        if (splitIndex !== i) {
          const temp = sortedArray[splitIndex];
          sortedArray[splitIndex] = sortedArray[i];
          sortedArray[i] = temp;
        }

        // Move the split index to the right by one,
        //   denoting an increase in the less-than sub-array size.
        splitIndex++;
      }

      // Leave values that are greater than or equal to
      //   the pivot value where they are.
    }

    // Move the pivot value to between the split.
    sortedArray[end] = sortedArray[splitIndex];
    sortedArray[splitIndex] = pivotValue;

    // Recursively sort the less-than and greater-than arrays.
    recursiveSort(start, splitIndex - 1);
    recursiveSort(splitIndex + 1, end);
  };

  // Sort the entire array.
  recursiveSort(0, unsortedArray.length - 1);
  return sortedArray;
};

Итак, я потратил некоторое время, чтобы понять, как работает splitIndex. Он начинается с 0 и увеличивается на 1, только если текущий элемент в цикле for меньше, чем точка поворота. Когда мы сталкиваемся с числом, превышающим опорное значение, splitIndex остается на своем значении, а i увеличивается. На следующем шаге, если число также меньше, чем пивот, мы меняем их местами.

Так, например, с этим массивом: [2,4,65,1,15] splitIndex и i равны во время цикла for, пока мы не получим число 65. Здесь splitIndex не увеличивается, и когда мы достигаем числа 1, мы меняем местами 1 и 65.

Я не носитель английского языка, поэтому я не совсем понимаю, что автор имеет в виду:

 // If the element just to the right of the split index,
        //   isn't this element, swap them.

Мне еще предстоит полностью понять, как работает код, но, по-вашему, правильно ли я сказал?

Спасибо

Взгляните на этот вопрос: stackoverflow.com/questions/39665299/…

David 09.04.2019 15:55

Это в основном Схема разбиения Ломуто . Проверка splitIndex != i, вероятно, займет больше времени, чем избегание ненужных свопов.

rcgldr 09.04.2019 16:16
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
В настоящее время производительность загрузки веб-сайта имеет решающее значение не только для удобства пользователей, но и для ранжирования в...
Безумие обратных вызовов в javascript [JS]
Безумие обратных вызовов в javascript [JS]
Здравствуйте! Юный падаван 🚀. Присоединяйся ко мне, чтобы разобраться в одной из самых запутанных концепций, когда вы начинаете изучать мир...
Система управления парковками с использованием HTML, CSS и JavaScript
Система управления парковками с использованием HTML, CSS и JavaScript
Веб-сайт по управлению парковками был создан с использованием HTML, CSS и JavaScript. Это простой сайт, ничего вычурного. Основная цель -...
JavaScript Вопросы с множественным выбором и ответы
JavaScript Вопросы с множественным выбором и ответы
Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний,...
0
2
89
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Переменная splitIndex отслеживает (в той части массива, которую вы сейчас сортируете) разделитель между элементами, которые «меньше» и «равны или больше», чем опорная точка. Ваше описание того, как это работает, кажется в основном правильным.

В общем, если мы сталкиваемся с элементом, который меньше опорного элемента, мы меняем его на элемент в splitIndex, чтобы поместить его в раздел «меньше, чем опорный», а затем увеличиваем splitIndex, чтобы указать, что раздел вырос. Если мы встречаем тот, который равен или больше, мы оставляем его там, где он есть, и не увеличиваем раздел.

Это имеет смысл предполагая, что элемент в splitIndex не меньше, чем стержень. Это верно, если i больше, чем splitIndex, потому что тогда мы уже встретили хотя бы один такой элемент и пропустили его.

Исключением является случай, когда мы В настоящее время проверяем элемент в splitIndex (что будет иметь место, пока все элементы до сих пор были меньше, чем опорная точка). В этом случае мы бы заменяли элемент самим собой. Это лишнее, так что это причина проверки splitIndex !== i.

Что касается

    // If the element just to the right of the split index,
    //   isn't this element, swap them.

Я подозреваю, что автор допустил ошибку в комментарии. Он должен говорить «элемент в индексе разделения», а не «элемент справа от индекса разделения».

Другие вопросы по теме