Сортировка выбором в JavaScript

В данной статье мы расскажем о концепции сортировки выбором и реализуем ее в JavaScript.

Сортировка выбором

При использовании этого алгоритма массив делится на две части –отсортированную и несортированную. Сортированный список находится вначале. Все элементы справа от последнего отсортированного элемента считаются несортированными.

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

После этого программа снова находит подходящий элемент, меняя его на крайний левый элемент несортированного списка и расширяя отсортированный список.

После каждой итерации надо проверять на один элемент меньше, пока не будет отсортирован весь массив или список.

Рассмотри, как сортировка выборкой работает с массивом:

 5, 2, 4, 6, 1,
Сортировка выбором в JavaScript

Реализация сортировки выборкой

Перейдем к реализации данного алгоритма в JavaScript:

function selectionSort(inputArr) { let n = inputArr.length; for(let i = 0; i < n; i++) { // Находим наименьшее число в правой части массива let min = i;  for(let j = 0; j < n; j++){            if(inputArr[j] < inputArr[min]) {                min=j;             }         }         if(min!= i) {             // Заменяем элементы let tmp = inputArr[i];              inputArr[i] = inputArr[min];             inputArr[min] = tmp;              }    }    return inputArr;}

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

Сейчас добавим входной массив и вызовем возможность:

let inputArr = [5, 2, 4, 6, 1, 3];selectionSort(inputArr);console.log(inputArr);

Результат работы кода:

(6) [1, 2, 3, 4, 5, 6]

Временная сложность алгоритма

На первой итерации, в массиве, состоящем из n элементов, мы делаем n-1 сравнений и одну замену. Во второй итерации мы выполняем n-2 сравнения и т.д. Следовательно, общее число сравнений будет(n-2) +(n-1) + … + 1, что в сумме составит n(n-1) / 2 =(n 2 -n) / 2. Это дает нам время работы O(n 2).

O(n 2) – довольно высокий показатель временной сложности алгоритма. При сортировке набора используются более быстрые алгоритмы сортировки с временной сложностью O(nlogn).

С другой стороны, по сравнению с временной сложностью иных алгоритмов сортировка выборкой будет более эффективной. В том числе пузырьковой и гномьей сортировки.

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

Варианты сортировки выбором

Сортировка выборкой – основа для некоторых популярных и эффективных алгоритмов сортировки! Самым известным из них будет множественная сортировка, которая использует структуру данных куча для хранения элементов. Это ускоряет поиск, удаление элементов и временную сложность алгоритма с O(n ^ 2) до O(nlogn).

Другой вариант – двунаправленная сортировка выбором. Она выполняет ту же самую работу на 25% быстрее.

Заключение

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

Но если входной набор данных небольшой, то сортировка выбором будет лучшим вариантом, чем быстрая сортировка или сортировка слиянием. Но в данных случаях сортировка вставкой оказывается более эффективной.

Добавить комментарий

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