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

0 ∞ 3

В этой статье мы расскажем о концепции сортировки выбором и реализуем ее в 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 = i; 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% быстрее.

Заключение

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

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