☕ Разбираемся в алгоритме быстрой сортировки с помощью JavaScript

Раскладываем по полочкам, как работает алгоритм быстрой сортировки с помощью JavaScript с пошаговой иллюстрацией каждого шага.

Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

1. углубишься в решение практических задач;
2. узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.

Ты также будешь на связи с преподавателем и другими студентами.

В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂

Быстрая сортировка (англ. quicksort) – это метод сортировки значений в списке в последовательные списки с помощью повторяющейся процедуры.

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

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

Метод быстрой сортировки повторяется для всех результирующих списков, пока не останется только одно значение или пустой список значений.

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

У вас есть список значений, как показано ниже:

Что вы хотите сделать, так это упорядочить значения от наименьшего к наибольшему. Как это сделать?

Первое что нужно сделать – это выбрать одно значение и сделать его опорным значением. Выберем число 47. Следующее, что вы должны сделать – поместить значения, которые меньше или равны 47 с левой стороны. Значения больше 47 будут располагаться справа:

Теперь вы будете повторять тот же процесс, пока не останется только одно значение или пустой список значений.

Следующий шаг – начать со списков отдельных значений. Затем поместить значение слева от опорного значения, если оно уже находится слева, или поместите его справа, если оно уже находится справа.

Вот как будут выглядеть окончательные результаты:

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

Метод быстрой сортировки с помощью Javascript

Первое что вы сделаете – это определите переменную для значений, используя const.

const values = [2, 27, 14, 52, 31, 96, 73, 47, 22, 6];

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

function QuickSort(List) {

}

Функция QuickSort принимает один параметр, называемый List.

Следующее, что вы сделаете – это проверите длину списка. Если длина равна 1, тогда вы возвращаете список как есть:

function QuickSort(List) {
  if(List.length <= 1) {
    return List;
  }
}

Давайте теперь выберем опорное значение и создадим два пустых списка.

Назовем один список leftList, а другой список – rightList.

function QuickSort(List) {
   if (List.length <= 1) {
       return List;
   }

   const pivot = List[List.length - 1];
   const leftList = [];
   const rightList = [];
}

Как видно из приведенного выше блока кода, опорное значение будет последним значением из нашего списка значений, которые вы определили на первом шаге.

Два пустых списка будут использованы для хранения значений, которые вы сравниваете с опорным значением. Если значение меньше или равно опорному значению, то оно будет храниться в leftList. Если значение больше, чем опорное значение, то оно будет храниться в rightList.

Чтобы реализовать это, воспользуемся циклом for, как показано ниже.

function QuickSort(List) {
   if (List.length <= 1) {
       return List;
   }

   const pivot = List[List.length - 1];
   const leftList = [];
   const rightList = [];

   for (let i = 0; i < List.length - 1; i++) {
       if (List[i] < pivot) {
           leftList.push(List[i]);
       }
       else {
           rightList.push(List[i])
       }
   }
}

Теперь вызовем QuickSort в списке leftList и rightList, чтобы разделить их и полностью отсортировать. Чтобы сделать это, используйте оператор расширения из Javascript.

Оператор расширения (англ. spread operator) позволит нам быстро скопировать все или часть существующего списка в другой список.

function QuickSort(List) {
   if (List.length <= 1) {
       return List;
   }

   const pivot = List[List.length - 1];
   const leftList = [];
   const rightList = [];

   for (let i = 0; i <= List.length - 1; i++) {
       if (List[i] < pivot) {
           leftList.push(List[i]);
       }
       else {
           rightList.push(List[i])
       }
   }

   return [...QuickSort(leftList), pivot, ...QuickSort(rightList)];
}

Чтобы проверить, работает код или нет, вызовем функцию QuickSort на нашем списке значений и посмотрим, будут ли они упорядочены от наименьшего к большему.

const values = [2, 27, 14, 52, 31, 96, 73, 47, 22, 6];

function QuickSort(List) {
   if (List.length <= 1) {
       return List;
   }

   const pivot = List[List.length - 1];
   const leftList = [];
   const rightList = [];

   for (let i = 0; i < List.length - 1; i++) {
       if (List[i] < pivot) {
           leftList.push(List[i]);
       }
       else {
           rightList.push(List[i])
       }
   }

   return [...QuickSort(leftList), pivot, ...QuickSort(rightList)];
}

console.log(QuickSort(values));

Чтобы увидеть результат, нужно создать HTML-файл и подключить к нему JavaScript-файл, который вы написали выше.

 <!DOCTYPE html>
<html lang="en">
<head>
   <meta charset="UTF-8">
   <meta http-equiv="X-UA-Compatible" content="IE=edge">
   <meta name="viewport" content="width=device-width, initial-scale=1.0">
   <title>Document</title>
</head>
<body>

   <script src="./assignment.js"></script>
</body>
</html>

После этого откройте HTML-файл в браузере. Затем кликните правой кнопкой мыши на странице и выберите Inspect из списка опций.

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

Метод быстрой сортировки очень эффективный метод, который обеспечивает O(nlog(n)) производительность в среднем и его относительно легко реализовать.

Пример доступен на Github!

Материалы по теме

• ☕ Распространенные алгоритмы и структуры данных в JavaScript: основные понятия и работа с массивами
• ☕ Распространенные алгоритмы и структуры данных в JavaScript: объекты и хеширование
  
• ☕ Must-have алгоритмы для работы со строками на C++
  

Источники

• https://dev.to/the_greatbonnie/quicksort-algorithm-explained-with-diagrams-and-javascript-fe9