26 января 2022

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

Работаю в ИТ 6+ лет в сфере разработки ПО для мобильных устройств. Преимущественно работаю с экосистемой Apple. Разрабатываю для iPhone, iPad, iWatch.
Раскладываем по полочкам, как работает алгоритм быстрой сортировки с помощью JavaScript с пошаговой иллюстрацией каждого шага.
☕ Разбираемся в алгоритме быстрой сортировки с помощью JavaScript

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

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

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

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

***

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    

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

assignment.js
        function QuickSort(List) {

}

    

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

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

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

    

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

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

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

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

    

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

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

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

assignment.js
        
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) позволит нам быстро скопировать все или часть существующего списка в другой список.

assignment.js
        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 на нашем списке значений и посмотрим, будут ли они упорядочены от наименьшего к большему.

assignment.js
        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-файл, который вы написали выше.

index.html
         <!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 из списка опций.

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

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

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

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

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

***

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

Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека фронтендера»

Источники

МЕРОПРИЯТИЯ

Комментарии

ВАКАНСИИ

Добавить вакансию
Head of Media Productions
Москва, от 200000 RUB до 500000 RUB
Программист 1C
Москва, по итогам собеседования

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ