Share This
Связаться со мной
Крути в низ
Categories
//☕ Объясняем алгоритм быстрой сортировки с помощью JavaScript

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

objasnjaem algoritm bystroj sortirovki s pomoshhju javascript f8d4504 - ☕ Объясняем алгоритм быстрой сортировки с помощью JavaScript

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

objasnjaem algoritm bystroj sortirovki s pomoshhju javascript e586248 - ☕ Объясняем алгоритм быстрой сортировки с помощью JavaScript

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

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

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

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

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

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

objasnjaem algoritm bystroj sortirovki s pomoshhju javascript 22c8ead - ☕ Объясняем алгоритм быстрой сортировки с помощью JavaScript

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

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

objasnjaem algoritm bystroj sortirovki s pomoshhju javascript 08d6cd0 - ☕ Объясняем алгоритм быстрой сортировки с помощью JavaScript

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

objasnjaem algoritm bystroj sortirovki s pomoshhju javascript 3952634 - ☕ Объясняем алгоритм быстрой сортировки с помощью JavaScript

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

objasnjaem algoritm bystroj sortirovki s pomoshhju javascript b405778 - ☕ Объясняем алгоритм быстрой сортировки с помощью JavaScript

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

objasnjaem algoritm bystroj sortirovki s pomoshhju javascript 57d7481 - ☕ Объясняем алгоритм быстрой сортировки с помощью 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 из списка опций.

objasnjaem algoritm bystroj sortirovki s pomoshhju javascript 595cc42 - ☕ Объясняем алгоритм быстрой сортировки с помощью JavaScript

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

objasnjaem algoritm bystroj sortirovki s pomoshhju javascript 9948f31 - ☕ Объясняем алгоритм быстрой сортировки с помощью JavaScript

***

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

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

***

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

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

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

  • 1 views
  • 0 Comment

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

Связаться со мной
Close